K en yakın noktalar. Zaman karmaşıklığı O (n), O değil (nLogn). Nasıl?

Question

Google haritaları gibi enlem ve boylam şeklinde bir milyonlarca koordinat listesi verildiğinde, en yakın k şehirlerini belirli bir yere nasıl yazdıracaksınız?

Bir röportaj sırasında bu soruyu sordum. Görüşmeci, bunun N (N) 'de, NlogN olan tüm listeyi sıralamak yerine k'ye kadar ekleme sıralamalarını kullanarak yapılabileceğini söyledi. İnternette başka cevaplar buldum, ve çoğu NLogN ... o [görüşmeci] doğru mu?

Answer 1

Sanırım, mesafeyi hesaplarken K elemanlarının listesini tutabilirsiniz.

Yeni bir uzaklığa sahip olduğunuz her sefer, en büyük olandan küçükse listeye yerleştirin ve en büyüğü kaldırın.

Sıralı bir dizi kullanıyorsanız bu ekleme, O (k) veya ikili bir yığın kullanıyorsanız O (logK) olabilir.

En kötü durumda, n kere ekleyeceksiniz. Toplamda, O (NK) veya O (NlogK) olacaktır. K yeterince küçük ise, O (N) 'dir. Eğer iki yarısını size bunlardan tür tek buldukça -

Answer 2

O QuickSelect (https://en.wikipedia.org/wiki/Quickselect)

Temelde bir değişiklik ile quicksort var bir algoritma var:

• yarım k-inci pozisyon içeriyorsa - subdividing ve sorting ile devam edin
• Eğer k-th pozisyonundan sonra bir yarısı tamamen dolduysa - onu sıralamaya gerek yok ise, bu elemanlarla ilgilenmiyoruz
• Eğer k-th pozisyonundan önce bir yarısı ise Düzenlemek için ed, tüm bu elemanlara ihtiyacımız var ve bunların sırası önemli değil

Son işlemden sonra, dizinin ilk k yerlerinde en yakın k öğelerine sahip olacaksınız (ancak bunlar zorunlu olarak sıralanmamıştır).

Her adımda yalnızca bir buçuk işlemi yaptığınızdan, zaman n+n/2+n/4+n/8+...=2n (sabitleri göz ardı ederek) olacaktır.

Garantili O(n) için her zaman iyi bir dönüş seçebilirsiniz; örn. medyan medyanı (https://en.wikipedia.org/wiki/Median_of_medians).

Answer 3

Ayrıca, bu algoritmayı, belirli bir çözünürlük içinde mesafeleri otomatik olarak sıralayabilecek bir "HashMap benzeri" dizi kullanan O (N) karmaşıklığı ile de kullanabilirsiniz.

Fikir şehirler listesinde döngü olduğunu

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); 
} 

ilgi koordinat ile mesafeyi hesaplamak ve sonra nerede kent gereken belirlemek için mesafeyi kullanın: Burada

Java sözde kod "HashMap-like" dizisine cityDistances eklenir. Uzaklık ne kadar küçük olursa, endeks 0'a yakın olacaktır.
resolution ne kadar küçükse, son döngüden sonra 10 şehirle sonuçlanacaktır ( closestCities).