1. 概要

マージソートは、問題をサブ問題に分割する最も一般的なソートアルゴリズムの1つです。 各サブ問題の解決策が準備できたら、サブ問題の結果を「マージ」して主な問題を解決します。

このチュートリアルでは、時間計算量（別名 マージソートのBigO ）と、最悪の場合の原因となる組み合わせ。

2. マージソートの2つのステップ

アルゴリズムには2つのステップがあります。

ステップ1は「分割」です。ここでは、サブ配列のサイズが1になる段階に到達するまで、アルゴリズムが配列を2つに繰り返し分割します。

上記の配列（16個の要素と= 16）の除算関数の時間計算量は8 + 4 + 2 + 1=15です。 つまり、配列のサイズがの場合、マージソートの除算関数の時間計算量は（/ 2 + / 4…1まで）であり、これもです。

アルゴリズムのステップ2には、「マージ+ソート」が含まれています。この場合、2つのサブ配列がマージされ、サブアレイの各ペアからソートされた配列が作成されます。 最後のステップでは、元の配列の2つの半分がマージされ、完全な配列が並べ替えられます。

このアルゴリズムは時間をループし、すべてのループの時間計算量はです。したがって、関数全体の時間計算量はです。

アルゴリズム全体の複雑さは、2つのステップ の複雑さの合計です。これは、マージソートの最悪のケースでもあります。

3. マージソートの時間計算量の最悪のケース

マージとソートの実行中に比較の数を減らすことができれば、時間の複雑さを改善できます。 ただし、マージ操作に関係する左右のサブ配列に、並べ替えられた配列の代替要素がある場合、最適化はできません。 たとえば、左と右のサブ配列がそれぞれ{1,3,5,7}と{2,4,6,8}の場合、両方の配列のすべての要素を少なくとも1回比較する必要があります。これにより、結果が得られます。最悪の時間計算量で。

アルゴリズムのプロセスフローは次のようになります。

配列{1,2,3,4,5,6,7,8}でこのアルゴリズムを使用すると、次の組み合わせとして{5,1,7,3,6,2,8,4}が見つかります。以下に示すように、マージソートの複雑さが最悪になります。

4. 結論

この記事では、マージソートの最悪の時間計算量である。について説明しました。 これは、すべてのマージ操作の左右のサブ配列に代替要素がある場合に発生します。