給定一個 2D 平面和 N 個點 (n1=(x1,y1), n2=(x2,y2)..., nN=(xN,yN))，什么是快速（O(n) 或更好）算法將找到任何點的最近鄰居（例如n1最近鄰居是n3，n2最近鄰居是n4）。我正在考慮將其存儲在字典中，其中鍵是點，值是鄰居。SO 上似乎有很多類似的問題，但我找不到任何 Python 代碼或非其他語言的答案。
2 回答
子衿沉夜
TA貢獻1828條經驗 獲得超3個贊
平均而言，可以產生比 O(n) 更好的結果的簡單解決方案是使用kd 樹來存儲點。構建樹的最壞情況復雜度為 O(nlogn)。之后的搜索平均為O(logn)，最壞情況為 O(n) （通常對于遠離所有其他數據的點）。
此外，您可能對 LSH 或局部敏感散列感興趣，雖然它是一種近似方法，這意味著您不會總是得到正確的答案，對于高維數據，它提供了重要的加速，其復雜性與所選參數密切相關。
暮色呼如
TA貢獻1853條經驗 獲得超9個贊
對于給定的點P，簡單的解決方案：
計算 P 與所有其他點的距離，時間復雜度為 O(n)。
將它們保存為元組列表（或類似的數據結構），即（點，距 P 的距離）的元組。
遍歷列表即可獲得前 K 個最接近的點，時間復雜度為 O(n)。
第二種解決方案會花費更多的空間復雜度 (O(n^2)) 和隨著時間的推移進行維護，但會縮短查找 K 個最近鄰居的時間：
將每個點的字典保存為按距離排序的點列表（或類似的數據結構） - 構建此表一次的時間復雜度為 O(n^2 * log(n))。
查找 K 個最近點的時間復雜度為 O(k) - 字典訪問 + 從有序列表中復制 k 個元素。
時間復雜度的開銷在于以一種保持該數據結構有效的方式添加新點或刪除舊點 - 兩者都為 O(n*log(n))。
您選擇的解決方案應該針對您想要優化的內容
添加回答
舉報
0/150
提交
取消