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

П

Y, у = In n + 0(1)

i =l

сложность T^in) можно записать в виде

Т}₁(п)=⁽" ^{+ 4)(}"-¹⁾-1пп + 0(1) (6.6)

[К 4 и, проще, в виде

Г; (п) = ^+0(п). (6.7)

п_² 4

Таким образом, сложность в среднем по числу сравнений первого ва­рианта сортировки простыми вставками, как и сложность в худшем случае, есть величина порядка п², но при больших п первая слож­ность примерно вдвое меньше второй. Формула (6.6) показывает, что, вообще говоря, вопреки бытовым представлениям сложность в сред­нем не есть среднее арифметическое затрат в худшем и в лучшем слу­чае: такое среднее арифметическое для рассматриваемой сортировки является рациональной функцией от п и не может описываться этой формулой, содержащей логарифм.

Если рассмотреть вместо случайных величин Е}_п, £²,..., Е^^х слу­чайные величины г\\, г;²,..., rf_n ^_1, соответствующим образом отража­ющие затраты исследуемой сортировки по числу перемещений, то, очевидно, будем иметь

^ *S r,j, *S?j, + 1,

i = 1, 2,..., n - 1. Поэтому сложность в среднем по числу перемещений

п² тоже есть — +0(п). Нетрудно показать, что и сложности в среднем

по числу сравнений и числу перемещений второго варианта сорти­ровки простыми вставками равны — + 0{п). Сложность в среднем по суммарному числу сравнений и перемещений и для первого, и для второго варианта есть ^+0(п), поскольку для любых случайных величин Е,,г), определенных на каком-либо вероятностном простран­стве, выполняется

Е(? + т)) = Е? + Ет). (6.8)

Глава 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! n Zj 2 "

k =0 k =0 k =0

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

n -1

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

^s{n)<n

§ 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,..., п.

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

£'_п(а) = ^(аО, Оа) = C n - i f a "),

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

Дата добавления: 2014-01-11