27

挿入ソートの実行時間は、Ω(n) (入力がソートされる場合) および O(n 2 ) (入力が逆ソートされる場合) です。平均して、Θ(n 2 ) 時間で実行されます。

どうしてこれなの？たとえば、平均ケースが O(n log n) に近くないのはなぜですか?

4

3 に答える 3

50

この質問に答えるために、まず、挿入ソートの実行時間を評価する方法を決定しましょう。実行時間の適切な数式を見つけることができれば、その式を操作して平均実行時間を決定できます。

必要な重要な観察事項は、挿入ソートの実行時間は、入力配列の反転数と密接に関連しているということです。配列の反転とは、相対順序が間違っている A[i] と A[j] のペアのことです。つまり、i < j ですが、A[j] < A[i] です。たとえば、この配列では次のようになります。

0 1 3 2 4 5

反転が 1 つあります。3 と 2 を入れ替える必要があります。この配列では:

4 1 0 3 2

6 つの反転があります。

  • 4と1
  • 4 と 0
  • 4と3
  • 4と2
  • 1と0
  • 3と2

反転の重要な特性の 1 つは、ソートされた配列に反転がないことです。これは、すべての要素が、その後にあるすべての要素よりも小さく、前にあるすべての要素よりも大きくなければならないためです。

これが重要な理由は、挿入ソートで実行される作業量と元の配列の反転数との間に直接的な関係があるためです。これを確認するために、挿入ソートの簡単な擬似コードを確認してみましょう。

  • i = 2 .. n の場合: (1 インデックスを仮定)
    • j = i - 1 を設定します。
    • A[j] > A[j + 1] の場合:
      • A[j] と A[j + 1] を入れ替えます。
      • j = j - 1 に設定します。

通常、このような関数によって実行される作業の合計量を決定する場合、内側のループによって実行される作業の最大量を決定し、それを外側のループの反復回数で乗算します。これにより上限が得られますが、必ずしも厳密な境界ではありません。完了した作業の合計を説明するより良い方法は、作業には 2 つの異なるソースがあることを認識することです。

  • 2、3、...、n、および
  • スワップを実行する内側のループ。

その外側のループは常に Θ(n) の作業を行います。ただし、内側のループは、アルゴリズムのランタイム全体で行われるスワップの総数に比例する量の作業を行います。ループがどれだけの作業を行うかを確認するには、アルゴリズムのすべての反復で行われるスワップの合計数を決定する必要があります。

これが反転の出番です。挿入ソートが実行されると、常に配列内の隣接する要素が交換され、2 つの要素が反転を形成する場合にのみ交換されることに注意してください。では、スワップを実行した後、配列内の反転の総数はどうなるでしょうか? さて、グラフィカルに、これがあります：

 [---- X ----] A[j] A[j+1] [---- Y ----]

ここで、X はスワップされたペアの前にある配列の一部であり、Y はスワップされたペアの後にある配列の一部です。

A[j] と A[j+1] を交換するとします。反転の数はどうなりますか? さて、2 つの要素間の任意の反転を考えてみましょう。6 つの可能性があります。

  • 両方の要素が X にある、または両方の要素が Y にある、または 1 つの要素が X にあり、1 つの要素が Y にある。これらの要素を移動しなかったため、反転はまだそこにあります。
  • 一方の要素は X または Y にあり、もう一方は A[j] または A[j+1] のいずれかです。要素の絶対位置が変更された可能性があっても、要素の相対的な順序は変更されていないため、反転は依然として存在します。
  • 1 つの要素は A[j] で、もう 1 つの要素は A[j+1] です。次に、スワップ後に反転が削除されます。

これは、スワップを実行した後、隣接するペアの反転のみが消失したため、反転の数をちょうど 1 つ減らすことを意味します。これは、次の理由から非常に重要です。I 反転から開始すると、スワップごとに数値がちょうど 1 ずつ減少します。反転がなくなると、それ以上スワップは実行されません。したがって、スワップの数は反転の数と同じです!

これにより、挿入ソートの実行時間を Θ(n + I) として正確に表すことができます。ここで、I は元の配列の反転数です。これは、元の実行時の境界と一致します。並べ替えられた配列では、0 回の反転があり、実行時間は Θ(n + 0) = Θ(n) であり、逆に並べ替えられた配列では、n(n - 1)/ です。 2 回の反転で、実行時間は Θ(n + n(n-1)/2) = Θ(n 2 ) です。気の利いた！

これで、特定の配列を指定して挿入ソートの実行時間を分析する非常に正確な方法が得られました。平均実行時間を分析する方法を見てみましょう。これを行うには、入力の分布について仮定する必要があります。挿入ソートは比較ベースのソート アルゴリズムであるため、入力配列の実際の値は実際には重要ではありません。それらの相対的な順序だけが実際に重要です。以下では、すべての配列要素が別個のものであると仮定しますが、そうでない場合、分析はそれほど変化しません。そこに着いたら、どこが台本から外れているかを指摘します。

この問題を解決するために、X ijの形式の一連の指標変数を導入します。ここで、X ijは確率変数であり、A[i] と A[j] が反転を形成する場合は 1 になり、それ以外の場合は 0 になります。これらの変数は n(n - 1)/2 個あり、要素の異なるペアごとに 1 つずつあります。これらの変数は、配列内で考えられる各反転を考慮していることに注意してください。

これらの X が与えられると、配列内の反転の総数に等しい新しい確率変数 I を定義できます。これは、X の合計によって与えられます。

私 = Σ X ij

配列内の予想反転数である E[I] に関心があります。期待値の線形性を使用すると、これは

E[I] = E[Σ X ij ] = Σ E[X ij ]

したがって、E[X ij ]の値を取得できれば、予想される反転数、したがって予想される実行時間を決定できます。

幸いなことに、すべての X ijはバイナリ指標変数であるため、次のようになります。

E[X ij ] = Pr[X ij = 1] = Pr[A[i] と A[j] は反転]

では、重複のないランダムな入力配列が与えられた場合、A[i] と A[j] が反転である確率はどうなるでしょうか? 半分の時間では、A[i] は A[j] よりも小さくなり、残りの半分の時間では A[i] は A[j] よりも大きくなります。(重複が許可されている場合は、重複を処理するための卑劣な用語が追加されていますが、ここでは無視します)。したがって、A[i] と A[j] の間に反転がある確率は 1 / 2 です。したがって、次のようになります。

E[I] = ΣE[X ij ] = Σ (1 / 2)

合計には n(n - 1)/2 項があるため、これは次のようになります。

E[I] = n(n - 1) / 4 = Θ(n 2 )

したがって、期待どおりに Θ(n 2 ) の反転があるため、期待どおりの実行時間は Θ(n 2 + n) = Θ(n 2 )になります。これは、挿入ソートの平均的なケースの動作が Θ(n 2 )である理由を説明しています。

お役に立てれば！

于 2013-06-11T23:12:35.670 に答える