我無法決定從 n 點集中選擇離某個點 P 最近的 k 個點的最快方法。我的猜測如下：
- 計算 n 距離，對其排序并選擇 k 個最小值；
- 計算逐點距離并更新一個 k 大小的點堆疊；
歡迎任何其他方式。
uj5u.com熱心網友回復：
獲取中位數是 O(n) 操作，因此整個問題的復雜度最低為 O(n) - 計算所有距離并找到按此閾值劃分整個集合的第 k 個最小元素。
也可以在 K >> k 的塊中作業。前k個距離的最大值作為一個初步閾值：不需要考慮所有比這更遠的點。而是將所有小于該點的點放入一個陣列中，在陣列大小接近K后，可以使用第k元素線性演算法對陣列進行重新磁區。
uj5u.com熱心網友回復：
對于任何 k 值，找到最小的 k 個元素是 O(n)。如果您需要對 k 個元素進行排序，則為 O(n log k)。這就是磁區演算法。
你最好閱讀維基百科上的演算法。它是快速排序，但您只需要在一側“遞回”，因為另一側可以保證完全退出或完全進入。有一些昂貴的技巧可以保證 O(n log n) 而不僅僅是平均值。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520460.html
標籤：算法计算机科学