algorithm - 挿入ソートの最悪の場合の実行時間

Question

最悪の場合、挿入ソートの実行時間の複雑さが n(n-1)/2 ~ n^2 になるのはなぜですか? 2による除算を強調していますか？

Answer 1

1. 実行時間はそうn(n-1)/2ではありません。各ステップには1台以上のマシンOPが必要です（私が知っているすべてのマシンで）。これが、アルゴリズム分析で通常大きなO表記と「無視」定数を使用する理由です。分析を一般的で、プラットフォームに依存しないようにしたいのです。

2. 挿入ソートは、等差数列の合計であるn(n-1)/2 = O(n^2)ため、 分析されます。最初の反復には1ステップ、次の2ステップには2ステップが必要です。n番目にはnステップが必要なので、等差数列の合計から取得します。1 + 2 + ... + n = n(n-1)/2

Answer 2

これは永遠に閉じられていることは知っていますが、挿入ソートの最悪のシナリオの背後にある数学をブラッシュアップしようとしている他の人のためにこれを追加したかった. n(n-1) / 2 の式を次のように説明している素晴らしいビデオを見つけました。

以下の合計を評価するには:

最初にそれをシリーズ表記にドロップします（sと呼びます）：

s = 1  + 2 + 3 + ... n-3+n-2+n-1

次に、逆に表示します。

s = n-1+n-2+n-3+ ...  3 + 2 + 1

各ペアを追加して s に s を追加すると、次のようになります。n+n+n+....n+n+n

または、言い換えれば2s = n(n-1)、n、n-1 回あり、それを取得するのに 2 つのセットが必要だったからです。

2s = n(n-1)したがって、 になる不等式を解くだけで済みますs = n(n-1) / 2。

Answer 3

アルゴリズムの紹介では、2.1 章で挿入ソートの詳細を説明します。ここでは、挿入ソートのプロセス全体について説明します。

最悪のケースは、サブアレイの逆順の切り替えによって引き起こされます。