Почему в среднем случае вставляется сортировка Θ (n ^ 2)?

Ответ 1

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

Ключевое наблюдение, которое нам нужно иметь, заключается в том, что время выполнения сортировки вставки тесно связано с числом инверсий во входном массиве. Инверсия в массиве представляет собой пару элементов A [i] и A [j], которые находятся в неправильном относительном порядке, то есть я < j, но A [j] А [I]. Например, в этом массиве:

0 1 3 2 4 5

Существует одна инверсия: переключатели 3 и 2 должны переключаться. В этом массиве:

4 1 0 3 2

Есть 6 инверсий:

• 4 и 1
• 4 и 0
• 4 и 3
• 4 и 2
• 1 и 0
• 3 и 2

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

Причиной этого является то, что существует прямая связь между объемом работы, выполняемой в сортировке вставки, и количеством инверсий в исходном массиве. Чтобы увидеть это, рассмотрите несколько быстрых псевдокодов для сортировки вставки:

• Для я = 2.. n: (Предполагая 1-индексацию)
  • Установите j = я - 1.
  • Пока A [j] > A [j + 1]:
    • Переведите A [j] и A [j + 1].
    • Установите j = j - 1.

Обычно, определяя общий объем работы, выполняемой такой функцией, мы можем определить максимальный объем работы, выполняемой внутренним циклом, а затем умножить его на количество итераций внешнего цикла. Это даст верхнюю границу, но не обязательно плотную. Лучший способ объяснить всю проделанную работу - признать, что существуют два разных источника работы:

• Внешний цикл, который насчитывает 2, 3,..., n и
• Внутренний цикл, который выполняет свопы.

Этот внешний цикл всегда работает & Theta; (n). Тем не менее, внутренний цикл выполняет объем работы, который пропорционален общему количеству свопов, выполненных в течение всего времени выполнения алгоритма. Чтобы узнать, сколько работы будет выполняться в этом цикле, нам нужно будет определить, сколько общих свопов производится во всех итерациях алгоритма.

Здесь присутствуют инверсии. Обратите внимание, что при запуске сортировки вставки он всегда меняет смежные элементы в массиве и только заменяет два элемента, если они образуют инверсию. Итак, что происходит с общим числом инверсий в массиве после выполнения обмена? Ну, наглядно, у нас есть следующее:

 [---- X ----] A[j] A[j+1] [---- Y ----]

Здесь X - это часть массива, идущая перед swapped парами, а Y - часть массива, идущего после swapped пары.

Предположим, что мы заменим A [j] и A [j + 1]. Что происходит с количеством инверсий? Итак, рассмотрим произвольную инверсию между двумя элементами. Существует 6 возможностей:

• Оба элемента находятся в X или оба элемента находятся в Y, или один элемент находится в X, а один элемент находится в Y. Тогда инверсия все еще существует, поскольку мы не перемещали ни один из этих элементов.
• Один элемент находится в X или Y, а другой - либо A [j], либо A [j + 1]. Тогда инверсия все еще существует, поскольку относительные упорядочения элементов не изменились, хотя их абсолютные позиции могут иметь.
• Один элемент - A [j], а другой A [j + 1]. Затем инверсия удаляется после обмена.

Это означает, что после выполнения свопа мы уменьшаем количество инверсий точно одним, потому что исчезла только инверсия соседней пары. Это чрезвычайно важно по следующей причине: если мы начнем с я инверсий, каждый своп уменьшит число на один. Как только никаких инверсий не осталось, больше не выполняется свопов. Следовательно, количество свопов равно числу инверсий!

Учитывая это, мы можем точно выразить время выполнения сортировки вставки как & Theta; (n + I), где я - количество инверсий исходного массива. Это соответствует нашим первоначальным границам времени выполнения - в отсортированном массиве есть 0 инверсий, а время выполнения - & Theta; (n + 0) = & Theta; (n), а в массиве с обратной сортировкой - n (n - 1 )/2 инверсии, а время выполнения - & Theta; (n + n (n-1)/2) = & Theta; (n ²). Острота!

Итак, теперь у нас есть сверхточный способ анализа времени выполнения сортировки вставки, заданного конкретным массивом. Посмотрим, как мы можем проанализировать его среднюю продолжительность выполнения. Для этого нам нужно сделать предположение о распределении входных данных. Поскольку сортировка вставки - это алгоритм сортировки на основе сравнения, фактические значения входного массива фактически не имеют значения; на самом деле имеет значение только их относительный порядок. В дальнейшем я буду предполагать, что все элементы массива различны, хотя, если это не так, анализ не изменит все так сильно. Я укажу, куда уходят вещи - script, когда мы доберемся туда.

Чтобы решить эту проблему, мы собираемся ввести кучу индикаторных переменных формы X _ij, где X _ij - случайная величина, которая равна 1, если A [i] и A [j] образуют инверсию и 0 в противном случае. Там будет n (n - 1)/2 этих переменных, по одному для каждой отдельной пары элементов. Обратите внимание, что эти переменные учитывают каждую возможную инверсию в массиве.

Учитывая эти X, мы можем определить новую случайную переменную I, равную общему числу инверсий в массиве. Это будет дано суммой X:

I = & Sigma; X <суб > IJсуб >

Нам интересно E [I], ожидаемое количество инверсий в массиве. Используя линейность ожидания, это

E [I] = E [& Sigma; X _ij] = & Sigma; E [X <суб > IJсуб > ]

Итак, теперь, если мы сможем получить значение E [X _ij], мы можем определить ожидаемое количество инверсий и, следовательно, ожидаемое время выполнения!

К счастью, поскольку все X _ij являются двоичными индикаторными переменными, мы имеем, что

E [X _ij] = Pr [X _ij= 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] = & Sigma; E [X _ij] = & Sigma; (1/2)

Так как в сумме найдется n (n - 1)/2 членов, то это работает на

E [I] = n (n - 1)/4 = & Theta; (n ²)

Итак, в ожидании будут инверсии & Theta; (n ²), поэтому по ожиданию время выполнения будет & Theta; (n ² + n) = & Theta; (п ²). Это объясняет, почему поведение сортировки в среднем случае есть & Theta; (n ²).

Надеюсь, это поможет!

Ответ 2

Для удовольствия я написал программу, которая проходила через все комбинации данных для вектора сравнения совпадений размера 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

EDIT: значение для 15

 15  14    64.182   105        0.5393

EDIT: выбранные более высокие значения

 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. Из этого я сделал вывод, что при приближении п к бесконечности средний случай подходит к наихудшему случаю, деленному на два.

Ответ 3

Большинство алгоритмов имеют средний размер, такой же, как в худшем случае. Чтобы понять, почему это так, позвоните O в худшем случае, а Ω - в лучшем случае. Предположительно, O >= Ω, поскольку n переходит в бесконечность. Для большинства распределений средний случай будет близок к среднему значению наилучшего и худшего - то есть (O + Ω)/2 = O/2 + Ω/2. Поскольку нас не интересуют коэффициенты, а O >= Ω, это то же самое, что и O.

Очевидно, что это упрощение. Существуют распределенные распределения времени, которые искажены так, что предположение о среднем случае, являющемся средним наихудшим случаем и наилучшим случаем, недействительно *. Но это должно дать вам приличную интуицию относительно того, почему это так.

* Как упоминалось в комментариях templatetypedef, некоторые примеры - quicksort/quickselect, поиск BST (если вы не балансируете дерево), поиск в хэш-таблице и метод симплекс.