AOP_Tom3 (1021738), страница 186
Текст из файла (страница 186)
См. 1пуогшас)оп Рсоселзтй йессеге 3 (1974), 8 — 12. 12. После удаления наименьшего из (Л|,ЛюХ|,Л|) получаем конфигурацию плюс и — 3 изолированных элементов; третий из них может быть найден еще за 1Рэ(п — 1) — 1 шагов. есчи а > 2; если о > 1 1" если Ь>2; ерши с > 2. (а-2, Ь+1, с+1, 8), (а — 1, 6, с+1, р() или (а-1, 6+1, с, р(), (а, Ь вЂ” 1, с, 4+1), (а, Ь, с-1, |1+1)р Отсюда следует, что требуется ) 1а~( + 6 + с — 2 сравнений, чтобы из (а,б,с,|1) получить (О, 1, 1, а+6+с+|2-2).
(Ссс САСМ 15 (1972), 462-464. В работе ПОСВ 16 (1975), 71-74, Пол доказал, что этот алгоритм также минимизирует среднее число сравнений.) 17. Используйте (6) сначала для наибольшего элемента, затем — для наименьшего. Обратите внимание на то, что (и/2) сравнений общие для обоих глучаев. 18. И(а) < 18п — 151 при всех достаточно больших п, 21. Швг О.
Постройте два дерева турниров с выбыванием размерами 2" и 2" Швг 2 для 1 < / < б (К этому моменту уже выведено / — 1 наибольших элементов Оставшиеся элементы вместе с набором фиктивных, каждый из которых равен — |ю, появятся теперь в двух деревьях, А и В, где А имеет 2" листьев, а  — 2~ 'еР.) Пусть а — победитель в А, и предположим, что а выиграл у ае, а|, ..., аы, где а| — победитель среди 2 элементов.
Аналогично пусть Ь и 6е, Ьр, ..., Ьы ер — | победитель и обладатель второго места в В. Если / = 1, вывести шах(а, Ь) и прекратить выполнение. В противном случае "нарастить' другой уровень в нижней части В, вставив 2 'е' фиктивных элементов, каждый из которых считается проигравшим в первой встрече с участником В. (Наша стратегия — влить В в А, если возможно, заменив нм поддерево 13. Найдя медиану первых /(и) элементов, скажем Х;, сравним ее с каждым из остальных; это даст разбиение всех элементов на приблизительно и/2 — 6 меньших, чем Х„и и/2 + Ь болыпих, чем Хр, при некотором Ь.
Остается найти (Ц-й в порядке убывания нли возрастания элемент большего множества, что требует еще и/2 + О((/с) 1ойп) сравнений. Среднее значение )6( равно 0(1/|/и) + 0(п/Я(п) ) (рассмотрите точки, равномерно распределенные на интервале (О.. 1)). Обозначим через Т(п) среднее число сравнений для /(и) = п~Р~; имеем Т(п) — и = Т(ппР~) — пэеэ 4 и/2 + О(р|~Р~); отсюда следует искомый результат. Интересно, что при и = 5 этот метод требует только 5|аз сравнений в среднем, что несколько лучше, чем дерево из упр.
9. 14. В общем случае Г наибольших элементов можно найти за (/р(п) < 1рр(п — 1) + 1 сравнений, если определить С-й в порядке убывания элемент из (Л|,..., Л„|) и сравнить его с Х„(имея в виду упр. 2). (Киркпатрик доказал, что (12) нвляется нижней оценкой для Ур (и+ 1) — 1. При бблыпих 1 найдена более точная оценка сгр(п) (см. 3. Чр. Зо1|п, ЯСОМР 17 (1988), 640 — 647).) 15.
Требуется |п|п(1,и+1 — 1) слов памяти. Предположим, что 1 < и+ 1 — б Если мы не сохраним все первые 1 слов, когда они читались в первый раз, то можем потерять С-й в порядке убывания элемент, зависящий от последукрщих значений, все еще не известных нам. Обратно, 1 ячеек достаточно, так как мы можем сравнивать вновь введенный элемент с предылуп|им с-м, запоминая значение в регистре тогда и только тогда, когда он больше.
10. Перед началом вып|нтнепня алгоритмы (о,б,с,й) = (и, О, 0,0), а после завершения получается четверка (О, 1, 1, и — 2). Если соперник избегает непредвиденных исходов, то после каждого сравнения (а, Ь, с. с() может перейти либо в себя, либо в А' в А, которое содержит ао, ам, а»»+,.
Обратите внимание на то, что А', как н только что подросшее В, есть дерево турнира с выбыванием, в котором 2» '+в+' листьев.) Сравните Ь с а» ьлвп затем сравните победителя с а»-с+»эв и так до тех пор, пока не будет найдено с = тах(Ь,а» ь»1 ц....а» с). Случай 1, 6 < с: вывести а и поменять В с А', Случай 2, 6 = с и Ь < а: вывести а и поменять В с А'. Случай 3, 6 = с и 6 > а: вывести Ь. После отработки этих трех случаев мы останемся с деревьями А и В (возможно, новыми), в которых победитель В только что ушел на выход.
Удалите этот элемент из В и замените его элементом — оо, выполнив все сравнения, необходимые для восстановления структуры дерева (как в методе выбора из дерева). Этим завершится пшг ! На шаге 0 выполняется 2 — 1 + 2"~' ' — 1 сравнений, а на шаге С выпачняется одно. На каждом из шагов 1, 2,..., С вЂ” 1 выполняется не более Ь вЂ” 1 сравнений, кроме случая 2, когда их может быть Ь.
Но если только возникает случай 2, мы сохраним одно сравнение на гледующий раз для случая 1 или случая 2, поскольку ао тогда окажется равным — оо. Таким образом, суммарно на шагах от 1 до С вЂ” 1 выполняется не более (С вЂ” 1)(1с — 1) + 1 сравнений. Как следует нз результатов у~р, 3, имеем И'~(и) < и + (С вЂ” 1)(Ь вЂ” 1) для всех и < 2" + 2»+' ', если Й > С > 2.
Если и > 2 + С вЂ” 2, результаты упр. 4 говорят, что Иг (и) > и — С+ (18(2 + С вЂ” 2)'='), а это равно и — С+ (С вЂ” 1)6+ 1, если С > 3. Таким образом, данный метод оптимален при 2 + С вЂ” 2 < и < 2 + 2»+' ', если й > С > 3 (а также дли некоторых меньших значений и, если С больше). Аналогичный метод, в котором используются резервные элементы вместо — сю при перестройке В в конце шагов 1, ..., С вЂ” 2, доказывает, что Ус(и) < и+ (С вЂ” 1)(Ь вЂ” 1), когда и < 2" + 2~т' '+ С вЂ” 2 и Ь > С > 3 (см.
доказательство формулы (11)). (См. Х А18оНСЛтв 5 (1984), 557-578.) 22. В общем случае, если 2" 2" < и+ 2 — С < (2'+ 1) 2" и С < 2" < 2С, такав процедура с С + 1 деревьями с выбыванием размером 2" использует на ((С вЂ” 1)/2) сравнений меньше, чем (11), так как, по крайней мере, столько сравнений, примененных в (й) для нахождения минимума, могут быть вновь использованы в (ш). 23. Как следует из (15), кшсичество У1„1»! (и)/и ограничено снизу значением 2 при и -+ оо; но в работе П.
11ог, РЬ. П. СЬеэ!э, Те! А ив На!геев!Су, 1995, показано, что в действительности нижняя граница значительна выше 2. Дор и Ю. Звяк (1 йичс!») также нашли верхнюю границу, которая оказалась равной 2.942 (ЯООА 6 (1995), 28-37); они доказали, что асимптота для верхней оценки есть 1ьв(и) < (1+ о!8 — + О(о!об1о8-)) и, 1 1 что не очень отличается от (15), если о достаточно мало [СшпЬСпаСойса 16 (1996), 41-58). 24.
Поскольку )У~(и) = иЧ-0(С !о8 и), как гледует из выражении (б), утверждение, которое содержится в указании, определенно, справедливо, если С <»/и/!ни. Предположим, что это утверждение выполняется для и, и пусть а и о имеют ранги С = (С вЂ” ъЯпи) и С+ —— ! С+»/С !а и) среди первых и из расположенных в случайном порядке 2и элементов. (Наименьший элемент имеет ранг 1.) Сравните другиг и элементов с о и сравните те из них, которые меньше е, также с и. Вероятность р, того, что элемент х ранга С в первых и имеет ранг в среди всех, равна (; с)(~„";)/(~„"). Среднее значение в есть 2 вр, = »Яс; это среднее число элементов < х; следовательно, среднее число сравнений с и равно ( "„) !+ —— С + О(и 1об и) м~. Пусть а и о имеют ранги в и в» среди всех 2и элементов и пусть Т (2С вЂ” ъl2Сра 2и),2+ — — )2!+»/2~!п2и).
Если» < Т ив» > Т», можно отыскать элементы рангов Т и Тт посредством выбора вв-в +1 элементов между а и и. Докажем, что очень маловероятно, чтобы оказалось в > Т или в < Т вЂ” 2»/и!аи, или ве < Тв, или в+ > Те+2 /и 1и и; таким образом, .почти всегда будет достаточно 0(и 1об п) С дополнительных 112 сравнений. Из указания следует индукции по п, если мы сможем показать, что "очень маловероятно" означает "с вероятностью 0(и ' ') для всех достаточно больших и". Обратите вин»«ание, что рцы/р, = в(п — в + С)/(в+ 1 — С)(2и — в) уменьшается по мере того, как в увеличивается от С до п + С и это отношение < 1 тогда и только тогда, когда в > 2п(С вЂ” 1)/(и — 1), оно < 1 — „-'си' Па+ 0(п '), когда в = в(с) = 21+ ос(и — С)/и~1~.
Таким образом, вероятность того, что в > в(с) равна < 2с 'и'Сэрдм(1 » 0(п Мс)). Аналог»сино р, л/р, < 1 — -'сп Пс — 0(п '), если в = в(с) = 2С вЂ” 1 — с(С вЂ” 1)(п + 1 — с)/пэгс, так что в < в(с) с вероятностью < 2с 'иц~рц,1(1+ 0(и П~)). В тех случаях, которые нас интересуют, подходящие значения сесть > .55п»1~(1п п)«С~С '1~(п — С) ' для всех больших п, а аппроксимация Стирлинга дает, что рцю и рцю равны 0(и в (2п — в) 1 ) ехр( — 2вс~(п — С)с/пв — 2(2гс — в)с»сс/лсв) < 0(С ехр( — 41(и — С)с /лс )) < 0(С ~ гс ).
Это подтверждает, что вероятность 0(г» ' '(!обп) "с) действительно очень мала [Аналогичная схема имеется и в САСЛ1 18 (1975), 1б5-172, но представленный в этой работе анализ некорректен.] 25. Имея заданный алгоритм выбора и перестановку я множества (1, ,и), организуем для каждой бй перестановки отдельный счет (аккумулятор). После каждого сравнения к,: Ял Добавам 1 на счет х„если [Я, — С[ > [лг, — С[; если же [к, — С[ = [лг, — С[, отнесем по -' на счет обеих Отнесение на счет я, назьсвается полевкам, егли к, < к, < С или хс > я, > С; в противном случае оно бесполезно. Пусть х« - итоговый счет для й.
Тогда общее число сравнений равно хл + + х„. Очевидно, что хс = 0; но х» > 1 для всех й ф С, поскольку каждый элемент, отличный от С, имеет полезный счет Докажем, что Ехсл«+ Ехс «> 3 при 0 </с<С. Пусть А«(я) = [первое добавление на счет С+ й было бесполезным]. Тогда А«(я) = 1 — А «(я'), где з.' подобно лг, но элементы (С вЂ” й,..., С + й — 1,1 -» й) заменены в нем соответственно элементами (С вЂ” 64-1,..., С Ьй, с-1с). Таким образом, ЕА» + Е А .« = 1 Пусть В«(я) = [первое добавление на счет и С + й, и С вЂ” Сс было -' и С + Сс получило второе добавление на счет прежде, чем С вЂ” й]. Пусть также С»(лг) = [хс««> 2 + А«]. Тогда В»(я) < С«(лс'), где хг подобно лг, но с заменой элементов (С вЂ” й, С вЂ” Сс+ 1,..., С+ й — 1) элементами (с+й — 1,1 — /с..., С+/с — 2). Аналогично В»(я) < С «(я"), где яс' получено из к посредством замены (С вЂ” й+1,..., С+/с — 1, С+й) зле»сентами (С вЂ” /с+2,, С+1с, С вЂ” й+1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
