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