合併排序運行時間

Question

我知道合併排序的運行時間是O（n * lg（n）），合併排序是比較排序，這也意味着在最壞的情況下它需要Ω（n logn）排序列表。

因此我可以得出結論：合併排序的運行時間是theta（n * lg n）？

Answer 1

如果是O(X)和Omega(X)，這意味着它是Theta(X)。並且log_b1(...)與log_b2(...)倍相同的轉換因子常數。

你說的是（翻譯）：

我知道合併的運行時間排序是，在最壞的情況下，不遜於n log(n)。 [你用數學得出了這個結論。]但是在最壞的情況下，比較排序至少需要n log(n)。

因此，合併排序的最壞情況行爲恰好爲n log(n)是合理的。

這當然暗示你沒有關於你的序列的信息。

編輯：你也可以從第一原則證明。需要注意的是，您可以在線性Theta（N1 + N2）時間內合併兩個排序數組，同時保持它們合併（通過並行掃描它們）。 （細分數組，無論你得到什麼序列，總是會得到Theta（log（N））時間，這是很小的，所以我們忽略它。）現在我們注意到每個元素必須合併Theta（log（N））時間（樹的深度，如果你畫出來的話）。因此Theta（N log（N））。

Answer 2

是的，合併排序的複雜性是theta（n * lgn）。還有另外一種方法可以確定這一點。

合併排序被稱爲分而治之算法。首先它將大小爲n的數組分爲兩個n/2部分，然後在這兩個部分上遞歸，最後將結果合併到排序數組中。

我們假設合併排序時間是T（n）。然後：
- 劃分操作是恆定的theta（1） - 你只需要通過將長度除以2來找到數組的中間元素
- 數組每個部分的遞歸需要T（n/2）時間，這使得2T（N/2）對他們倆的
- 合併操作是已知有THETA（n）的複雜性

所以最後你得到的T（n）的下列經常性方程=：
THETA （1）|如果n == 1
2 * T（n/2）+ theta（n）|如果n> 1

求解這個方程可以得到T（n）= theta（nlgn）;

有關更多詳細信息，請參閱Corman的「算法簡介」一書。