Почему вставка сортировки Θ(n^2) в среднем случае?
Сортировка вставки имеет время выполнения, которое составляет Ω(n) (когда вход отсортирован) и O (n2) (когда вход отсортирован обратно). В среднем он работает за Θ (n2) времени.
Почему это? Почему, например, среднее значение не ближе к O(n log n)?
4 ответа
Чтобы ответить на этот вопрос, давайте сначала определим, как мы можем оценить время выполнения сортировки вставки. Если мы можем найти хорошее математическое выражение для среды выполнения, мы можем затем манипулировать этим выражением, чтобы определить среднее время выполнения.
Ключевое наблюдение, которое нам нужно иметь, заключается в том, что время выполнения сортировки вставки тесно связано с числом инверсий во входном массиве. Инверсия в массиве - это пара элементов A[i] и A[j], которые находятся в неправильном относительном порядке, то есть i Есть одна инверсия: 3 и 2 должны быть переключены. В этом массиве: Есть 6 инверсий: Одним из важных свойств инверсий является то, что отсортированный массив не имеет инверсий, поскольку каждый элемент должен быть меньше, чем все, что идет после него, и больше, чем все, что идет до него. Причиной этого является то, что существует прямая связь между объемом работы, выполненной в сортировке вставки, и количеством инверсий в исходном массиве. Чтобы увидеть это, давайте рассмотрим несколько быстрых псевдокодов для сортировки вставкой: Обычно, при определении общего объема работы, выполняемой такой функцией, мы можем определить максимальный объем работы, выполняемой внутренним циклом, а затем умножить его на количество итераций внешнего цикла. Это даст верхнюю границу, но не обязательно жесткую границу. Лучший способ учесть всю проделанную работу - это признать, что есть два разных источника работы: Этот внешний цикл всегда работает Θ(n). Внутренний цикл, однако, выполняет объем работы, пропорциональный общему количеству перестановок, выполненных за все время выполнения алгоритма. Чтобы увидеть, сколько работы будет выполнять этот цикл, нам нужно определить, сколько всего обменов будет сделано за все итерации алгоритма. Это то место, где приходят инверсии. Обратите внимание, что при выполнении сортировки вставки всегда происходит замена смежных элементов в массиве, и это происходит только в случае замены двух элементов, если они образуют инверсию. Так что же происходит с общим числом инверсий в массиве после того, как мы выполним обмен? Ну, графически, у нас есть это: Здесь X - это часть массива, предшествующая перестановленной паре, а Y - часть массива, которая идет после перестановленной пары. Давайте предположим, что мы поменялись местами A[j] и A[j + 1]. Что происходит с количеством инверсий? Что ж, давайте рассмотрим некоторую произвольную инверсию между двумя элементами. Есть 6 возможностей: Это означает, что после выполнения обмена мы уменьшаем количество инверсий ровно на одну, потому что исчезла только инверсия соседней пары. Это чрезвычайно важно по следующей причине: если мы начнем с инверсий I, каждый своп уменьшит число ровно на единицу. Как только не осталось инверсий, перестановки не выполняются. Поэтому количество свопов равно количеству инверсий! Учитывая это, мы можем точно выразить время выполнения сортировки вставки как Θ(n + I), где I - число инверсий исходного массива. Это соответствует нашим исходным границам времени выполнения - в отсортированном массиве имеется 0 инверсий, и время выполнения равно Θ(n + 0) = Θ(n), а в массиве с обратной сортировкой есть n(n - 1)/2 инверсии, и время выполнения равно Θ (n + n (n-1) / 2) = Θ (n2). Острота! Так что теперь у нас есть супер точный способ анализа времени выполнения сортировки вставки для определенного массива. Давайте посмотрим, как мы можем проанализировать его среднее время выполнения. Для этого нам нужно сделать предположение о распределении входных данных. Поскольку сортировка вставкой является алгоритмом сортировки на основе сравнения, фактические значения входного массива на самом деле не имеют значения; на самом деле имеет значение только их относительное упорядочение. В дальнейшем я собираюсь предположить, что все элементы массива различны, хотя, если это не так, анализ не сильно изменится. Я укажу, где вещи выходят за рамки сценария, когда мы туда доберемся. Чтобы решить эту проблему, мы собираемся ввести группу индикаторных переменных в форме Xij, где Xij - случайная величина, равная 1, если A[i] и A[j] образуют инверсию, и 0 в противном случае. Там будет n(n - 1)/2 из этих переменных, по одной для каждой отдельной пары элементов. Обратите внимание, что эти переменные учитывают каждую возможную инверсию в массиве. Учитывая эти X, мы можем определить новую случайную переменную I, которая равна общему количеству инверсий в массиве. Это будет дано суммой X: I = Σ Xij Нас интересует E[I], ожидаемое количество инверсий в массиве. Используя линейность ожидания, это E [I] = E [Σ Xij] = Σ E [Xij] Так что теперь, если мы можем получить значение E [Xij], мы можем определить ожидаемое количество инверсий и, следовательно, ожидаемое время выполнения! К счастью, поскольку все Xij являются бинарными индикаторными переменными, мы имеем E [Xij] = Pr [Xij = 1] = Pr [A[i] и A[j] - инверсия] Так какова вероятность того, что при произвольном входном массиве без дубликатов A[i] и A[j] являются инверсией? Ну, в половине случаев A[i] будет меньше, чем A[j], а другая половина времени A[i] будет больше, чем A[j]. (Если разрешены дубликаты, есть хитрый дополнительный термин для обработки дубликатов, но мы пока проигнорируем это). Следовательно, вероятность того, что между A[i] и A[j] есть инверсия, равна 1 / 2. Следовательно: E [I] = ΣE [Xij] = Σ (1/2) Поскольку в сумме есть n(n - 1)/2 слагаемых, E [I] = n (n - 1) / 4 = Θ (n2) Итак, в ожидании, будет Θ (n2) инверсий, поэтому в ожидании время выполнения будет Θ (n2 + n) = Θ (n2). Это объясняет, почему в среднем случае сортировки вставок Θ (n2). Надеюсь это поможет!0 1 3 2 4 5
4 1 0 3 2
[---- X ----] A[j] A[j+1] [---- Y ----]
Для забавы я написал программу, которая проверила все комбинации данных для вектора размером n, считая сравнения, и обнаружил, что лучший случай - это n-1 (все отсортировано), а худший - (n*(n-1))/2.
Некоторые результаты для разных n:
n min ave max ave/(min+max) ave/max
2 1 1 1 0.5000
3 2 2.667 3 0.5334
4 3 4.917 6 0.5463
5 4 7.717 10 0.5512
6 5 11.050 15 0.5525
7 6 14.907 21 0.5521
8 7 19.282 28 0.5509
9 8 24.171 36 0.5493
10 9 29.571 45 0.5476
11 10 35.480 55 0.5458
12 11 41.897 66 0.5441
Кажется, что среднее значение следует за минутой ближе, чем за макс.
РЕДАКТИРОВАТЬ: некоторые дополнительные значения
13 12 48.820 78 0.5424
14 13 56.248 91 0.5408
РЕДАКТИРОВАТЬ: значение для 15
15 14 64.182 105 0.5393
РЕДАКТИРОВАТЬ: выбранные более высокие значения
16 15 72.619 120 - 0.6052
32 31 275.942 496 - 0.5563
64 63 1034.772 1953 - 0.5294
128 127 4186.567 8128 - 0.5151
256 255 16569.876 32640 - 0.5077
Недавно я написал программу для вычисления среднего числа сравнений для вставки сортировки для более высоких значений n. Из них я сделал вывод, что при приближении n к бесконечности средний случай приближается к наихудшему, деленному на два.
Давайте посмотрим на программу: Общее представление
Loop : j = 1 to n
{
temp = array[j]
k = j - 1
Loop until : ( k > 0 ) and ( array[k] > temp ) {
array[k+1] = array[k] // shifting one element at a time
k = k - 1
}
array[k+1] = temp
}
Внешний цикл:1 - 2 - 3 - 4 - 5 - .... n
Внутренний цикл: для каждого отдельного элемента будет собственный внутренний цикл.
Возьмем пример массива:[ 3, 2, 9, 1, 2, 6, 5 ] ( average-case )
3 - 2 - 9 - 1 - ..... n
| | | |
no. of loop 1 0 3 (n + 1) / 2
(n+1)/2 -> (multiple cases. so, using median of all probabilities)
Итак, для каждого элемента, который находится ( n ) внутри цикла, выполняется ( (n+1)/2 ) количество раз
-> n(n+1)/2
-> (n2 + n )/2
-> n2 + n // drop constants
-> n2 // drop lower order terms
поэтому даже для среднего случая временная сложность:O(n*n)
Примечание. Все циклы, которые растут пропорционально размеру входных данных, имеют линейную временную сложность O(n). Если вы перебираете только половину массива, это все еще O (n). Помните, что мы опускаем константы, поэтому 1/2 n => O(n).
Большинство алгоритмов имеют средний случай, такой же, как и худший. Чтобы понять, почему это так, назовем O наихудшим случаем, а Ω - наилучшим. Предположительно, O >= Ω при n, переходящем в бесконечность. Для большинства распределений средний случай будет близок к среднему для лучшего и худшего случаев, то есть (O + Ω)/2 = O/2 + Ω/2. Поскольку мы не заботимся о коэффициентах и O >= Ω, это то же самое, что и O.
Очевидно, это упрощение. Существуют распределения времени выполнения, которые искажены так, что предположение о том, что средний случай является средним для наихудшего случая и лучшего случая, недопустимо *. Но это должно дать вам приличную интуицию относительно того, почему это так.
* Как упомянуто templatetypedef в комментариях, некоторыми примерами являются быстрая сортировка / быстрый выбор, поиск BST (если вы не уравновешиваете дерево), поиск в хэш-таблице и симплекс-метод.