K最近点。時間複雑度O（n）ではなく、O（nLogn）である。どうやって？

Question

Googleマップと同様に、緯度と経度の形で100万リストの座標が与えられていますが、どの地点に最も近いk都市をどのように印刷しますか？

私はこの質問をインタビュー中に聞いていました。インタビュアーは、これは、O（n）では、NlogNであるリスト全体をソートするのではなく、kまでの挿入ソートを使用して行うことができると述べています。私は他の回答をオンラインで見つけ、ほとんどがNLogN ...彼[面接官]は正しいのですか？

Answer 1

私は、距離を計算するとき、あなたはK要素のリストを維持することができると思います。

新しい距離がある場合は、最大のものよりも小さい場合はリストに挿入し、最大のものを削除します。

この挿入は、ソートされた配列を使用している場合はO（k）、バイナリヒープを使用している場合はO（logK）になります。

最悪の場合、n回挿入します。合計で、O（NK）またはO（NlogK）になります。 Kが十分に小さい場合、それはO（N）である。

Answer 2

それはquickselectのアルゴリズム（https://en.wikipedia.org/wiki/Quickselect）

は、基本的には変更を加えたクイックソートだだ - あなたはそれらの並べ替えだけ半分ずつ持っている時はいつでも：半分はk番目の位置が含まれている場合

• を -
• 半分が完全にk番目の位置の後にある場合、ソートする必要はありません。これらの要素には関心がありません。
• 半分が完全にk番目の位置の前にある場合それをソートするには、これらの要素がすべて必要であり、その順序は関係ありません。

終了後、配列の最初のk個の場所に最も近いk個の要素があります（必ずしもソートされているわけではありません）。

すべてのステップで半分しか処理しないので、時間はn+n/2+n/4+n/8+...=2n（定数は無視されます）です。

保証のあるO(n)の場合、いつでも、たとえばメジアンの中央値（https://en.wikipedia.org/wiki/Median_of_medians）。

Answer 3

また、指定された解像度内で距離を自動的にソートする "HashMapのような"配列を利用するO（N）の複雑さでこのアルゴリズムを使用することもできます。

アイデアは都市のリストをループにある

City[] cities = //your city list 
Coordinate coor = //the coordinate of interest 

double resolution = 0.1, capacity = 1000; 

ArrayList<City>[] cityDistances = new ArrayList<City>[(int)(capacity/resolution)]; 
ArrayList<City> closestCities = new ArrayList<City>(); 

for(City c : cities) { 
    double distance = coor.getDistance(c); 
    int hash = distance/resolution; 

    if(cityDistances[hash] == null) cityDistances[hash] = new ArrayList<City>(); 
    cityDistances[hash].add(c); 
} 


for(int index = 0 ; closestCities.size() < 10 ; index++) { 
    ArrayList<City> cList = cityDist[index]; 
    if(cList == null) continue; 
    closestCities.addAll(cList); 
} 

は、関心の座標との距離を計算し、次にどこの都市がすべきかを決定するために距離を使用します。ここでは

は、Javaでの擬似コードです"HashMapのような"配列 cityDistancesに追加することができます。距離が小さいほど、インデックスは0に近くなります。 resolutionが小さいほど、リスト closestCitiesは最後のループ後に10都市になる可能性が高くなります。