Al в a, которое содержит ao, ai, a-t+i- Обратите внимание на то, что Л, как и только что подросшее В, есть дерево турнира с выбыванием, в котором 2*""*"+ листьев.) Сравните 6 с ak-t+j+i, затем сравните победителя с а*; (++2 и так до тех пор, пока не будет найдено с = тах(6,afc (+j i,... ,a)t-i). Случай 1, 6 < с: вывести а и поменять В с Л. Случай 2, 6 = с и 6 < а: вывести а и поменять В с А. Случай 3, 6 = с и 6 > а: вывести 6. После отработки этих трех случаев мы останемся с деревьями Аи В (возможно, новыми), в которых победитель В только что ушел на выход. Удалите этот элемент из В и замените его элементом -оо, выполнив все сравнения, необходимые для восстановления структуры дерева (как в методе выбора из дерева). Этим завершится шаг j.

На шаге О выполняется 2* - 1 + 2*"*"" - 1 сравнений, а на шаге t выполняется одно. На каждом из шагов 1, 2, ..., t - 1 выполняется не более fe - 1 сравнений, кроме случая 2, когда их может быть к. Но если только возникает случай 2, мы сохраним одно сравнение на следующий раз для случая 1 или случая 2, поскольку ао тогда окажется равным -оо. Таким образом, суммарно на шагах от 1 до < - 1 выполняется не более (t - l)(fc - 1) + 1 сравнений.

Как следует из результатов упр. 3, имеем Wt{n) < п + (t - l)(fc - l) для всех п < 2* + 2*+", если к >t >2. Если п > 2* + < - 2, результаты упр. 4 говорят, что Wt{n) > n - t+ rig(2* + t - 2)-], a это равно n-t + {t-l)k + l, если t > 3. Таким образом, данный метод оптимален при 2* + < - 2 < п < 2* + 2*+", если fc > t > 3 (а также для некоторых меньших значений п, если t больше).

Аналогичный метод, в котором используются резервные элементы вместо - оо при перестройке В в конце шагов 1, ..., t - 2, доказывает, что Vt(n) <n + {t - l)(fc - 1), когда n < 2*" + 2*"*"" + t - 2 и к >t > 3 (см. доказательство формулы (11)). [См. J. Algorithms 5 (1984), 557-578.]

22. В общем случае, если 2"" • 2* < п + 2 -1 < (2 + 1) • 2* и « < 2 < 2t, такая процедара с t + 1 деревьями с выбыванием размером 2* использует на [(t - l)/2j сравнений меньше, чем (11), так как, по крайней мере, столько сравнений, примененных в (ii) для нахождения минимума, могут быть вновь использованы в (iii).

23. Как следует из (15), количество Vfn/2] {п)/п ограничено снизу значением 2 при п -> оо; но в работе D. Dor, Ph. D. thesis, Tel Aviv University, 1995, показано, что в действительности нижняя граница значительно выше 2. Дор и Ю. Звик (U. Zwick) также нашли верхнюю границу, которая оказалась равной 2.942 [SODA 6 (1995), 28-37]; они доказали, что асимптота для верхней оценки есть

Va„(n) < (l-halgi-hO(aloglogi))n,

что не очень отличается от (15), если а достаточно мало [Combinatorica 16 (1996), 41-58].

24. Поскольку Wt{n) = n+0(t logn), как следует из выражения (6), утверждение, которое содержится в указании, определенно, справедливо, если t < Vn/Inn. Предположим, что это утверждение выполняется для п, и пусть и я v имеют ранги t = [t - \/tlnn\ и t+ = [t + Vtlnn] среди первых n из расположенных в случайном порядке 2п элементов. (Наименьший элемент имеет ранг 1.) Сравните другие п элементов спи сравните те из них, которые меньше v, также с и. Вероятность ps того, что элемент х ранга t в первых п имеет ранг S среди всех, равна {t-DCn-t)/Сп) Среднее значение s есть E*Ps = гГ*5 среднее число элементов < х; следовательно, среднее число сравнений с и равно {+1)+ - t + 0(пlog п)2. Пусть и и V имеют ранги s- и s+ среди всех 2п элементов и пусть Г = [2t - y/2t\n2n\, Т+ = [2t + л/2* In 2п ]. Если s- <Т- из+> Т+, можно отыскать элементы рангов Г и Г+ посредством выбора s+ - s 4-1 элементов между и и v. Докажем, что очень маловероятно, чтобы оказалось s- > Г или s < Г - 2\/nlnn, или s+ < Т+, или s+ >

Г+ + 2Vn\nn\ таким образом, почти всегда будет достаточно 0(пlog п) дополнительных сравнений. Из указания следует индукция по п, если мы сможем показать, что "очень маловероятно" означает "с вероятностью 0(п"") для всех достаточно больших п".

Обратите внимание, что Ps+i/Ps = s{n - s + t)/{s + 1 - t){2n - s) уменьшается no мере того, как s увеличивается от < до n + t и это отношение < 1 тогда и только тогда, когда S > 2n(t-l)/(n-l); оно < 1- icn~ + 0(n"), когда s = Цс) = 2t + ct(n-t)/n. Таким образом, вероятность того, что s > s(c), равна < 2c~npg(c){l + 0(п~)). Аналогично Ps-i/ps < 1 - fcn-/ - 0(n-), если s = s(c) = 2t - 1 - c(t - l)(n + 1 - t)/n так что s < s{c) с вероятностью < 2с~прф{1 + 0(n")). В тех случаях, которые нас интересуют, подходящие значения с есть > .55n(lnn)t"(n-для всех больших n, а аппроксимация Стирлинга дает, что рс) и Ps(c) равны

0(n/=s-/=(2n - s)-i/=) exp(-2sc7n - tf/n - 2(2n - 8)сЧУп)

< 0{Г exp(-4t(n - 0c7n)) < 0(Г/=n-=).

Это подтверждает, что вероятность 0(п" (log п)) действительно очень мала. [Аналогичная схема имеется и в САСМ 18 (1975), 165-172, но представленный в этой работе анализ некорректен.]

25. Имея заданный алгоритм выбора и перестановку тг множества {1,... ,п}, организуем для каждой г-й перестановки отдельный счет (аккумулятор). После каждого сравнения тг; : Trj добавим 1 на счет тг;, если тг; -t > [tTj если же тг,- -< = Trj - tj, отнесем по на счет обеих. Отнесение на счет тг; называется полезным, если тг; < тг < t или тг; > тг > t; в противном случае оно бесполезно. Пусть Xk - итоговый счет для к. Тогда общее число сравнений рав1ю xi + -\- Хп. Очевидно, что xt = 0; но xj: > 1 для всех к ф t, поскольку каждый элемент, отличный от t. имеет полезный счет. Докажем, что YiXt+k + EiXt-k > 3 при О <к <t.

Пусть Ак(тт) = [первое добавление на счет t + к было бесполезным]. Тогда Ак(тт) -

1 - А-к{т), где тг подобно тг, но элементы {t - к,... ,t + к - l,t + к) заменены в нем соответственно элементами {t~k + l,..., t+k, t - k). Таким образом, Е At -Ь Е Ак = 1.

Пусть Вк{т) = [первое добавление на счет п t + к, и t - к было и t + к получило второе добавление на счет прежде, чем t - к]. Пусть также Ск{тт) = [xt+k > 2 -- Ак]. Тогда Bkir) < С*;(тг ), где тг подобно тг, но с заменой элементов (t - k,t - к + 1,... ,t + к - 1) элементами {t+k-l,t - k,. .., t+k -2). Аналогично В )с(тг) < С-к(п"), где тг" получено из тг посредством замены (t-k+1,... , t+k-1, t+k) элементами (t-k+2,..., t+k, t-k+1). Отсюда следует, что EBfc < ECt иЕВ-к < EC-k.

Докс1зательство завершается выводом, что xt-k + xt+k > 2 + Ак + А-к - Вк - В-к + Ск + С-к- [Дальнейшие результаты приводятся в JACM 36 (1989), 270-279.]

Верхняя оценка в (17) имеет также соответствующую нижнюю оценку: Эндрю и Фрэнсис Яо доказали, что Vt{n) > п + t(lnlnn - \nt - 9) при « > 1 и п > (8t)* [см. SICOMP 11 (1982), 428-447].

26. (а) Обозначим вершины компонентов двух типов через о; 6 < с. Соперник поступает следующим образом при неизбыточных сравнениях. Случай 1, о : а: принять произвольное решение. Случай 2, х : 6: сказать, что х > 6; все последующие сравнения у : Ь с этим конкретным 6 будут иметь результат у > Ь, в противном случае сравнения выбираются соперником для Ut{n - 1), что приводит в общей сложности к > 2 4- Ut(n - 1) сравнениям. Это снижение будем для краткости выражать так: "пусть 6 = min; 2 + Ut(n-iyi Случай 3, X : с: пусть с = max; 2 + Ut-\(n - 1).

(b) Обозначим новые типы вершин di, di < е; f < д < h > i. Случай I, а : а или с : с: произвольное решение. Случай 2, а : с: сказать, что а < с. Случай 3, х : 6: пусть Ь - min;

2 + Ut{n - 1). Случай 4, х : d: пусть d - min; 2 + Ut{n - 1). Случай 5, х : е: пусть е - max;

3 + Ut-i(n - 1). Случай б, X : /: пусть / = min; 2 + Ut(n - 1). Случай 7, х : д: пусть / и р = min; 3 + Ut{n - 2). Случай 8, х : h: пусть h = шах; 3 + Ut-i{n - 1). Случай 9, х : i: пусть i = min; 2 + Ut(n - 1).

(с) Поскольку при t = \ имеем f/((n) = п - 1, в этом случае неравенство выполняется. При \ <t < njl - 1 используем индукцию и (а). При t = п/2, lJt(n - 1) = Vt-iiji - 1) используем индукцию и (а).

27. (а) Высота h удовлетворяет соотношению 2 > Е; 1 Е/ Pr(i)/p = 1/р.

(b) Если г < t, мы достигнем A3 после не менее чем п - \So\ - \То\ - п - jSo) - г подбрасываний монеты. <-й по старшинству элемент будет либо самым малым, либо самым большим в Q, & элементы из Q еще не будут сравниваться один с другим, так что нам понадобится не менее \Q\ - 1 дополнительных подбрасываний монеты. Если 5о < q, получим \Q\ = г, а если нет, то получим \Q\ > \So\ - \С(уо)\ + 1 > \So\ - (q - г) + 1; так что в обоих случаях будет сделано не менее п - q подбрасываний. Существует п + 1 -t множеств Г, в которых содержатся t - 1 старших элементов, определяемых данным листом дерева, и для каждого такого Т вероятность достичь его равна либо О, либо 2*7("), где f > п - q есть число подбрасываний монеты, соответствующее Т. [Этот соперник был "реализован" в статье Бента (Bent) и Джона (John), STOC 17 (1985), 213-216.]

(c) Если t < г, замените t значением п+1 - t; получим, что t > г, когда г максимизирует правую сторону, поскольку г будет 0{\/п). Если возможно достичь A3 с C(j/) > q - r при всех у € То, алгоритм выполнит п - 1 сравнений t-ro по старшинству элемента со всеми други.ми в дополнение не менее чем к (г - l){q - г + 1) сравнениям, которые выполняются между 5 и Г \ {г/о}.

(d) Выберем г = [/т] и q = 2г - 2. (Несколько лучше положить g = г + [Ут+J - 2; такой выбор позволит максимизировать нижнюю оценку, выведенную в (с).)

РАЗДЕЛ 5.3.4

1. (Если m = 2fc- 1 нечетно, то лучше, чтобы в диаграмме за Vk вместо Wk+\, Vk+i, Wk+2, ... следовали элементы Vk+i, Wk+i, Vk+2, Такая замена корректна, поскольку линии, которые мы переставляем, сравниваются одна с другим.)

(3,5)-элементное четно-нечетное слияние

8-элементная сортировка Пратта

хз У1 У2

У4

Уъ

-VI -WI -V2

- W2 -V4 -W3 -V5

2]

• гг

гз

г4 25 26 27 28

2. Для приращения h нужно 2 - [2Л > п] уровней; см. приведенную выше диаграмму для

3. С{т,т-1) - С{т,т) - 1 при т>1.

4. Если предположить, что Т{&) = 4, то в каждый момент должны действовать три компаратора, так как 5(6) = 12. Но тогда, удалив нижнюю линию и связанные с ней четыре компаратора, мы получили бы 5(5) < 8, а это - противоречие. [Те же рассуждения показывают, что Г(7) == Т{8) = 6. Яан Парберри (Ian Parberry) провел длительный компьютерный поиск и пришел к результату Г(9) = T(IO) = 7; см. Math. Systems Theory 24 (1991), 101-116.]