Глава 2. Сложность в среднем

Каждая из сложностей в среднем как по числу сравнений, так и по числу перемещений для двух вариантов сортировки простыми встав­ками (всего четыре сложности) есть ⁿ + O{n); каждая из сложно­стей в среднем по общему числу сравнений и перемещений для двух вариантов этой сортировки (всего две сложности) есть ⁿ-+O(n).

Можно вспомнить, что в примере 1.4, в котором мы рассматрива­ли для двух вариантов сортировки простыми вставками их сложности в худшем случае по суммарному числу сравнений и перемещений, на­блюдалась непохожая ситуация, чему имеется, повторимся, простое объяснение: в отличие от (6.8), равенство шах(? + т?) = шах £ + шах tj, вообще говоря, места не имеет.

Общая формулировка установленного нами соотношения:

Теорема 6.1. Сложность в среднем некоторого алгоритма по сум­марному числу операций нескольких различных типов равна сумме сложностей в среднем этого алгоритма по числу операций каждого типа в отдельности.

Среди наиболее элементарных сортировок мы пока рассмотрели сложность в среднем только для сортировки простыми вставками. Сразу же можно добавить, что для сортировки выбором ее сложности по числу сравнений в среднем и в худшем случае совпадают, так как число сравнений однозначно определяется длиной n массива. Число сравнений на i-м этапе (i-м просмотре массива) пузырьковой сорти­ровки равно n — i. Не сталкиваясь с большими трудностями, можно показать (см. задачу 38), что математическое ожидание s{n) числа просмотров массива есть

k! kⁿ~^k n —

х—1 ^{k k n} ~^k

2_j ^Г~ • (⁶.⁹)

n!

k=o

Очевидно, что s(n)<n. С другой стороны,

у^ k! kⁿ-^k _ху(n-1)!k_1уk_n + 1 2-1 n! ~~~2-i n! nZj 2 "

k=0 k=0 k=0

Поэтому s(n)^n тг— = —Z-. Мы имеем

2

n-1

2

и s(n) =Θ(n). Из этого следует, что сложность в среднем по числу сравнений пузырьковой сортировки квадратична.

^s{n)<n

§ 7. Пример медленного роста сложности в среднем

53

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

§ 7. Пример медленного роста сложности в среднем в сравнении со сложностью в худшем случае

Следующий пример показывает, что при п —> оо сложность в среднем может расти существенно медленнее, чем сложность в худшем случае.

Пример 7.1. Рассмотрим сложность в среднем f_QS(n) быстрой сор­тировки по числу сравнений. Будем считать, что в качестве разбиваю­щего элемента всегда выбирается первый элемент сортируемой части массива. Введем случайную величину Е,_п на П„, равную числу срав­нений быстрой сортировки для а е П_п (в этом смысле £_п(а) = C^T_qs{a)).

Имеем

f_QS(n) = E?_n = ^y J] £_п(а).

Введем разложение

^Пп=^Кп +^Кп+---+^Кп>

где событию К¹_п принадлежат все те перестановки длины п, для кото­рых разбивающий элемент занимает i-ю позицию после завершения разбиения. В силу предложения 6.1(i) (видно, что К[ = FJ;¹ — событие состоит в том, что 1-й элемент перестановки равен i), получаем

P_п(7ф = -, i = l,2,..., п.

Разбиение перестановки а (первый этап быстрой сортировки) порож­дает две перестановки а'еП_- и а"еП_-. В соответствии с этим определим еще две случайные величины

£'_п(а) = ^(аО, Оа) = Cn-ifa"),

где i — номер позиции, которую занимает разбивающий элемент по­сле разбиения. По формуле полного математического ожидания

п п

E?_п=2 E(?„|1фP_паф=^(п -1 + E(?;Х) + E(?;х))±;

1=1 1=1

54