соперник может принимать произвольное решение, не противоречащее некоторому частичному упорядочению.

Рассмотрим результаты завершенного турнира, матчи которого предопределялись таким соперником. Мы скажем, что "Л превосходит В" тогда и только тогда, когда А = В или А превосходит игрока, который первым победил В. (Только гфвое поражение игрока существенно в этом отношении, последующие его игры игнорируются. В соответствии с поведением соперника любой игрок, первым победивший какого-либо другого игрока, ни в одной из предыдущих встреч не должен иметь поражений.) Отсюда следует, что игрок, который выиграл свои первые р матчей, превосходит на основании этих р игр не более 2 игроков. (Если р = О, это очевидно, если же р > О, то р-й матч был сыгран против игрока, который либо ранее потерпел поражение, либо превосходит не более 2~ игроков.) Чемпион превосходит всех, поэтому он должен был сыграть не менее [Ign] матчей.

Таким образом, задача нахождения второго в порядке убывания элемента полностью решена с помощью теоремы S в "минимаксном" смысле. В упр. 6 показано, что можно дать простую формулу для минимального числа сравнений, необходимых для выявления второго элемента множества, если известно произвольное частичное упорядочение элементов.

А что будет, если t > 2? В упомянутой статье Кислицын пошел дальше. Он рассмотрел большие значения t, доказав, что

Wtin) <n-t+ Jl при n>t. (6)

n+l-t<j<n

Мы видели, что при t = 1 и t - 2 эта формула представляет собой равенство; при t = 3 она может быть слегка улучшена (см. упр. 21).

Мы докажем теорему Кислицына, показав, что первые t стадий выбора из дерева требуют не более п - t Л- 1Г„+1 <<<„ [Igil сравнений (исключая все сравнения с -оо). Интересно, что правая часть (6) равна В{п), когда t = п, а также когда t = n-1 [см. формулу 5.3.1-(3)]; следовательно, методы выбора из дерева и бинарных вставок приводят к одной и той же верхней оценке для задачи сортировки, хотя это совершенно различные методы.

Пусть а - расширенное бинарное дерево с п внешними узлами, а тг - перестановка множества {1,2,..., п}. Поместим элементы перестановки тг во внешние узлы слева направо в симметричном порядке и заполним внутренние узлы в соответствии с правилами турнира с выбыванием, как при выборе из дерева. Повторно применив операцию выбора к результирующему дереву, можно определить последовательность с„ 1 с„ 2 ... ci, где Cj есть число сравнений, требуемых, чтобы перенести элемент j в корень дерева после того, как элемент j + l будет заменен элементом -00. Например, если а - дерево

и если 7Г = 5 3 1 4 2, то мы получаем последовательные деревья

й ш/)

(Ah ты

С4 = 1

СЗ =2

С2 = о

С1 =0

Если же7г = 31542, то последовательность C4 сз сг ci будет иной, а именно - 2 1 1 0. Легко видеть, что cj всегда есть 0.

Пусть /г(а,7г) - мультимножество {c„ i, с„ 2, • •, cj}, определяемое а и тг. Если

а а"

и если элементы 1 и 2 не содержатся оба либо в а, либо в а", то легко видеть, что

/х(а,7г) = {р(аУ) + 1) й (/(«>") + 1) й {0}

для подходящих перестановок тг и тг", где /х + 1 обозначает мультимножество, получаемое в результате прибавления 1 к каждому элементу /х (см. упр. 7). С другой стороны, если и эле.мент 1, и элемент 2 находятся в а, имеем

/х(а, тг) = {р(а, тг) -f е) Ы (/х(а", тг") -f 1) Ы {0},

где fj. + е обозначает какое-нибудь мультимножество, получаемое в результате прибавления 1 к некоторы.м элементам и О - к остальным. Аналогичная формула справедлива и в том случае, если элементы 1 и 2 находятся в а". Будем говорить, что мультимножество /xi мажорирует р, если и /xi, и /хг содержат равное число элементов и если к-й в порядке убывания элемент рх больше к-то в порядке убывания элемента /хг для всех к или равен ему. Определим р{а) как мажоранту р{а,тт) по всем перестановкам тг в том смысле, что р{а) мажорирует /х(о:,7г) при всех тг и р(а) = /х(а,тг) при некотором тг. Приведенные выше формулы показывают, что

/(□) = 0, КО) = (/Да) +1) й (/(«") +1) й{0};

а"

следовательно, /х(а) есть мультимножество всех расстояний от корня до внутренних узлов а.

Если читатель уследил за ходом наших рассуждений, ему должно быть ясно, что теперь мы готовы доказать теорему Кислицына (6). Поскольку Wt(n) меньше или равно п - 1 плюс t - I наибольших элементов /х(а), где а - любое дерево, используемое при сортировке посредством выбора из дерева, то можно считать а полным бинарным деревом с п внешними узлами (см. раздел 2.3.4.5), причем

;x(a) = {[lglJ,Llg2J,...,[lg(n-l)J}

= {ng21-l,rig31-l,...Jlgnl-l}. (10)

Мы получим формулу (6), если рассмотрим -1 наибольших элементов этого мультимножества.

Теорема Кислицына дает хорошую верхнюю оценку для Wt{n); Кислицын отметил, что Уз{5) = б < 13(5) = 7, но не смог найти в общем случае оценку для Vt{n), лучшую, чем для Wt{n). Это было сделано А. Хадьяном (А. Hadian) и М. Собелем (М. Sobel), которые использовали выбор с замещением вместо выбора из дерева (см. раздел 5.4.1). Выведенная ими формула [Univ. of Minnesota, Dept. of Statistics Report 121 (1969)],

Vt{n)<n-t+it-l)\\g{n + 2-t)], n>t, (11)

отличается от формулы Кислицына тем, что каждый элемент суммы в (6) заменен наименьшим элементом.

Теорему Хадьяна и Собеля (11) можно доказать, воспользовавшись следующей схемой. Сначала сформируем бинарное дерево для турнира с выбыванием п - t + 2 элементов (участников), что потребует п - t + 1 сравнений. Наибольший элемент превосходит n-t+1 других элементов, поэтому он не может быть -м в порядке убывания. Заменим его во внешнем узле дерева одним из - 2 элементов, оставшихся в резерве, и найдем наибольший элемент из образовавшегося набора n-t-f-2 элементов; это требует не более lg(n -f- 2 - )] сравнений, поскольку придется заново вычислить только один путь в дереве. Повторим эту операцию в общей сложности t-2 раз - по одному разу для каждого элемента из резерва. Наконец, заменим текущий наибольший элемент элементом - оо и определим наибольший из оставшихся п + 1 - t элементов; для этого потребуется не более lg(n + 2 - t) - 1 сравнений, и -й в порядке убывания элемент исходного множества попадет в корень дерева. Суммировав число сравнений, получаем выражение (11).

Разумеется, мы должны заменить t на п--1 - t в правой части соотношения (11), если п+1-t дает лучшее значение (как при п = б и = 3). Как ни странно, но эта формула дает для 7(13) меньшую оценку, чем для б(13). Верхняя оценка в (И) точна для п < б, но когда п и t становятся большими, можно получить значительно лучшие оценки для Vt{n).

Например, можно использовать следующий изящный метод (принадлежащий Дэвиду Г. Дорену (David G. Doren)), чтобы показать, что 14(8) < 12. Обозначим элементы через Хх,... ,Х. Сначала сравним Хх:Х2 и Хз:Х, а затем - двух "победителей" между собой; проделаем то же самое для пар XsiX и Xy-.Xs и "победителей" этих пар. Переименуем элементы так, чтобы получить Хх < Х2 < Х4 > Хз, Х5 < Хб < Xs > Хт, затем сравним Х2:Хб; в силу симметрии положим Х2 < Хб, поэтому получим конфигурацию