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