算法來尋找最接近100明星原點

問：有包含超過一百萬點（X，Y），其中每一個代表一個明星的文件。（a，b）處有一顆行星地球。現在，任務是構建一個算法，將最接近的100顆恆星返回到地球。算法的時間和空間複雜度是多少？

這個問題已經多次在各種採訪中被問到。我試圖查找答案，但找不到滿意的答案。

一種方法來做到這一點，我認爲可能會使用大小爲100的最大堆。計算每個星的距離，並檢查距離是否小於最大堆的根。如果是，請將其替換爲root並調用heapify。

其他更好/更快的答案？

P.S：這不是一個家庭作業問題。

2012-02-08 noMAD

[在長度爲n的列表中查找x個最小整數]的可能重複（http://stackoverflow.com/questions/3764355/find-the-x-smallest-integers-in-a-list-of-長度-n） – hugomg 2012-02-08 22:16:43

是的，可惜。這是一個有趣的問題，但已經在這裏回答。 – 2012-02-08 22:21:24

@missingno：它有點類似，但這個問題可以很容易地通過我上面提供的解決方案來解決。這裏有一些額外的計算需要，我想知道是否有辦法將它們最小化。 – noMAD 2012-02-08 22:31:28

實際上，您可以通過使用非常聰明的技巧在O（n）和空間O（k）上做到這一點，其中k是您想要的最近點數。

的selection problem是如下：給定元件的陣列和一些索引i，重新排列所述陣列的所述元件，使得所述第i個元素是在正確的位置，比所述第i個元素更小的所有元素都向左，並且所有大於第i個元素的元素都在右側。例如，給定陣列

40 10 00 30 20

如果我試圖基於索引2（零索引）來選擇，一個結果可能是

10 00 20 40 30

由於在索引2（20）的元件是在正確的地方，左邊的元素小於20，右邊的元素大於20.

事實證明，由於這是一個不太嚴格的要求比實際排序數組，它是可能的這在時間O（n），其中n是數組的元素的數量。這樣做需要一些複雜的算法，如median-of-medians算法，但確實是O（n）時間。

那麼你如何在這裏使用它？一種選擇是將文件中的所有n個元素加載到數組中，然後使用選擇算法在O（n）時間和O（n）空間（這裏k = 100）中選擇最高k值。

但你實際上可以做得比這更好！對於任何你想要的常量k，保持2k個元素的緩衝區。將文件中的2k個元素加載到數組中，然後使用選擇算法重新排列它，使得最小的k個元素位於數組的左半部分，最大的位於右側，然後丟棄最大的k個元素（它們可以' t是k個最近點中的任何一個）。現在，從文件中加載k個更多的元素到緩衝區中並再次執行此選擇，並重復此操作，直到處理完文件的每一行。每次您做出選擇時，都放棄緩衝區中最大的k個元素，並保留迄今爲止所見到的k個最近點。因此，最後，您可以最後一次選擇前k個元素並查找前k個元素。

新方法的複雜性是什麼？那麼，你使用O（k）內存作爲緩衝區和選擇算法。由於您在讀取k個新元素之後調用select，因此最終調用select O（k）總共爲O（n/k）次的緩衝區。由於在一個大小爲O（k）的緩衝區上選擇需要時間O（k），因此這裏的總運行時間是O（n + k）。如果k = O（n）（一個合理的假設），這需要時間O（n），空間O（k）。

希望這會有所幫助！

來源

2012-02-08 22:20:40 templatetypedef

謝謝，我確實學到了一些東西:) – noMAD 2012-02-08 22:35:20

對此，我會添加一個優化。在向緩衝區添加新元素之前，如果它大於先前迭代中找到的第k個最大值，則丟棄該元素。在這個「大於」測試中，您可以在測試實際距離之前首先檢查單個座標是否較大。這根本不會改變big-O，但它避免了大量的距離計算，並且平方根操作相當緩慢。所以你得到一個更好的常數。 – btilly 2012-02-08 22:40:52

@btilly：由於sqrt是一個單調函數，您可以隨時避免sqrt操作。使距離最小化的點也使距離平方最小化（正方形消除sqrt）。 – 2012-02-08 23:03:22

這是一個著名的問題，並出現了很多解決的爲： http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

，如果你沒有發現它是有用的，還有一些其他的資源，如Rurk的計算幾何的書。

來源

2012-02-08 22:34:08 orezvani

查詢點在這種情況下是已知的，所以我們甚至不必去knn。 – 2012-02-08 23:43:23

你的算法是正確的。請記住，程序的時間複雜度爲O（n。log 100）= O（n），除非找到最近點的數量可能會有所不同。

來源

2012-02-08 23:48:28

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()

來源

2015-06-01 18:24:11 aertoria

我剛剛在Python中爲您的問題編碼，希望它有幫助 – aertoria 2015-06-01 18:25:53

爲了詳細說明的MaxHeap溶液你將建立一個最大堆與來自文件（在這種情況下，K = 100）中的前k個元素。

最大堆的關鍵是它與地球的距離（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）時間來完成。最後，我們只剩下最大堆中的k個元素。你可以調用heapify k次來返回所有這些k元素。這是另一個O（klogk）。總體時間複雜度爲O（k +（nk）logk + klogk）。

來源

2015-07-27 16:41:44

算法來尋找最接近100明星原點

回答

相關問題