爲什麼合併排序最差情況運行時間O（n log n）？

Question

有人可以用簡單的英語向我解釋或簡單的解釋嗎？

Answer 1

在「傳統」合併排序中，每次傳遞數據都會使已排序子部分的大小加倍。第一遍之後，文件將被分類爲長度爲二的部分。第二次通過後，長度爲四。然後是8,16等等，直到文件的大小。

有必要保持加倍排序部分的大小，直到有一個部分包含整個文件。它將使段大小的lg（N）加倍以達到文件大小，並且數據的每次傳遞將花費與記錄數成比例的時間。

Answer 2

這是因爲無論是最差情況還是平均情況，合併排序都會在每個階段將數組分成兩部分，每個階段給出lg（n）分量，另一個N分量來自每個階段的比較階段。所以把它合併成幾乎是O（nlg n）。無論是平均情況還是最壞情況，lg（n）因子總是存在。其餘N因素取決於在兩種情況下進行的比較所作出的比較。現在最糟糕的情況是每個階段的N次輸入發生N次比較。所以它變成了O（nlg n）。

Answer 3

合併排序使用分而治之的方法來解決排序問題。首先，它使用遞歸將輸入分爲一半。分割後，將其分成一半並將它們合併爲一個分類輸出。參見圖

這意味着，最好先進行排序一半的問題，並做了簡單的合併子程序。因此瞭解合併子例程的複雜性以及在遞歸中調用多少次非常重要。

合併排序的僞代碼非常簡單。

# C = output [length = N] 
# A 1st sorted half [N/2] 
# B 2nd sorted half [N/2] 
i = j = 1 
for k = 1 to n 
    if A[i] < B[j] 
     C[k] = A[i] 
     i++ 
    else 
     C[k] = B[j] 
     j++ 

這是很容易看到，在每個循環中，您將有4個操作：ķ++，我++或J ++，則if語句和歸屬C = A | B。因此，您將有小於或等於4N + 2的操作，從而產生複雜性。爲了證明4N + 2將被視爲6N，因爲對於N = 1是正確的（4N + 2 < = 6N）。

所以假設你有ň元素的輸入，並承擔ñ是2的功率在每一個層次，你有兩次以上的子問題與從先前輸入的一半元素的輸入。這意味着在等級j = 0,1,2，...，lgN將會有輸入長度爲N/2^j的子問題。操作中的每個級別Ĵ的數量將小於或等於

2 ^Ĵ* 6（N/2^j）的6N =

觀察到它好好嘗試重要的級別，您將始終擁有更少或相等的6N操作。

由於有LGN + 1個級別，複雜度將是

O（6N *（LGN + 1））= O（6N * LGN + 6N）= 爲O（n LGN）

參考文獻：

• Coursera course Algorithms: Design and Analysis, Part 1

Answer 4

在每個階段陣列分割到您有單個元件即打電話給他們的子列表的階段，

• 後，我們比較與其相鄰子列表的每個子表的元素。例如，[重用@ DAVI的圖像 ]

  

  1. 在階段-1中的每個元件與相鄰一個進行比較，因此n/2比較。
  2. 在階段2，子列表的每個元素都與其相鄰子列表進行比較，因爲每個子列表都被排序，這意味着兩個子列表之間進行的最大比較次數爲< =子列表的長度，即2（在Stage- 2）以及第4階段和第4階段的4個比較，因爲子列表的長度保持倍增。這意味着每個階段的最大比較次數=（子列表長度*（子列表數量/ 2））==> n/2
  3. 正如您所觀察到的，階段的總數將是log(n) base 2 因此，總數複雜性將== （在階段的每個階段*比較次數的最大數目）== O（（N/2）*的log（n））==> O（n日誌（n））的

Answer 5

歸併算法需要三個步驟：

1. 除法步驟計算子陣列的中間位置，它需要恆定的時間O（1）。
2. conquer step遞歸地對每個大約有n/2個元素的兩個子數組進行排序。
3. 合併步驟合併總共n個元素，每次最多需要n次比較，因此需要O（n）。

該算法需要大約logn階段對n個元素的數組進行排序，因此總時間複雜度爲nlogn。

Answer 6

許多其他的答案是偉大的，但我沒有看到高度和深度提及任何有關「合併排序樹」的例子。這是另一種解決問題的方法，它專注於樹的研究。這裏的另一個圖像，以幫助解釋：

只是一個概括：其他答案已經指出，我們知道，合併序列的兩個分類片的工作線性時間（即我們從調用該合併的輔助函數運行主要分類功能）。
現在看一下這棵樹，我們可以把根的每個後代（根除外）作爲對排序函數的遞歸調用，讓我們試着評估我們在每個節點上花了多少時間...既然切片序列和合並（兩者一起）需要線性時間，任何節點的運行時間相對於該節點序列的長度是線性的。

這裏是樹深度進來的地方。如果n是原始序列的總大小，則任何節點的序列大小爲n/2 ⁱ，其中i是深度。這在上圖中顯示。結合每個切片的線性工作量，我們的運行時間爲樹中每個節點的O（n/2 ⁱ）。現在我們只需要對n個節點進行總結。做到這一點的一種方法是認識到樹中每個深度級別都有節點。因此，對於任何級別，我們都有O（2 ^我 * n/2 ^我），這是O（n），因爲我們可以取消2 ^我 s！如果每個深度都是O（n），我們只需要乘以這個二叉樹的logn即高度。答：O（nlogn）

參考：Data Structures and Algorithms in Python