最近對點（CLRS皮克1043）的：分割一個排序後的數組分成兩個有序陣列

在查找最近點對在O（nlgn）時間的運行時間，僞代碼，用於分離一個已排序列表分成兩個已排序的列表（ CLRS第三版第1043頁）據說在O（n）時間運行。最近對點（CLRS皮克1043）的：分割一個排序後的數組分成兩個有序陣列

algorithm from CLRS pg 1043

然而，這種假設線在固定時間內4次運行，我覺得很難相信（我假設它在O（LGN運行）時，如果它被存儲爲二進制樹，給總的運行時間爲O（nlgn）

Y是一個有序的數組，YL和YR是兩個新的子數組，PL是Y的隨機序列子集，YL是相同的子集，但是在排序順序

我在哪裏出錯我的推理？

來源

2016-12-26 max_max_mir

將Y的元素添加到PL時，將其標記爲屬於PL。（只是猜測，我不知道PL是如何形成的）。 –

如果PL製作得像合理的hashmap/hashset，預期的查找平均時間可以是O（1），但最壞的情況是另一回事...... –

@AlexanderAnikin我們實際上正在處理大O符號的最壞情況。 –

爲了簡單起見，我們假設該列表是整數，而不是字符串或整數這樣可以大大這裏的事情複雜化。

有兩種計算方法在這裏考慮：

for循環：這對於運行Y的時間長度，這我假設是N這裏
棘手的部分 - 的Y比較[I]與PL（注：如果我們認爲它們是字的大小，兩個數字的比較是恆定的）。現在，由於我們正在處理隨機訪問機器，訪問Y [i]是不變的。然而，爲了將它與一個長度爲PL的數組進行比較，例如，k需要k時間。如果這個k非常小並且與輸入數組Y的大小無關，那麼理想情況下這將是恆定的。

若要以更高的精度編寫它，則意味着您考慮k次比較所需的時間（PL的長度），因此此僞代碼的總時間爲O（Nk）。但是，如果假設k是隨機的，獨立於N保持爲真，那真的是O（N）

來源

2016-12-26 06:19:43

PL依賴於N--你可以假設k = N/2，但那 –

我不知道它是如何應該在書裏工作，但思考方式的算法外觀就像，你能想出以下的想法：

Y[i]，X[i]，YL[i]，XL[i]，YR[i]和XR[i]是整數，對應於i的index個點（所以你只需要存儲一些全球其中，給定的索引陣列，返回x或y座標）。
PL[i]是一個布爾值，true如果i-點在左邊部分，否則爲false。

在每個遞歸步驟，你可以計算PL[i]使用y座標（O(n)時間）。然後你分開兩套的點的集合「左」和「右」使用來自書中的算法，通過if PL[Y[i]]更換線if Y[i] in PL（例如訪問O(1)，所以整體而言，我們得到O(n)）。

這有O(n)時間複雜度和使用O(n)內存。

因此最接近的對問題在T(n) = O(n log n)中以這種方式解決。

來源

2016-12-26 13:22:17 md5

我同意它有O（n log n）時間，但是這本書宣稱它有O（n）次。 –

@max_max_mir：對於整個最接近的對問題，我的意思是「O（n log n）」（這個確實是'O（n）'的特定步驟）。 – md5

你能提供一個這樣的例子嗎？假設Y = [（3,1），（2,2），（4,3），（1,4），（6,5）]並按y座標排序。 PL是[（1,4），（3,1）]，並按x座標排序。如果我在Y的任何一點查找列表PL，它需要我O（n）時間。不過，我認爲你說有一種方法可以進行反向查找以確定一個點是否在PL中，這需要O（1）次 - 但我不太明白。 –

最近對點（CLRS皮克1043）的：分割一個排序後的數組分成兩個有序陣列

回答

相關問題