AOP_Tom3 (1021738), страница 9
Текст из файла (страница 9)
Рассмотрим результаты завершенного турнира, матчи которого предопределялись таким соперником. Мы скажем, что "А превосходит В" тогда и только тогда, когда.4 = В или А превосходит игрока, который первым победил В. (Только пзрвое поражение игрока существенно в этом отношении, последующие его игры игнорируются. В соответствии с поведением соперника любой игрок, первььи победивший какого-либо другого игрока, ни в одной из предыдущих встреч не должен иметь поражений.) Отсюда следует, что игрок, который выиграл свои первые р матчей, превосходит на основании этих р игр не более 2г игроков.
(Если р = О, это очевидно, если же р > О, то р-й матч был сыгран против игрока, который либо ранее потерпел поражение, либо превосходит не более 2г ' игроков.) Чемпион превосходит всех, поэтому он должен был сыграть не менее (!кп) матчей. 1 Таким образом, задача нахождения второго в порядке убывания элемента полностью решена с помощью теоремы Я в "минимаксном" смысле. В упр.
6 показано, что можно дать простую формулу для минимального числа сравнений, необходимых для выявления второго элемента множества, если известно произвольное частичное упорядочение элементов. А что будет, если 1 > 2? В упомянутой статье Кислицын пошел дальше. Он рассмотрел большие значения 1, доказав, что ~е(п) < п — г+ ~ ($6 у) при п > й (6) ь+1-1<1«к Мы видели, что при 1 = 1 и 1 = 2 эта формула представляет собой равенство; при 1 = 3 она может быть слегка улучшена (см.
уяр, 21). Мы докажем теорему Кислицына, показав, что первые 1 стадий вь~бора нз дерева требуют не более п — 1+ ~„+,,«„(16Я сравнений (исключая все сравнения с — ос). Интересно, что правая часть (6) равна В(п), когда 1 = п, а также когда 1 = и, — 1 (см.
формулу 5.3.1 — (3)); следовательно, методы выбора из дерева и бинарных вставок приводят к одной и той же верхней оценке для задачи сортировки, хотя это совершенно различные методы. Пусть а — расширенное бинарное дерево с и внешними узлами, а я — перестановка множества (1, 2,..., и). Поместим элементы перестановки я во внешние узлы слева направо в симметричном порядке и заполним внутренние узлы в соответствии с правилами турнира с выбыванием, как при выборе из дерева.
Повторно применив операцию выбора к результирующему дереву, можно определить последовательность с„~ с„з...с,, где с есть число сравнений, требуемых, чтобы перенести элемент з' в корень дерева после того, как элемент ~' + 1 будет заменен элементом †. Например, если а — дерево и если я = 5 3 1 4 2, то мы получаем последовательные деревья ,,=О сэ =О сэ = з сз — — г Если же я = 3 1 5 4 2, то последовательность с4 сэ ст сг будет иной, а именно — 2 1 1 О.
Легко видеть, что сг всегда есть О. Пусть р(а,я) — мультимножество (с„г,с„а,...,сг), определяемое а и я, Если гг' оя и если элементы 1 и 2 не содержатся оба либо в а', либо в а", то легко видеть, что р(о,я) = (р(а',я') + Ц Ь (р(а",з") + Ц м (О) для подходящих перестановок я' и х", где р, + 1 обозначает мультимножество, получаемое в результате прибавления 1 к каждому элементу р (см. упр. 7). С другой стороны, если и элемент 1, и элемент 2 паходятгя в а', имеем р(а,я) = (р(а',я') + е) Ь (р(о",кл) + Ц 'чг (О), где р + г обозначает какое-нибудь ьгультилгножество, получаемое в результате прибавления 1 к некоторым элементам р и Π— к остальным.
Аналогичная формула справедлива и в том случае, если элементы 1 и 2 находятся в а". Будем говорить, что мультимгнзжество рг мажорируегн рт, если и рг, и рз содержат равное число элементов и если й-й в порядке убывания элемент рг больше 1г-го в порядке убывания элемента рз для всех й или равен ему. Определим р(а) как мажоранту р(а, я) по всем перестановкам я в том смысле, что р(о) мажорирует р(а,т) при всех к и р(а) = р(а, я) при некотором я. Приведенные вьппе формулы показывают, что р(П) = й, Иу( Д ) = ( (-') - Ц ~ (р(-Я) 4 Ц Ь (О); а' ая следовательно, р(о) есть мультпмножество всех расстояний от корня до лай "греняпх узлов а.
Если читатель уследил за ходом нагпих рассуждений, ему должно бьгть ясно, что теперь мы готовы доказать теорему Кислицына (6). Поскольку У',(и) меньше илн равно п — 1 плюс 1 — 1 наибольпшх элементов р(а), где а — любое дерево, используемое при сортировке посредством выбора из дерева, то можно считать а полным бинарным деревом с и внешними узлами (см. раздел 2.3.4.5), причем Мы получим формулу (6), если рассмотрим С вЂ” 1 наибольших элементов этого мультимножества. Теорема Кислицына дает хорошую верхнюю оценку для И'л(и); Кислицын отметил, что 1з(5) = 6 < Из(5) =- 7, но не смог найти в общем случае оценку для р;(п), лучшую, чем для Ил(п).
Это было сделано Л. Хадьяном (Л. Набйап) и М. Собелем (М. БоЬе1), которые использовали ел~бор с замещением вместо выбора из дерева (см. раздел 5.4.)). Выведенная ими формула (Сшт. о1 Мшпезоса, Перс. оЕ БСасгзс!сз Нерогг 121 (1969)), Ъс(п) < п — С+(С 1)Г15(п+2 С)1 и > С, (11) отличается от формулы Кислицына тем, что каждый элемент суммы в (6) заменен наименьшим элементом.
Теорему Хадьяна в Собеля (11) можно доказать, воспользовавшись следующей схемой. Сначала сформируем бинарное дерево для турнира с выбыванием и — С + 2 элементов (участников), что потребует п — С + 1 сравнений. Наибольший элемент превосходит п — С+ 1 других элементов, поэтому он не может быть С-м в порядке убывания. Заменим его во внешнем узле дерева одним из С вЂ” 2 элементов, оставшихся в резерве, и найдем наибольший элемент нз образовавшегося набора п -С+ 2 элементов; это требует не более (15(п+ 2 — С)) сравнений, поскольку придется заново вычислить только один путь в дереве.
Повторим эту операцию в общей сложности С вЂ” 2 раз— по одному разу для каждого элемента из резерва. Наконец, заменим текущий наибольший элемент элементом — оо и определим наибольший из оставшихся п + 1 — С элементов; для этого потребуется не более ~15(п+ 2 — С)) — 1 сравнений, и С-й в порядке убывания элемент исходного множества попадет в корень дерева. Суммировав число сравнений, получаем вьгражение (11), Разумеется, мы должны заменить С на п+ 1 — С в правой части соотношения (11), если п+ 1 — С дает лучшее значение (как при п = 6 н С = 3).
Как ни странно, но эта формула дает для Ъг(13) меньшую оценку, чем для ге(13). Верхняя оценка в (11) точна для и < 6, но когда и и С становятся большими, можно получить значительно лучшие оценки для Ъл(п). Например, можно использовать следующий изящный метод (принадлежащий Дэвиду Г. Дорену (11атЫ 6. хосеп)), чтобы показать, что Рз(8) < 12. Обозначим элементы через Хы.,,,Хз. Сначала сравним ХС.Хг и Хз.Хы а затем — двух "победителей" между собой; проделаем то же самое для пар Хл ..Хе и Лг: Хз и "победителей" этих пар. Переименуем элементы так, чтобы получить Х, < Хг < Х4 > Лз, Хл < Хе < Хз > Хг, затем сравним Хг.Хе, в силу симметрии положим Хг < Хе, поэтому получим конфигурацию (Теперь Хг и Хв вылили из игры и мы должны найти третий в порядке убывания элемент из (Хм..., Хг).) Сравним Хз ..Хт и отбросим меньший: в худшем случае получим Хз < Хп Найдем третий в порядке убывания элемент из э — в ° 7 З вЂ” 4 Это можно сделать еще за ! з(5) — 2 = 4 шага, так как процедура для Ъз(5) = 6 в (11) начинается со сравнения двух непересекающихся пар элементов.
Можно использовать другие трюки подобного вида и получить результаты, показанные в табл. 1, но никакого общего метода до сих пор не существует. Значения, указанные для !'э(9) = Ъв(9) и 1;;(10) = Ъгв(10), являются оптимальными, как доказано в рабюте ЪЪ'. СазагсЬ, ЪУ. Ке!!у, ЪЪг. Рн8Ь, ЯСАСТ !уняв 27,2 (Липе, 1996), 88-96, в которой использовался компьютерный поиск. Хорошая нижняя оценка для задачи выбора в случае, когда 1 малб, получена в работе Дзвида Г, Киркпатрнка (Ратай С. К!г!гранат!с(г) (.!АСМ 28 (1981), 150-165): если 2 < 1 < (п + 1)/2, получим г — 2 п — 1+ 21! Ъ'г(и) > и+ г — 3+ ~ 18 г+л Л=о (12) В своей диссертации (РЬ.
Р. 1Ьсв!в, Б. о! Тогопго, 1974) он доказал, что 1.;(и) «и+1+ !8и ' + !8и ' (13) эта нижняя оценка соответствует нижней оценке, что следует из (12) при 18 —— 5 74г/о всех целых чисел и н превосходит (12) не более чем на 1. Выполненный Киркпатриком анализ дает осн<иание предположить, что равенство в (13) будет соблюдаться и для всех и > 4, по Ютта Зстерброк (Листа Енвгегйгос1г) отыскала удивительный противоречащий этому пример Ъз(22) = 28 (РЛэсгесе Арр!!ег( МаГЛ.
41 (1993), 131-137]. Несколько улучшенная нижняя оценка для больших значений 1 найдена С. У. Бентом (8. ЪЪг. Вепт) и Дж. У. Джоном (Л. Ч'. ЛоЬп) (см. упр. 26): Ъс(п) > и+ т — 2Гх/ш1 'г' 2+ Г!8(( )/(и+1 — 1))1. (14) Эта формула доказывает, в частности, что 1 1 Ъ ап (п) > (1 + а 18 — + (1 — а) 18 — 1 п + 0 (хгги ) .
а 1 — а) (15) Линейный метод. Если и нечетно и 1 = !'и/2), то с-й в порядке убывания (и Г-й в порядке возрастания) элемент называется медианой. В соответствии с (11) мы можем найти медиану п элементов за ш гп.18и сравнений, но это лишь приблизительно вдвое быстрее сортировки, .хотя в таком случае нам нужно значительно меныпе информации. В течение нескольких лет объединенные усилия множества исследователей были направлены на улучшение формулы (11) для больших значений ! я п; наконец, в 1971 году Мануэль Блум (Мапне1 В1шп) открыл метод, требующий только Р(п !о8 !о8 и) шагов. Подход Блума к этой задаче дал толчок к Таблица 1 ОЦЕНКИ Ь1(я) ПРИ МАЛЫХ я п 1б(п) 1з(п) Иэ(о) 1е(я) ~'е(о) 1"е(п) 1~;.(я) Ре(п) 1я(п) 1(а(п) 1 0 2 1 1 3 2 3 2 4 3 4 4 5 4 б 6 б 5 7 8 7 б 8 10 8 7 9 11 9 8 11 12 10 9 12 14" 3 б 4 8 7 5 10' 10 8 б 12 12 11 9 14 14' 14 12 15 1б* 16 " 15 7 11 8 14" 12 9 ' Для этих случаев в упр.
10-12 приводятся схемы, поэволяюоше'улучшить (11). " См. К. эоя!пса. Тт воя оГ СЬе ЖСЕ об уярао Е59, 12 (Песеты, 1976), 17 — 18 развитию нового класса методов, который привел к следующему построению (см. К. К1сея1, К. Тат)эл, о'. Сотр. аЫ Яуя. Яс'. 7 (1973), 448 — 461). Теорема Ь. !'~(п) < 15п — 163 прн 1 < 1 < н, когда п > 32. Докаэашельство. Когда п малб, теорема тривиальна, так как К(п) < о(п) < 10п < 1оп — 163 для 32 < и < 2'о. Добавив самое большее 13 фиктивных элементов — оо, можно считать, что н = 7(29 + 1) при некотором целом д > 73. Теперь для выбора 1-го в порядке убывання элемента воспользуемся следующим методом. Шаг 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
