расчет сложности времени для вставки сортировки

Question

Я пытаюсь понять временную сложность сортировки вставок. Я застрял в то время как цикл. Я не могу понять, сколько раз, пока цикл выполняет

InsertionSort(A)
    for j = 2 to A.length
        key = A[j]
        i = j - 1
        while i>0 and A[i]>key
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = key

Я знаю, что цикл for выполняется n + 1 раз, и каждый оператор в цикле выполняется n раз цикл while также выполняется n раз Но что я не понимаю, так это «Сколько раз операторы цикла while выполняются как в худшем, так и в лучшем случае?»

Answer 1

В худшем случае A отсортировано в порядке убывания, что означает, что для j -ой записи внутренний цикл будет выполняться j раз (дать или взять "+1" или "- 1" ...). К счастью, для этого есть формула: как Гаусс, как известно, спонтанно и под принуждением , суммирование всех чисел от 1 до n дает результат n*(n+1)/2.

Поскольку мы заботимся только о сложности, а не о фактических значениях, мы можем оставить постоянные и мультипликативные коэффициенты выключенными и получить O(n^2).

Если не принимать во внимание язык, тот факт, что внутри цикла есть цикл, является сильным показателем для O(n^2), когда счетчик внутренних циклов ограничен линейно - что он здесь.

В лучшем случае, когда A уже отсортировано в порядке возрастания, внутренний цикл будет введен вовсе, а общая сложность составит O(n).

Средний случай сильно зависит от того, как выглядит ваша ожидаемая "неупорядоченность". Например, сортировка будет вести себя очень хорошо, если ваш список в основном всегда уже отсортирован, а таких локальных переключений очень мало.