Инверсия для вставки сортировки!

Question

Этот вопрос я нашел на сайте Wikipedia (я хочу очень хорошо изучить алгоритмы сортировки).В любом случае, это вопрос - не могли бы вы объяснить мне, как я могу это показать?

Упражнение: Показать, что алгоритм вставки сортировки (A) выполняется за время O (n + I), учитывая, что 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] - количество инверсий, вызванных элементом i. Это должно очень легко понять доказательство.