爲什麼在合併排序中合併操作是O（n）？

Question

對於合併排序分割和征服操作，自底向上合併階段需要多少時間？我的導師說這是線性的，因此它會是O(n)。但我沒有明白。它將如何是線性的？

合併操作將如何線性O(n)？

Answer 1

合併兩個陣列的操作，是掃描陣列並選取兩個中最低/最高的陣列。

所以你必須

a: [1, 3, 6, 7] 
b: [4, 5, 7, 8] 

你比較喜歡這（樣的僞代碼）

indexA = 0; 
indexB = 0; 
auxilaryArray = []; 
indexAux = 0; 

while true 
    if indexA > len(a)-1 or indexb > len(b) -1 
     break 
    # you are cherry picking one from the two array which is lesser 
    # until any one of these array exausts 
    if(a[indexA] > b[indexB]) 
     auxilaryArray[indexAux++] = b[indexB++] 
    else 
     auxilaryArray[indexAux++] = a[indexA++] 

#append the remaining array 
while indexA < len(a) 
    auxilaryArray[indexAux++] = a[indexA++] 

#appends the remaining array 
while indexB < len(b) 
    auxilaryArray[indexAux++] = b[indexB++] 

你看看數組a[k]，並b[m]由三個環路的和迭代會是k+m。

---

如果

a: [1, 3, 6, 7] 
b: [4, 5, 7, 8] 

下面是該第一循環：

(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2) # 6 iterations; array a exhausted 

第二循環不會因爲a運行已經掃描。

第三環追加

b[2], b[3] # 2 iterations; b exhaused 

你看8 = 4 + 4循環運行？什麼是訂單O(n)。

---

在歸併除法操作是對數的，ln n - 合併部分是線性的。既然你分割和合並回來的順序變成乘法所以Mergesort是O(nln(n))。

不像泡泡，選擇，插入排序從左到右掃描（O（n）），然後通過連續交換（泡泡）適合正確的候選，或通過掃描未排序數組的其餘部分（選擇），或者通過在數組的排序部分（插入）插入正確的位置 - 這些操作是O（n）...所以這些算法的整體順序變爲O（n ）