讓a1,...,an是一個實數序列。令m為序列的最小值，令為序列M的最大值。
我證明了序列中存在 2 個元素，x,y，使得|x-y|<=(M-m)/n。
現在，有沒有辦法找到一種演算法，可以找到時間復雜度為 2 個元素的演算法O(n)？
我考慮過對序列進行排序，但由于我對我一無所知，所以M我不能使用基數/桶或我熟悉的任何其他線性時間演算法。
我會很感激任何想法。提前致謝。
uj5u.com熱心網友回復：
首先要注意，真正的閾值應該是(M-m)/(n-1)。
第一步是計算最小m和最大M元素，在 O(N) 中。
你計算mid = (m M)/2價值。
您將值集中在陣列mid的開頭而不是mid陣列的末尾。
您選擇元素數量最多的部分，然后進行迭代，直到保留的數字很少。
如果兩個部分具有相同數量的元素，則可以選擇其中任何一個。如果剩余部分的元素比 多得多n/2，那么為了保持 O(n) 復雜度，您可以只保留n/2 1它們，因為目標不是找到最小的差異，而是一個足夠小的差異。
正如@btilly 的評論中所指出的，此解決方案在某些情況下可能會失敗，例如使用 input [0, 2.1, 2.9, 5]。為此，需要計算左手的最大值和右手的最小值，并測驗答案是否為right_min - left_max。即使解決方案變得不那么優雅，這也不會改變 O(n) 復雜度。
搜索程序的復雜性：O(n) O(n/2) O(n/4) ... O(2) = O(2n) = O(n)。
uj5u.com熱心網友回復：
首先找出
n,M,m. 如果尚未給出，則可以在 中確定O(n)。然后創建
n 1元素的記憶體存盤；我們將使用存盤n 1桶存盤寬度w=(M-m)/n。桶同樣覆寫了值的范圍：桶1來自[m; m w[、桶2來自[m w; m 2*w[、桶n來自[m (n-1)*w; m n*w[ = [M-w; M[和(n 1)th桶來自[M; M w[。現在我們遍歷所有值并根據分配的間隔將它們分類到桶中。每個桶最多應該有 1 個元素。如果桶已經被填滿，這意味著元素之間的距離比半開區間的邊界更近，例如我們找到了
x, y帶有 的元素|x-y| < w = (M-m)/n。如果沒有找到這樣的兩個元素，那么總
n桶n 1中的桶將被一個元素填充。所有這些元素都已排序。我們再次遍歷所有的桶，只比較相鄰桶內容的距離，是否有兩個元素滿足條件。由于桶的寬度，對于不相鄰的桶，條件不能為真：對于那些距離總是|x-y| > w。
（滿足 4. 中最后一個不等式也是原因，為什么區間是半開且不能閉合，以及為什么我們需要n 1桶而不是n。另一種方法是，使用n桶并將現在的最后一個桶設為特殊情況[M; M w]。但是O(n 1)=O(n)使用n 1步驟比對最后一個桶進行特殊封裝更可取。）
運行時間是O(n)針對第 1步和第 2 步的——實際上，對于第 3 步和第 4 步0，我們沒有做任何事情，因為每個桶只有一個元素。總而言之。O(n)O(n)1O(n)
該任務表明，可以對不靠近在一起的元素進行排序，也可以在不考慮精細距離的情況下進行粗略排序，O(n)而不是O(n*log(n)). 它有有用的應用程式。計算機上的數字是離散的，它們具有有限的精度。我已經成功地將這種排序方法用于實時生產代碼中的信號處理/快速排序。
關于@Damien 的評論：對于每個這樣的序列，真實的閾值都可證明是正確的。(M-m)/(n-1)到目前為止，我在答案中假設我們正在查看的序列是一種特殊型別，其中更強的條件為真，或者至少對于所有序列，如果更強的條件為真，我們會在O(n).
如果這是 OP 的一個小錯誤（據說已經證明了更強的條件），我們應該找到兩個元素x, y，|x-y| <= (M-m)/(n-1)我們可以簡化：
- -- 3. 我們將像上面一樣執行步驟 1 到 3，但將
n存盤桶和存盤桶寬度設定為w = (M-m)/(n-1)。桶n現在從[M; M w[.
對于第 4 步，我們將執行以下替代方案：
4./alternative: n每個桶都裝滿一個元素。桶中的元素n必須M并且位于桶間隔的左邊界。對于桶中每個可能的元素，y = M該元素x與桶中元素的距離為：，因此我們找到滿足條件 qedn-1thxn-1th|M-x| <= w = (M-m)/(n-1)xy
uj5u.com熱心網友回復：
Damien 在他的評論中是正確的，正確的結果是必須有 x，y 使得 |xy| <= (毫米)/(n-1)。如果你有序列 [0, 1, 2, 3, 4] 你有 5 個元素，但沒有兩個元素比 (Mm)/n = (4-0)/5 = 4/5 更接近。
使用正確的閾值，解決方案很容易 - 通過掃描輸入一次來找到 M 和 m，然后將輸入分桶到 (n-1) 個大小為 (Mm)/(n-1) 的桶中，將值放在將一對桶的邊界劃分為兩個桶。根據鴿子洞原理，至少一個桶中必須有兩個值。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424317.html
標籤：算法
下一篇：在Unity3D中查找最近的物件