mergesort - マージソートでのマージ操作がO（n）である理由

Question

マージソート分割統治操作の場合、ボトムアップマージフェーズでどのくらいの時間が必要ですか？私のインストラクターは、それは線形であると言っているので、そうなるでしょうO(n)。しかし、私はそれを取得できませんでした。どのように線形になりますか？

マージ操作はどのように線形になりO(n)ますか？

Answer 1

2つのアレイのマージ操作は、アレイをスキャンし、2つの中で最も低い/最も高いものを選択します。

だからあなたは

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]配列であるかどうかを確認し、3つのループによる反復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はすでにスキャンされているため、2番目のループは実行されません。

3番目のループは追加します

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 ²）になります。