algorithm - 挿入ソートの反転！

Question

これはウィキペディアのサイトで見つけた質問です(ソートアルゴリズムをよく学びたいです)。とにかく、これは質問です - どうすればそれを示すことができるか説明してもらえますか?

練習問題: I が配列 A の反転数であるとすると、Algorithm Insertion Sort (A) が時間 O(n + I) で実行されることを示します。

Answer 1

このページImplementationのとAnalysisのセクションを見てください。

そこに提示されているアルゴリズムを考えてみましょう：

private static void insertionsort()
{
    int i, j, t;
    for (i=1; i<n; i++)
    {
        j=i;
        t=a[j];
        while (j>0 && a[j-1]>t)
        {
            a[j]=a[j-1];
            j--;
        }
        a[j]=t;
    }
}

while ループがv[i]繰り返し実行されることに注意してください。ここで、v[i]は element によって引き起こされる反転の回数ですi。これにより、そこでの証明が非常に理解しやすくなるはずです。