algorithm - マージソートの反復時間

Question

重複の可能性：
マージソートでのマージ操作がO（n）である理由

マージソートに関して各反復が正確にO（n）をとるのはなぜですか？誰かが私にそれを詳細に説明できるでしょうか？そしてなぜC_merge（n）= O（n）？それは、2つのソートされた配列をマージする時間を意味しますか？

Answer 1

アイデアは、2つのソートされた配列があり、一方が他方の最大の要素よりも大きい最小の要素を持つ2つの配列ではないということです。私が言いたかったのは、そうではないということ[1, 3, 9, 12]です[13, 17, 19]。[3, 12, 13, 17]しかし、それはとのようなもの[1, 9, 19]です。

ほら、後でそれらを追加することはできません。では、どのように組み合わせるのですか？次のアルゴリズムに従います。

1. 最初にm要素があり、2番目に要素があるとしますn。サイズの補助配列を作成しますm+n。これにより、結合およびソートされた最終的な配列が格納されます。
2. 配列の先頭を指す2つのカーソル-iとを割り当てます。j
3. iとj;の要素を比較します。小さい方を選択してください。値の補助配列をコピーし、カーソルを小さいカーソルの前に移動します。
4. アレイの1つが使い果たされるまで、＃3を繰り返します。次に、残りの要素を使い果たされていないアレイから補助アレイにコピーします。

したがって、この場合、を比較し(3, [1]); ([3], 9); (12, [9]); ([12], 19); ([13], 19); ([17], 19); (--, [19]) ます。分かりますか？どのように比較できますか？(m+n)。各操作を想定していますO(1)。長さの配列のマージプロセス(m+n)はですO(m+n)。

最良の場合、入力として配列をソートします。などでは、マージされる両方のサブアレイは結合する必要があります。ただし、上記の一般的なアルゴリズムを適用します。その場合、min(m,n)要素を比較してコピーする必要があります。max(m,n)次に、要素を補助配列にコピーします。いずれにせよ、あなたはトータル(m+n)オペレーションを持つことになります。