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

после очевидного упрощения имеем

п

E?_п = п - 1 + i 2(E(?'_П|^) + E(?;Х)).

Займемся вычислением E(?'_п|*ф и EСС^Лф, IsSisSn. Мы имеем разложение

Г\ —= / Ст

где событие G|,'^p определено так же, как в предложении 6.1(H), — это событие состоит в том, что относительный порядок элементов пере­становки, имеющих значения, меньшие i, совпадает с порядком эле­ментов перестановки р длины i - 1; имеем

E(?;Х)= 2 E(?n|Gn^P)Pn(GJ;^p).

рбП_-

Когда выполняется G^lf, значение £'_п(а) равно ^(р). Принимая до­полнительно во внимание предложение 6.1(H), имеем

E(?Ж)= £ ?_г-₁(р)_-Т5Г = E?_г-₁. Аналогично можно показать, что

здесь надо рассмотреть событие, которое состоит в том, что относи­тельный порядок элементов перестановки, имеющих значения, боль­шие i, совпадает с порядком элементов перестановки p длины n-i. В итоге получаем

1

п

1=1

E?_п = п -1 + - УсE?,! + E?_п-о.

Так как £ E?_г-₁ = £ E?_п-г= £ E?_fc, то

i=l i=l fc=0

2 "

n

k=0

E?_n = n - 1 + - У E?_fc. (7.1)

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

Таким образом, для Гд₅(п) = Е£_п мы имеем соотношение

п-1

f_QS(n) = n-l + !^?_QS(fc), (7.2)

fc=0

f_QS(0) = 0. Домножение обеих частей равенства (7.2) на п дает

п-1

nf_QS(n) = n(n-l)+2^?_QS(fc).

fc=0

При п>0 имеем для п-1:

л-2

(п - l)f_QS(n - 1) = (п - 1)(п - 2) + 2^ f_QS(fc).

fc=0

Вычитая почленно последнее равенство из предпоследнего, получаем

nf_QS(n) - (п - l)f_QS(n - 1) = 2(п - 1) + 2f_QS(n - 1),

т. е.

nf_QS(n) - (n + l)f_QS(n - 1) = 2(п - 1).

Делим последнее равенство на п(п + 1) и переходим к новой неиз­вестной функции tin) = ^£:

t(n)-t(n-l) = 2 ""* t(0) = 0.

Решением любого уравнения вида t(n) - t{n - 1) = <р(п) при функции <р, определенной для всех п ^ п₀, является t(n) = <р(_По) + £ <р(к),

к=п₀+1

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

п п п

t(n) = 2V -4^-= 2 У Л-2У ттг—^- (7.3)

Z_ik(k + l) Z_ik+l Z-tk(k + l) ^у

fc=i fc=i fc=i

Мы имеем V -A-= inn+ 0(1); с другой стороны, V —Ц-= 0(1),

поскольку ряд f] * сходится. Таким образом, t(n) = 21nn + 0(l);

fc=i ^ ' отсюда

f_QS(n) = (n + l)t(n) = 2n In п + 0(п). (7.4)

56

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

В то же время, сложность в худшем случае Tд₅(n) есть величина по­рядка n² (см. задачу 10).

Число перемещений, требуемое быстрой сортировкой для кон­кретного массива, не превосходит числа сравнений, домноженного на некоторую небольшую константу, откуда сложность в среднем T' (n) по числу перемещений элементов допускает оценку T'(n) = = O{n log n).

Сложность в среднем быстрой сортировки как по числу сравнений, так и по числу перемещений элементов допускает оценку O(nlogn).

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

Нелишне заметить, что если быстрая сортировка реализована как рекурсивная процедура, то при ее выполнении будет использован стек отложенных заданий. Рекурсию в данном случае можно органи­зовать так, что в стек будут попадать лишь значения индексов некото­рых элементов, но не сами элементы массива. В соответствии с опре­делением алгебраической сложности объем такого стека не влияет на пространственную сложность.

Если выйти за рамки алгебраической сложности, то размер стека отложенных заданий становится важной характеристикой алгорит­ма. Мы рассмотрим размер этого стека для некоторого типа рекур­сивных сортировок, к которому относится не только быстрая сорти­ровка, но и, например, рекурсивный вариант сортировки слияниями. Пусть сортировка организована так, что на первом ее этапе мы, сле­дуя некоторому принципу, выделяем из массива x длины n > 1 две какие-то его непересекающиеся части x', x", длина каждой из кото­рых меньше n. На втором этапе эти части сортируются рекурсивно с помощью той же сортировки, и на третьем, заключительном, этапе, исходя из результатов сортировки x' и x", массив x представляется, уже без рекурсий, в упорядоченном виде. Если n = О или n = 1, то никаких действий над элементами массива не производится.

Будем использовать для такого рода сортировок рабочее название «бинарные рекурсивные сортировки». Возникающие при выполнении таких сортировок рекурсии реализуются с помощью стека отложен­ных заданий.

Теорема 7.1. Если некоторая бинарная рекурсивная сортировка такова, что первым из x', x" сортируется массив, имеющий не пре-