Поэтому

Т(п) = Х- (т(1) + Т(п - 1) ++ Т(-п ~ ?)) j + 0(га) (8-2)

(слагаемое, соответствующее g = 1, входит дважды). Поскольку Г(1) = 6(1) и Т(га) = 0(п2), имеем

(Т(1) + Т(га - 1)) = (6(1) + 0(п2)) = 0(п).

Поэтому слагаемые Т(1) и Т(га - 1) в первой скобке (8.2) можно включить в 0(га). С учётом этого получаем

п - 1

T(n) = -J2(T(q)+T(n-q)) + e(n).(8.3)

П 9 = 1

Поскольку каждое слагаемое Т(к), где /г = 1,..., га - 1, встречается в сумме дважды, её можно переписать так:

2 п~Х

Т(п) =-J2T(k)+ в(п).(8.4)

п k=i

Решение рекуррентного соотношения

Соотношение (8.4) можно решить, используя метод подстановки. Предположим, что Т(п) anlgn + b, где константы а > 0 и Ь > О пока неизвестны, и попытаемся доказать это по индукции. При п = 1 это верно, если взять достаточно большие а и Ь. При га > 1 имеем

2 n 1

Г(га) = -Г(Л) + е(п)

П к=1

2 =4

-2 (aklgk + b) + e(n) п k=i

2а 4 . . . 26

Е klg к Н--(га - 1) + 6(га).

га fc=i

Ниже мы покажем, что первую сумму можно оценить так:

п-111

klgk -га2 lgra - -га2.(8.5)

к=1

Используя это, получим

ш, . 2а (\ о, 1 Л 26, . Л. .

ТЫ) <: - ( -п2 lg п - -п2 \ + - Ы - 1) + ©Н

ага lg га - -га + 26 + 0(га)

= ага lg га + 6 + О(га) + 6 - -raj ага lg га + 6,

если выбрать а так, чтобы га было больше 0(га)+6. Следовательно, среднее время работы есть О (га lgra).

Доказательство оценки для суммы

Осталось доказать оценку (8.5). Поскольку каждое слагаемое не превышает ralgra, получаем оценку

п-1

k lg к га2 lg га.

fc=i

Для наших целей она не подходит - нам необходима более точная оценка га2 lg га - £7(га2).

Если в предыдущей оценке заменять лишь lg к на lg га, оставив к в неприкосновенности, получим оценку

ЕП 1 га(га - 1)1 2

Hg£;lgra2K =--lg и -га lg га.

fc=ifc=i

Осталось лишь заметить, что заменяя \gk на lgra, мы прибавили по крайней мере по к 1 к каждому слагаемом первой половины суммы (где к га/2), всего примерно (га/2)2/2 = га2/8.

Более формально,

п-1Г™/2!-1п-1

/г lg /г =/г lg /г +/г lg к

к=1к=1к=\п/2]

При к < [га/2] имеем lg к lg(ra/2) = lg га - 1. Поэтому

n-iГ™/2!-1п-1

к lg /г (lg га - 1)/г + lg га/г

fc=lfc=lfc="n/2]

п-1\п/2]-1

11/га \ га

= lgra2- 2 2ПП~ gn~ 2\2~ ) 2

к=1к=1

1 2,1 2

< -га lg га--га

при п 2. Оценка (8.5) доказана.

[Следующий простой вывод оценки для среднего времени работы вероятностного алгоритма быстрой сортировки (для несколько другого варианта алгоритма) предложил Л.А. Левин.

(1)Будем представлять себе сортировку так: есть N камней разного веса и чашечные весы для их сравнения. Мы берём случайный камень и делим всю кучу на три части: легче его, тяжелее его и он сам, после чего (рекурсивный вызов) сортируем первую и вторую части.

(2)Как выбрать случайный камень? Можно считать, что сначала всем камням случайно присваиваются различные ранги (будем считать их числами от 1 до N), и в качестве границы берётся камень минимального ранга (из подлежащих сортировке в данный момент). (Можно проверить, что это равносильно независимым выборам камней на каждом шаге: на первом шаге каждый из камней может быть выбран с равной вероятностью, после такого выбора в каждой из групп все камни также равновероятны и т. д.)

(3)Таким образом, каждый камень характеризуется двумя числами от 1 до W - порядковым номером (в порядке возрастания весов) и рангом. Соответствие между номерами и рангами определяет число операций в процессе сортировки.

(4)Для каждых двух номеров i, j из {1,..., N} через p(i,j) обозначим вероятность того, что камни с этими номерами будут сравниваться друг с другом. Например, p(i, г + 1) = 1, поскольку соседние по весу камни должны быть сравнены обязательно (сравнения с другими камнями их не различают).

(5)Заметим, что p(i, г + 2) = 2/3. В самом деле, сравнения не произойдёт в том и только том случае, когда из трёх камней с номерами г, г + 1 и г + 2 камень г + 1 имеет наименьший ранг. Аналогично, p(i, г + к) = 2/(к + 1) (камни с номерами г и г + к сравниваются, если среди к + 1 камней i, г + 1,..., г + к один из двух крайних имеет наименьший ранг).

(6)Математическое ожидание числа сравнений можно разбить в сумму m(hJ) ожиданий числа сравнений между камнями с номерами г и j. Но поскольку два данных камня сравниваются не более одного раза, m(i,j) = p(i,j). Таким образом, получаем точное выражение для математического ожидания числа сравнений:

(7) Группируя в этой сумме равные члены и вспоминая, что 1 + 1/2 + 1/3 + ... + 1/к = 0(\gk), получаем оценку 0(N\gN) для математического ожидания времени работы быстрой сортировки.

Анализ облегчается тем, что алгоритм разбиения (на три части) более симметричен. Реализация такого способа разбиения также