Анализ метода быстрой сортировки. Информацию о времени выполнения, приведенную вместе с программой Q, нетрудно вывести из закона сохранения Кирхгофа (см. раздел 1.3.3) и из того факта, что все помещенное в стек, в конце концов, оттуда извлекается. Закон Кирхгофа в применении к шагу Q2 показывает, что

Л = 1 + (5 + А") + (5 - 5 + А") + 5 = 25 + 1 + Л" + А". Следовательно, суммарное время реализации алгоритма составляет

24Л + 11В + 4С + 3D + 8Е + 7N + 9S машинных тактов,

(15)

А - число итераций разбиения;

В - число взаимных обменов на шаге Q6;

С - число сравнений, вьшолненных во время разбиения;

D - число случаев, когда Kj-i > Kj в ходе выполнения сортировки (16)

методом простых вставок (шаг Q9); Е - количество инверсий, удаленных в процессе простых вставок; 5 - количество случаев, когда происходит запись в стек.

Проанализировав эти шесть параметров, можно сделать обоснованный выбор значения параметра М, которым определяется "граница" между сортировкой методом простых вставок и методом разделения. Сам по себе анализ также весьма поучителен, поскольку алгоритм довольно сложен. В процессе анализа будут использоваться важные методики, которые читатели, освоившие их, смогут в дальнейшем применять самостоятельно. (Те же, кто не склонны к "разгребанию математических завалов", могут спокойно перевернуть страницы вплоть до формул (25).)

Как и при анализе большинства алгоритмов в этой главе, будем предполагать, что сортируемые ключи различны. В упр. 18 показано, что наличие равных ключей существенно не снижает эффективность алгоритма Q; в действительности присутствие равных ключей, по-видимому, даже способствует ее увеличению. Поскольку метод зависит только от относительного расположения ключей, можно предполагать также, что это просто чиача {1,2,..., Л}, расположенные в некотором порядке.

Справиться с проблемой попробуем, рассмотрев первую же итерацию разбиения, с которой мы впервые встречаемся на шаге Q7. Когда мы доберемся до этой операции, подмассивы Ri... Rj-i и Rj+i... Rn будут содержать записи в случайном порядке, если и в исходной последовательности они располагались в случайном порядке, поскольку относительное положение записей в подмассивах никак не влияет на алгоритм разделения. Таким образом, комбинация последовательных разбиений может быть проанализирована посредством индукции по N. (Это важное замечание, поскольку альтернативные апоритмы, которые не обладают этим свойством, оказываются, в конце концов, существенно более медленными; см. Computing Surveys 6 (1974), 287-289.)

Пусть S - значение первого ключа Ki, и предположим, что ровно t ключей Ку,... ,Ks превосходят s. (Напомню, что сортируемые в наших примерах ключи - целые числа {1,2,..., N}.) Есгш s = 1, то нетрудно видеть, что произойдет во время первой итерации разделения. Шаг Q3 вьтолнится однократно, шаг Q4 - N раз, а шаг Q5 приведет нас к шагу Q7. Таким образом, "взнос" первой итерации в анализируемые параметры будет следующим; А = 1, В = О, С = N + I. Аналогичные, но несколько более сложные рассуждения для случая s > 1 (см. упр. 21) показывают, что взнос первЬй итерации в суммарное время выполнения в общем случае будет составлять

А=1, B = t, C = N + 1 для 1 < s < TV. (17)

К этому необходимо добавить вклады последующих итераций, во время которых упорядочиваются под.массивы из s - 1 и 7V - s элементов соответственно.

Если предположить, что в исходной последовательности записи располагались в случайном порядке, то можно выписать формулы, которыми определяются производящие функции для распределений вероятностей величин А,В,... ,5 (см. упр. 22). Но для простоты рассмотрим здесь только средние значения этих величин А, Bn, , Sn как функции от N. Рассмотрим, например, среднее число сравнений Cn, выполненных в процессе разделения. Если N < М, то См = 0. В противном случае, поскольку любое данное значение s встречается с вероятностью 1/iV, по.лучим

= iV + l + - Ck тяМ>М. (18)

0<*:<JV

Аналогичные формулы имеют место и для остальных величин An, В, D, Ем, Sn (см. упр. 23).

Существует простой способ решения рекуррентных соотношений вида

а;„ = /п + - Хк для п>т. (19)

0<к<п

На первом шаге нужно освободиться от знака суммирования: поскольку (п + 1)а;„+1 = (п+ !)/„+!+2 Хк,

0<к<п

пХп = п/„ + 2 а;*:,

0<к<п

можно вычесть второе равенство из первого, получив

(п + 1)а;„+1 - пХп = дп + 2а;„, где д„ = {п+ l)/„+i - п/„.

Теперь рекуррентная зависимость принимает гораздо более простой вид:

(п + 1)хп+1 = (п + 2)хп + дп для п>т. (20)

Любое рекуррентное соотношение общего вида

OnXn+l = ЬпХп + 9п (21)

можно свести к простой сумме, если умножить обе части на "суммирующий множитель" ОоOi ...а„ 1 /Ьоbi.. .Ьп- Получаем

ао...а„ 1 ао...а„ 1 2/n-i-i = 2/п + с„, где 2/„ =----а;„, с„ = --- дп. (22)

Оо...О„ 1 boOi...bn

Для (20) суммирующий множитель равен просто п!/(п--2)! = l/(n--l)(n-f-2). Таким образом, находим, что простое соотношение

Хп+1 , (П + 1)/п--1 - "/п

- =-7 + ~1-ГТТ7-Г;7Г~ для п > m (23)

п + 2 п + 1 (п-Ь l)(n-f-2)

является следствием соотношения (19).

Если, например, положить /„ = 1/п, то получится неожиданный результат: Хп1{п -f-1) = Хт/{т + 1) при любом п>т. Если положить /„ = п -Ь 1, получится

Хп/{п -Ь 1) = 2/(п -t-1) -f- 2/п -t- • • • -f- 2/(ш -ь 2) -Ь а;„/(т -t- 1) = 2 (Я„+1 - Я+i) + ХтЦт + 1)