マージソートの最悪のケースはいつ発生しますか?
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. 結論
この記事では、マージソートの最悪の時間計算量である。について説明しました。 これは、すべてのマージ操作の左右のサブ配列に代替要素がある場合に発生します。