(Теперь Xl и Xg вышли из игры и мы должны найти третий в порядке убывания элемент из {Х2,..., Ау}.) Сравним ХггХу и отбросим меньший; в худшем случае получим Х2 < Хт. Найдем третий в порядке убывания элемент из

Это можно сделать еще за Уз (5) - 2 = 4 шага, так как процедура для Уз (5) = 6 в (11) начинается со сравнения двух непересекающихся пар элементов.

Можно использовать другие трюки подобного вида и получить результаты, показанные в табл. 1, но никакого общего метода до сих пор не существует. Значения, указанные для ¥4(9) = Уб(9) и У5(10) = Уб(10), являются оптимальными, как доказано в работе W. Gasarch, W. Kelly, W. Pugh, SIGACT News 27,2 (June, 1996), 88-96, в которой использовался компьютерный поиск.

Хорошая нижняя оценка для задачи выбора в случае, когда t мало, получена в работе Дэвида Г. Киркпатрика (David G. Kirkpatrick) [JACM 28 (1981), 150-165]: если 2 <t < {п + 1)/2, получим

t-2 г

n-t + 2

t + j

Vtin) >n + t

В своей диссертации [Ph. D. thesis, U. of Toronto, 1974] он доказал, что Уз(я) <я--1--

(12)

(13)

эта нижняя оценка соответствует нижней оценке, что следует из (12) при Ig 74% всех целых чисел я и превосходит (12) не более чем на 1. Выполненный Киркпатриком анализ дает основание предположить, что равенство в (13) будет соблюдаться и для всех п > 4, но Ютта Эстерброк (Jutta Eusterbrock) отыскала удивительный противоречащий этому пример Уз (22) = 28 [Discrete Applied Math. 41 (1993), 131-137]. Несколько улучшенная нижняя оценка для больших значений t найдена С. У. Бентом (S. W. Bent) и Дж. У. Джоном (J. W. John) (см. упр. 26):

Vtin)>n + m-2\y/m], т = 2 +

lg((")/(n+l-t))]. (14)

Эта формула доказывает, в частности, что

Vanin) > fl-ЬQlg--ь(l-Q)lg--)я-ьO(). \ а 1 - а/

(15)

Линейный метод. Если я нечетно и t = [я/2], то t-й в порядке убывания (и t-й в порядке возрастания) элемент называется медианой. В соответствии с (11) мы можем найти медиану я элементов за и яlgя сравнений, но это лишь приблизительно вдвое быстрее сортировки, хотя в таком случае нам нужно значительно меньше информации. В течение нескольких лет объединенные усилия множества исследователей были направлены на улучшение формулы (11) для больших значений t и я; наконец, в 1971 году Мануэль Блум (Manuel Blum) открыл метод, требующий только 0(яloglogn) шагов. Подход Блума к этой задаче дал толчок к

Таблица 1

ОЦЕНКИ Vt(n) ПРИ МАЛЫХ п

* Для этих случаев в упр. 10-12 приводятся схемы, позволяющиеулучшить (И). •* См. К. Noshita, Tr&ns. of the lECE of Japan E59,12 (December, 1976), 17-18.

развитию нового класса методов, который привел к следующему построению (см. R. Rivest, R. Tarjan, J. Сотр. and Sys. Sci. 7 (1973), 448-461).

Теорема L. Vt{n) < 15n - 163 яри 1 <t <n, когда n > 32.

Доказательство. Когда n мало, теорема тривиальна, так как Vt{n) < S(n) < lOn < 15я - 163 для 32 < я < 2°. Добавив самое большее 13 фиктивных элементов -оо, можно считать, что п = 7{2q + 1) при некотором целом q > 73. Теперь для выбора t-ro в порядке убывания элемента воспользуемся следующим методом.

Шаг 1. Разобьем элементы на 2? + 1 групп по 7 элементов и отсортируем каждую группу. Это потребует не более 13(2? + 1) сравнений.

Шаг 2. Найдем медиану из 2? + 1 медиан, полученных на шаге 1, и обозначим ее через X. Проведя индукцию по q, замечаем, что это требует не более Vq+i{2q + 1) < 30q - 148 сравнений.

Шаг 3. Теперь я - 1 элементов, отличных от х, разбиваются на три множества (рис. 41):

4 + 3 элементов, о которых известно, что они больше х (область В); 4 + 3 элементов, о которых известно, что они меньше х (область С); 6q элементов, отношение которых к х неизвестно (области А, D).

Выполнив дополнительно 4q сравнений, можно в точности сказать, какие элементы из областей А и D меньше х. (Сначала сравниваем х со средним элементом каждой тройки.)

Шаг 4. Теперь при некотором г мы нашли г элементов, больших, чем х, а также х и я - 1 - г элементов, меньших, чем х. Если t = г + 1, то х и будет ответом; если t < 1 + 1, то нужно найти t-й элемент в порядке убывания из г больших элементов; если t > г + 1, то нужно найти (t-l-r)-u элемент в порядке убывания из я - 1 - г меньших элементов. Суть дела в том, что иг, ия - 1-г меньше или равны lOq + 3 (раз..:ср областей А и D плюс В или С). Индукцией по q выводим, что этот шаг требует не более 15(10? + 3) - 163 сравнений.

Область А Область В

29+1

Область с Область D Рис. 41. Алгоритм выбора Райвеста и Таржана (5 = 4).

Общее число сравнений оказывается не больше

13(2? + 1) + ЗОд - 148 + 4д + 15(10? + 3) - 163 = 15(14? - 6) - 163.

Так как мы начали с не менее 14? - 6 элементов, доказательство завершено.

Из теоремы L следует, что время выбора всегда может быть линейным, а именно - что Vt{n) = 0{п). Метод, использованный в этом доказательстве, не вполне совершенный, поскольку на шаге 4 теряется значительное количество информации. Более глубокий анализ задачи приводит к уточнению оценок границ. (См., например, работу А. Schonhage, М. Paterson, N. Pippenger, J. Сотр. Sys. Sci. 13 (1976), 184-199, в которой доказано, что максимальное число сравнений, необходимых для поиска медианы, не превосходит 3n--0(nlogn)/. По поводу нижней оценки числа сравнений обратитесь к упр. 23; в нем же приведены ссылки на более поздние источники.)

Среднее число. Вместо минимизации максимального числа сравнений можно искать алгоритм, который минимизирует среднее число сравнений, предполагая, что порядок случаен. Как обычно, эта задача значительно труднее и она все еще не решена даже в случае t = 2. Клод Пикар (Claude Picard) упомянул о ней в своей книге Theorie des Questionnaires (1965). Широкое исследование было предпринято Милтоном Собелем (Milton Sobei) [Univ. of Minnesota, Dept. of Statistics, report 113 (November, 1968)]; Revue Frangaise dAutomatique, Informatique et Recherche Operationnelle 6,R-3 (December, 1972), 23-68].

Собель построил процедуру, графически представленную на рис. 42, которая находит второй в порядке убывания элемент из шести элементов, в среднем используя только б сравнений. В худшем случае требуется восемь сравнений, и это хуже, чем 2(6) = 7. Предпринятый Д. Хоэем (D. Ноеу) продолжительный компьютерный эксперимент показал, что в наилучшей процедуре решения этой задачи используется в среднем б сравнений, если ограничить эксперимент семью сравнениями. Таким образом, вероятно, никакая процедура нахождения второго из шести элементов не будет оптимальной одновременно и как минимаксная, и как минимизирующая среднее число сравнений.