Вопрос простого алгоритма

Question

Просматривая бесплатный курс MIT Algorithms на iTunesU и я застрял на первой лекции.

Возьмите сортировку вставкой, ее время действительно T (n / 2) в худшем случае (массив / список в обратном порядке)), но говорят, что это тэта н в квадрате.Я бы подумал, что это будет тета н.Я потерял, как они говорят, что это n в квадрате.Я застрял, как они приходят к выводу, что это n в квадрате, Википедия тоже не помогает.Может ли кто-нибудь замолчать дальше?

Answer 1

Вставка-сортировка массива из 4 элементов, которая начинается в обратном порядке:

4 3 2 1

сначала вставьте «4» в правильное положение в массиве длины 1 (т.е. ничего не делайте).

далее, вставьте «3» в правильное положение в массиве длиной 2:

3 4 2 1

(нам пришлось переместить 3 и 4)

далеевставьте «2» в правильное положение в массиве длиной 3:

2 3 4 1

(нам нужно было переместить 2, 3 и 4)

, затем вставить«1»

1 2 3 4

(нам нужно было сдвинуть 1, 2, 3 и 4)

Мы выполнили n шагов, и каждый шаг k требовал перемещения k элементов (илик-1 меняет местами, в зависимости от того, как вы хотите на это смотреть).Сумма k от 1 до n равна Theta (n ^ 2).

В случае простой структуры связанного списка [*] мы можем переместить объект на его место в O (1),но в целом поиск правильного места все еще требует линейного поиска по части уже отсортированных данных, поэтому для общего ввода все равно остается только O (n ^ 2).Базовая сортировка вставки для связанного списка, оказывается, очень хорошо справляется с данными в обратном порядке, потому что она всегда находит правильную позицию вставки немедленно.Таким образом, мы получаем n шагов O (1) каждый для общего времени выполнения O (n) для этих конкретных данных .

Предполагая, что мы все еще выбираем первый несортированный элемент для вставки, и чтомы ищем вперед отсортированную часть списка на каждом шаге, тогда наихудший случай сортировки вставки для списка - это уже отсортированные данные и снова Theta (n ^ 2).

[*] значениеНичего особенного, как список пропуска.

Answer 2

Из Википедия :

В худшем случае вход является массивом отсортировано в обратном порядке. В этом случае каждая итерация внутреннего цикла сканировать и сдвигать весь отсортированный подраздел массива перед вставка следующего элемента. За это сортировка с вставкой в ​​регистр время работы (то есть O (n2)).

Первый цикл перебирает массив / список для сортировки, внутренний цикл перебирает частично отсортированный массив / список. Если он уже отсортирован, вы можете видеть, что каждый раз итерируете до конца отсортированного контейнера.

Вот еще объяснение в псевдо:

for element in unsorted_container
    for current_element in sorted_container
        if element < current_element -> Will never happen since sorted in reverse order.
            InsertBefore(element, current_element)
    if element not inserted
        InsertAtEnd(element) <- Will always execute this part since it will always insert at end.