Временная сложность сортировки вставками

Может ли кто-нибудь объяснить, почему сортировка вставками имеет временную сложность Θ(n²)?

Я совершенно уверен, что понимаю временную сложность как концепцию, но я не совсем понимаю, как применить ее к этому алгоритму сортировки. Должен ли я просто искать математические доказательства, чтобы найти этот ответ?


sorting time-complexity insertion-sort
person Drake Drinnon    schedule 07.11.2013    source источник
comment
Самостоятельное написание математического доказательства только укрепит ваше понимание. Часто самые сложные части — это настройка. Например, сначала вы должны уточнить, нужна ли вам сложность алгоритма в наихудшем случае или что-то еще (например, сложность в среднем). Во-вторых, вы хотите определить, что считается реальной операцией в вашем анализе. Для алгоритмов сортировки на основе сравнения, таких как сортировка вставками, обычно мы определяем, что сравнения занимают O(1) времени, а обмены занимают O(1) времени. Вы можете обосновать для себя, является ли это действительной метрикой. С этого момента просто применяйте определение   -  person rliu    schedule 07.11.2013

Ответы (3)


arrow_upward
11
arrow_downward

В среднем каждая вставка должна пройти половину текущего отсортированного списка, выполняя одно сравнение за шаг. Список каждый раз увеличивается на единицу.

Таким образом, начиная со списка длины 1 и вставляя первый элемент, чтобы получить список длины 2, мы имеем в среднем обход 0,5 (0 или 1) места. Остальные 1,5 (0, 1 или 2 место), 2,5, 3,5,..., n-0,5 для списка длины n+1.

Это, по простой алгебре, 1 + 2 + 3 + ... + n - n * .5 = (n (n + 1) - n)/2 = n ^ 2 / 2 = O (n ^ 2)

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

В лучшем случае вы найдете точку вставки в верхнем элементе с одним сравнением, поэтому у вас есть 1+1+1+ (n раз) = O(n).

person Gene    schedule 07.11.2013
comment
Хороший ответ. Я просто хотел бы добавить 2 вещи: 1. Хороший набор заметок Питера Крамминса существует здесь catonmat.net/blog/mit-introduction-to-algorithms-part-one 2. В худшем случае у нас есть самые коварные входные данные. То есть список полностью отсортирован в обратном порядке. Таким образом, каждая итерация будет проходить «j» обходов. Формула расчета времени T(n) = sum(\theta(j)) для j = 2:n. (при условии, что список индексируется с 1) - person hAcKnRoCk; 27.12.2013
comment
@MhAcKN Точно. Вот почему реализации сортировки больших данных уделяют пристальное внимание плохим случаям. Вы обычно (и это очень грубое эмпирическое правило) не хотите использовать сортировку вставками, если данные могут вырасти до более чем сотни или около того. - person Gene; 27.12.2013
comment
Спасибо Гена. Теоретически вычислял временную сложность и ломал голову над тем, что на самом деле измеряет тета в асимптотических обозначениях. Поэтому я полагаю, что он определяет количество необходимых обходов. Просто небольшое сомнение, что произойдет, если операторы › или = будут реализованы более эффективным образом в одном из видов вставки. Тогда как мы изменим нотацию Theta(), чтобы отразить это. или я слишком много думаю? - person hAcKnRoCk; 27.12.2013
comment
@MhAcKN Вы правы, когда беспокоитесь о деталях. \O, \Omega, \Theta и др. касаются отношений между функциями, а не временем выполнения. Когда мы используем их для описания времени выполнения, замалчивание характера ввода и других небрежностей приводит к проблемам. В большинстве характеристик алгоритмов сортировки функция, описываемая с помощью \O, \Theta и т. д., представляет собой количество сравнений и количество входных данных для данных, вызывающих наихудшую производительность. Таким образом, время выполнения сравнения уже было исключено из анализа. С этим определением сортировка вставками (как вы описываете) \ Theta (n ^ 2). - person Gene; 28.12.2013
comment
В лучшем случае на единицу меньше, чем N: в простейшем случае требуется одно сравнение для N=2, два для N=3 и так далее. Для наихудшего случая количество сравнений равно N*(N-1)/2: в простейшем случае требуется одно сравнение для N=2, три для N=3 (1+2), шесть для N=4 (1 +2+3) и так далее. - person Olof Forshell; 11.09.2015
comment
@OlofForshell Что ж, -1 зависит от деталей реализации. При использовании сравнения индексов для остановки поиска точки вставки выполняется N-1 сравнение ключей и N сравнений индексов. При использовании дозорного выполняется только N ключевых сравнений. - person Gene; 16.09.2015

arrow_upward
1
arrow_downward

Это применимо только к массивам/спискам, то есть к структурам с O(n) временем для вставки/удаления. Для других структур данных он может быть другим. Например, для скиплистов это будет O(n * log(n)), потому что бинарный поиск возможен за O(log(n)) в скиплисте, но вставка/удаление будет постоянной.

person vladich    schedule 03.03.2017

arrow_upward
1
arrow_downward

В худшем случае временная сложность алгоритма Сортировка вставками составляет O(n^2). Худший случай сортировки вставками возникает, когда элементы в массиве уже хранятся в порядке убывания, а вы хотите отсортировать массив в порядке возрастания.

Предположим, у вас есть массив

Step 1 => | 4 | 3 | 2 | 1 | No. of comparisons = 1  |  No. of movements = 1 
Step 2 => | 3 | 4 | 2 | 1 | No. of comparisons = 2  |  No. of movements = 2
Step 3 => | 2 | 3 | 4 | 1 | No. of comparisons = 3  |  No. of movements = 3
Step 4 => | 1 | 2 | 3 | 4 | No. of comparisons = 4  |  No. of movements = 4

T(n) = 2 + 4 + 6 + 8 + ---------- + 2(n-1)

T(n) = 2 * ( 1 + 2 + 3 + 4 + -------- + (n-1))

T(n) = 2 * (n(n-1))/2

T(n) = O(n^2)

person Akshay    schedule 18.04.2019