ファーストを見つけるフレーズが適切な質問を私に聞かせて：アルゴリズムが原点に100最も近い星
Q：スターをそれぞれ表す百万人以上の点（x、y）を含むファイルがあります。 （a、b）には地球があります。さて、100個の最も近い星を地球に戻すアルゴリズムを構築することです。あなたのアルゴリズムの時間と空間の複雑さはどうなりますか？
この質問はさまざまなインタビューで何度も尋ねられています。私は答えを見てみましたが、満足できるものを見つけることができませんでした。
サイズ100の最大ヒープを使用している可能性がある方法の1つです。各星の距離を計算し、その距離が最大ヒープのルートより小さいかどうかを確認します。はいの場合は、ルートに置き換えてheapifyを呼び出します。
その他のより良い/より速い回答ですか？
P.S：これは宿題に関する質問ではありません。
あなたは実際にO（n）とO（k）の時間でこれを行うことができます。ここで、kは非常に巧妙なトリックを使って、あなたが望む最も近いポイントの数です。次のように
selection problemである：要素のアレイと、いくつかのインデックスiが与えられると、i番目の要素が正しい位置にあり、i番目の要素よりも小さいすべての要素が左になるように配列の要素を並べ替えますi番目の要素より大きな要素はすべて右になります。 Iインデックス2（ゼロインデックス付き）に基づいて選択しようとした場合、インデックス2（20）の要素が入っているので、例えば、配列
40 10 00 30 20
所与一の結果は
10 00 20 40 30
かもしれません正しい場所、左の要素は20より小さく、右の要素は20より大きい。
これは実際に配列を並べ替えるより厳しい要件ではないことが判明した。これは時間O（n）であり、ここでnは配列の要素数です。そうするには、median-of-mediansアルゴリズムのような複雑なアルゴリズムが必要ですが、実際にはO（n）時間です。
ここでどのように使用しますか？ 1つのオプションは、ファイルからn個の要素をすべて配列にロードし、選択アルゴリズムを使用してO（n）時間とO（n）空間（ここではk = 100）の先頭kを選択することです。
しかし、実際にはこれよりも優れています。任意の定数kに対して、2k要素のバッファを維持します。ファイルから配列に2k要素をロードし、次に選択アルゴリズムを使用して、配列の左半分にk要素があり、右に最大要素がくるように並べ替えます。次に、最大k要素を破棄しますtはk個の最も近い点のいずれかである）。今度は、k個の要素をファイルからバッファにロードしてこの選択をもう一度行い、ファイルのすべての行を処理するまでこれを繰り返します。選択するたびに、バッファ内の最大のk個の要素を破棄し、これまでに見たk個の最も近い点を保持します。結果的に、最後に1つ前のk個の要素を選択して先頭kを見つけることができます。
新しいアプローチの複雑さは何ですか？バッファと選択アルゴリズムにO（k）メモリを使用しています。 k個の新しい要素を読んだ後にselectを呼び出すので、サイズO（k）のバッファにselectをコールすると、O（n/k）回の合計になります。サイズO（k）のバッファ上の選択は時間O（k）を要するので、ここでのランタイムの合計はO（n + k）である。 k = O（n）（妥当な仮定）であれば、これは時間O（n）、空間O（k）を要する。
希望すると便利です。
ありがとう、私はいくつかを学んだ:) – noMAD
これに私はもう1つの最適化を追加します。バッファに新しい要素を追加する前に、以前の反復で見つかったk番目の最大値よりも大きいかどうかを破棄します。そして、この「より大きい」テストでは、実際の距離をテストする前に、単一の座標が大きいかどうかを最初に確認できます。これはbig-Oをまったく変更しませんが、距離の計算が大変なので平方根演算はかなり遅いです。だからあなたはより良い定数を得る。 – btilly
@btilly：sqrtは単調関数なので、常にsqrt演算を避けることができます。距離を最小限に抑える点は距離の二乗を最小にします（正方形はsqrtを打ち消します）。 –
それは有名な問題だし、そのために多くのソリューションのがあった：あなたはそれが便利なかった場合 http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm
、このようRurkの計算幾何学の本など、いくつかの他のリソースがあります。
この場合、クエリポイントはすでにわかっているので、knnに行く必要はありません。 –
あなたのアルゴリズムは正しいです。見つけるべき最も近い点の数が変わらない限り、プログラムの時間複雑さはO（n。log 100）= O（n）であることを覚えておいてください。あなたは、ファイル（この場合はk = 100）からの最初のk個の要素とMAX-ヒープを建設するMaxHeapソリューションについては詳しく説明し
import sys,os,csv
iFile=open('./file_copd.out','rU')
earth = [0,0]
##getDistance return distance given two stars
def getDistance(star1,star2):
return sqrt((star1[0]-star2[0])**2 +(star1[1]-star2[1])**2)
##diction dict_galaxy looks like this {key,distance} key is the seq assign to each star, value is a list [distance,its cordinance]
##{1,[distance1,[x,y]];2,[distance2,[x,y]]}
dict_galaxy={}
#list_galaxy=[]
count = 0
sour=iFile.readlines()
for line in sour:
star=line.split(',') ##Star is a list [x,y]
dict_galaxy[count]=[getDistance(earth,star),star]
count++
###Now sort this dictionary based on their distance, and return you a list of keys.
list_sorted_key = sorted(dict_galaxy,key=lambda x:dict_galaxy[x][0])
print 'is this what you want %s'%(list_sorted_key[:100].to_s)
iFile.close()
私はあなたの質問のためにこれをPythonでコーディングしました。 – aertoria
。
最大ヒープのキーは、地球からの距離（a、b）です。 2D平面上の2点間の距離を用いて計算することができる。
dist = (x1,y1) to (x2,y2) = square_root((x2 - x1)^2 + (y2 - y1)^2);
この構築するためにO（k）の時間がかかります。 kからnまでのすべての後続要素について。つまり、（n - k）個の要素は、地球からの距離を取得し、最大ヒープの上端と比較する必要があります。挿入する新しい要素が最大ヒープの上部よりもアースに近い場合は、最大ヒープの先頭を置き換え、ヒープの新しいルートでheapifyを呼び出します。
これは、O（（n-k）logk）時間がかかります。 最後に、max-heapのk要素だけが残っています。 heapifyをk回呼び出して、これらのすべての要素を返すことができます。これは別のO（klogk）です。
全体の時間複雑さは、O（k +（n-k）logk + klogk）となる。
可能な複製[長さnのリストにx個の最小整数を見つける]（http://stackoverflow.com/questions/3764355/find-the-x-smallest-integers-in-a-list-of-長さ - n） – hugomg
はい、残念です。興味深い質問ですが、すでにここで回答しています。 –
@missingno：これは似たようなものですが、私が上記で提供した解決策によって簡単に解決できるのです。ここでは余分な計算が必要なので、最小限に抑える方法があるかどうかを知りたいと思っていました。 – noMAD