Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 85
Текст из файла (страница 85)
Найдя медиану первых /(и) элементов, скажем Х„сравним ее с каждым из остальных; это даст разбиение всех элементов на приблизительно и/2 — Й меньших, чем Х», и и/2 + Ь больших, чем Х», при некотором Ь. Остается найти ]Ь]-й в порядке убывания или возрастания элемент большего множества, что требует еще и/2+ О(]Ь]!обп) сравнений. Среднее значение ]Ь] равно 0(1/т/й) + О(в/Я(п) ) (рассмотрите точки, равномерно распределенные на интервале ]0..1]).
Обозначим через Т(п) среднее число сравнений для /(и) = и»"; имеем Т(п) — и = Т(пэз ) — п»7" + и/2+ 0(п 7 ); отсюда следует искомый результат. Интересно, что прп и = 5 этот метод требует только ЬЦ сравнений в среднем, что несколько лучше, чем дерево из упр. 9. 14. В общем случае 1 наибольших элементов можно найти за (7»(п) < И»(п — 1) + 1 сравнений, есл»» определить г-й в порядке убывания элемент из (Х»,..., Х„» ) и сравнить его с Л„(имея в ви»0' упр. 2). (Киркпатрик доказал, что (12) является ни»кней оценкой длк О»(п+ 1) — 1.
При ббльших 1 найдена более точная оценка ц(п) ]ем. 2, %'. Зо!»и, яСОМ)э 17 (1988) 640 647] ) 15. Требуется ш!п(1» и+1-1) слов памяти. Предположим, что 1 < т»+ 1 — б Егли мы не сохраним все первые 1 слов, когда они читались в первый рэз, то можем потерять 1-й в порядке убывания элемент, зависящий от последующих значений, все еще не известных нам. Обратно, 1 ячеек достаточно, так как мы можем сравнивать вновь введенный элемент с предыдущим г-м, запоминая значение в регистре тогда и только тогда, когда он больше. 16. Перед началом выполнения алгоритмы (о,Ь а,д) = (п,0,0,0), а после завершении получаетск четверка (0,1,1,п — 2).
Егти соперник избе»вет непредвиденных исходов, то после каждого сравнения (п, Ь, с, »4) может перейти либо в себя, либо в А' в А, которое содержит ае, ам ..., а»,+., Обратите виямание на то, что А', как и только что подросшее В, есть дерево турнира с выбыванием, в котором 2" '+74' листьев.) Сравните Ь с а»-».ь!+», затем сравните победителя с о»-»+»+э и так до тех пор, пока не будет найдено с = шах(Ь,аь»~.1 и ..,,о» ~). Случай 1, 6 < с: вывести а н поменять В с А'.
Случай 2, Ь = с и 6 < а: вывести а и поменять В с А'. Случай 3, Ь = с и Ь > а: вь»вести 6. После отработки этих трех случаев мы останемся с деревьями А и В (возможно, новыми), в которых побелитевь В только что ушел на выход. Удалите этот элемеят нз В и замените его элементом -со, выполнив асе сравнения, необходимые для восстановления структуры дерева (как в методе выбора из дерева). Этим завершится шаг 71 На шаге 0 выполняется 2» — 1+ 2 +' ' — 1 сравнений, а на шаге ! выполняется одно. На кая»дом из шагов 1, 2, ..., ! — 1 выполняется не более 6 — 1 сравнений, кроме случая 2, когда их может быть 6.
Но если только возникает глучай 2, мы сохраним одно сравнение на следующий раз для случая 1 илн случая 2, поскольку ае тогда окажется равным -со. Таким образом, суммарно на шагах от 1 до Ф вЂ” 1 выцолияетсе не более (! — Ц(6 — 1) + 1 сравнений. Как следует из результатов упр, 3, имеем И~»(п) < и+ (! — Ц(6 — 1] для всех и < 2» + 2»+» ', если 6 > ! > 2. Если и > 2" + ! — 2, результаты упр.
4 говорят, что )4'»(и) > п — Ф+ (!8(2" + ! — 2) — '» ], а это равно и — 1+ (г — 1)6+ 1, если ! > 3. Таким образом, данный метод оптимален прн 2 +! — 2 < и < 2 + 2 +' ', если 6 > ! > 3 (а также для некоторых меньших значений и, если ! больше). Аналогичный метод, в котором используются резервные элементы вместо — оо при перестройке В в конце шагов 1, ..., ! — 2, доказывает, что У»(п) < я + (! — Ц(6 — Ц, когда я < 2 + 2"е' ' + ! — 2 и 6 > 1 > 3 (см.
дошшательство формулы (1ц). [См. Х А!8оп»6шз б (1984), 557-578.] 22. В общем случае, если 2" 2» < н + 2 — ! < (2' + Ц . 2" н ! < 2" < 21, такая процедура с 1+ 1 деревьями с аыбыванием размером 2 использует нв ](! — Ц/2] сравнений меньше, чем (1Ц, так как, по крайней мере, столько сравнений, примененных в (й) для нахождения минимума, могут быть вновь использованы в (!!!). 23, Как следует нз (15), количество Ъ'1„7з!(и)/и ограничено снизу значением 2 при и -+ сю; но в работе П. Ног, РЬ.
П. »Ьези., Те! Ат!т Пп!тегш!у, 1995, показано, что в действительности нижняя граница значительно выше 2. Дор и Ю. Зв»»к (1). ЕвбсЫ) также нашли верхнюю гранищ; которая оказалась равной 2.942 ]БОВА 6 (1995), 28-37]; они показали, что асимптота для верхней оценки есть Ъ' „(и) < (1+и !8 — + 0(а!ой!ой-))п, 1 1 что не очень отличается от (15), если о достаточно мало ]СшпЬ!ла»опса 16 (1996), 41-58]. 24. Поскольку ЬУ»(п) = и+ О(! !о8 и), как следует из выражения (б), утверждение, которое содержится в указании, определенно, справедливо., если ! <»/и/ 1п и. Предположим, что это утверждение выполняется для и, и пусть и и е имеют ранги ! = ]! — Япп] и !+ — — ]! + ч7! !пи] среди первых и из расположенных в случайном порядке 2п элементов. (Наименьший элемент имеет ранг 1.) Сравните другие и элементов с е и сравните те нз ннх, которые меньше е, также с о.
Вероятность р, того, что элемент и ранга ! в первых и имеет ранг з среди всех, равна (;,')(„",')»»(„"). Среднее значение з есть 2 вр, = ЛЯ!; зто среднее число элементов < х; следовательно, среднее чигло сравнений с и равно („",) !е = 1+ 0(п!ойп)ыз. Пусть и и е имеют ранги з н е+ среди всех 2п элементов и пусть Т ж (2! — »/2!!п2п], Тч.
—— ]21+»I2! !и 2п]. Если в < Т и зь > Те, можно отыскать элементы рангов Т н Т посредством выбора е+-е-+1 элементов мех»лу и и и, Докажем, что очень маловероятно, чтобы оказалось з > Т или з < Т вЂ” 2~А!пи, или и+ < Т+, или в+ > Т»+ 2«/и !и и: таким образом, почти всегда будет достаточно О(и |об я) Ы~ дополнительных сравнений. Из указания следует индукция по и, ыши мы сможем показать, что "очень маловероятно" означает "с вероятностью О(п ' ') для всех достаточно больших и". Обратите внимание, что р«ы/р, =- э(п — «+1)/(е+ 1 — 1)(2п — е) уменьшается по мере того, как э увеличиваетск от 1 до и + 1 и это отношение < 1 тогда и только тогда, когда э > 2п(1 — 1)/(и — 1); оно < 1 — -'сп '~'+0(п '), когда э = э(с) = 21+с|(п-1)/п»7~. Таким образом, вероятность того, что э > э(с), равна < 2с ~пы~рцы(1+ 0(н ы~)), Аналогично р, ь/р, < 1 — фсп Ыэ — 0(п '), если э = й(с) = 21 — 1 — с(1 — 1)(п+ 1 — 1)/ип7~, так что э < э(с) с вероятностью < 2с 'инар»м1(1+ О(п '7~)).
В тех случаях, которые нас интересуют,подхсдящиезначеииясесть >.55««~7 (!вп)ы 1 ~ (и — 1) для всех больших и, а аппроксимация Стирлинга дает, что рцы н рць1 равны 0(пЫ»в «7»(2п — э) Ыэ) ехр(-2эсэ(п — г)э/пз — 2(2п — «)сэгэ/пэ) < 0(1 7 ехр( — 41(㫠— 1)с/и )) < О(1 7 и ' ). Это подтверждает, что вероятность 0(п ьэ(!обп)Ы») действительна очень мала. [Аналогичная схема имеется и в САСМ 18 (1975), 165-172, но представленный в этой работе анализ некорректен.) 26. Имея заданный алгоритм выбора и перестановку я множества (1...., и), организуем для каждой |-й перестановки отдельный счет (аккумулятор).
После каждого сравнения я;: яу добавим 1 на счет я„если [я, — 1[ > [я„— 1[; если же [я; -1[ = [я -1[, отнесем по «на счет обеих. Отнесение на счет я, называется полезным, если х„< я < 1 или я; > я; > й в противном случае оно бесполезно. Пусть 㫠— итоговый счет для Ь. Тогда общее число сравнений равно х«+. + г.„.
Очевидно, что х« = О; но х» > 1 для всех Й ~ |, поскольку каждый элемент, отличный от й имев~ полезный счет. Докажем, что Ех,+«+ Е х, «> 3 прнО <5 <й Пусть А«(я) = [первое добавление на счет 1+ Ь было бесполезным!. Тогда А»(л) = 1 — .4»(я'), где я' подобно х, но элементы (1 — Й,...,1+ Й вЂ” 1,1+ Й) зал«енены в нем соответственно элементами (1 — 5+1,...,1+5,э-й).
Таким образом, Е А«+ Е А-« = 1. Пусть В«(я) = [первое добавление на счет и 1 + Ь, и 1 — Ь было -' и 1 + Ь получило второе добавление на счет прежде, чем 1- й). Пусть также С«(я) = [я««» > 2+ А»[. Тогда В«(я) < С»(я'), где х' подобно я, но с заменой элементов (1 — 5,1 — Ь + 1,...,1 + Ь вЂ” 1) элементами (1+1-1,1 — Ь,...,1+5 — 2). Аналогично В»(я) < С «(л"), где як получено из я посредством замены (1 — 5+1,..., Ф+Ь вЂ” 1„1+5) элементами (1-1+2,...,1+1,г-1+1). Отсзада следует, что Е В» < Е С«и Е В.. » < Е С.. «.
Доказательство завершается выводом, что х, «+ х«««> 2+ А«+ А-« — В« —  — «+ С» + С-«[Дальнейшие результаты приводятся в ЗАСМ 36 (1989), 270-279.[ Верхняя оценка в (17) имеет также соответствующую нижнюю оценку: Эндрю и Фрэнсис Яо доказали, что г',(и) > и+ -'1(1п |пи — |п1 — 9) при 1 > 1 н и > (81)цв [см. $1СОМР 11 (1982), 428-447]. 26. (а) Обозначим вершины компонентов двух типов через а; Ь < с. Соперник поступает глелующим образом при нензбыточных сравнениях. Случай 1, а: а': принять произвольное решение. Случай 2, я: Ь: сказать, что х > Ь; все последующие сравнения р: Ь с этим конкретным Ь будут иметь результат 9 > Ь, в противном случае сравнения выбираются соперником для К(п — 1), что приводит в общей сложности к > 2+ Ц(п — 1) сравнениям.
Это снюкение будем для краткости выражать так: "пусть Ь = ппп; 2+ Ц(п — 1)'! Случай 3, и; с пусть с = шах; 2+К «(и — 1). (Ь) Обозначям новые типы вершин дц г(э < е: / < 9 < Ь > «, Случай 1, а: о~ или с: с: произвольное решение, Случай 2, а: с: сказать, что а < с. Случай 3, х: Ь: пусть Ь ж ппп; 2+ 0«(ц — 1). Случай 4, х: 8: пусть г( = «и!и; 2+ 0«(п — 1). Случай 5, х: е: пусть е = шах; 3+ (/ь ь(п — 1). Случай б, х: /: пусть / = ппп; 2+ Уь(п — 1). Случай 7, я: ук пусть / и у = ппп; 3+ У,(п — 2). Случай 8, г: Ь; пусть Ь = ьпах; 3+ К ь(п — 1), Случай 9, х: и пусты' = пип; 2 + Уь(п — 1), (с) Поскольку при 1 = 1 имеем Уь(п) = и — 1, в этом случае неравенство выполняется.
При 1 < 1 < и/2 — 1 используем индукцию и (а). При 1 = и/2. К(п — 1) = К ь(п — 1) используем индукцию и (а). 27. (а) Высота Ь удовлетворяет соотношению 2" > ~„, 1 > ~, Рг(1)/р = 1/р. (Ь) Если г < Ь мы достигнем АЗ после ие менее чем и — [ое[ — [Те[ =- и — [Яе[ — г подбрасываний монеты. С-й по старшинству элемент будет либо самым малым, либо самым большим в Ц, а элементы из 1,) еще ие будут сравниваться один с другььм, так что иам поиэдобится ие менее [ф — 1 дополнительных подбрасываиий монеты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
