Симметрично Симметрично

Рис. 42. Процедура выбора второго в порядке убывания элемента из {Xi,X2,X3,Xi,Хь, Хв}, при которой используется в среднем б сравнений. Каждая "симметричная" ветвь идентична своему собрату, однако имена переставлены соответствующим образом. Во внешних узлах записано "j к", если известно, что Xj - второй, & Xk - наибольший элемент; число перестановок, приводящих к этому узлу, записано непосредственно под ним.

Пусть Vt (я) - минимальное среднее число сравнений, необходимых для определения t-ro элемента в порядке убывания из п элементов. В табл. 2 показаны точные значения для малых п, вычисленные Д. Хоэем.

Р. У. Флойд (R. W. Floyd) в 1970 году обнаружил, что для поиска медианы п элементов может потребоваться в среднем всего п -Ь 0(n/logn) сравнений. Хе (Не) и Р. Л. Ривест (R. L. Rivest) спустя несколько лет уточнили этот результат и сформулировали изящный алгоритм доказательства того, что

Vt(n) <п + mm{t, n-t) + 0{у/пlogn).

(16)

(См. упр. 13 и 24.)

Используя несколько отличный подход, который основан на обобщении построения Собеля при t = 2, Дэвид У. Матула (David W. Matula) [Washington Univ. Tech. Report AMCS-73-9 (1973)] показал, что

Vtin) <n-i-t\\gt]{ll-i-\n\nn).

(17)

Таким образом, для фиксированного t средний объем вычислений может быть снижен до я -Ь O(loglogn) сравнений. Изящная нижняя оценка Vt{n) представлена в упр. 25.

Задачи сортировки и поиска представляют собой частные случаи более общей задачи поиска перестановки п заданных элементов, которая имеет заданное частич-

Таблица 2

МИНИМАЛЬНОЕ СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ ПРИ ВЫБОРЕ

ное упорядочение. В работе А. С. Yao, SICOMP 18 (1989), 679-689, показано, что если частичное упорядочение задано ациклическим диграфом G на п вершинах с к связанными компонентами, то минимальное число сравнений, необходимых для разрешения проблемы, всегда равно 0 (ig[n\/T{G)) +п-к), как в худшем случае, так и в среднем, где T{G) - суммарное число частично упорядоченных составляющих в перестановках (число топологических сортировок в G).

УПРАЖНЕНИЯ

1. [15] Почему в турнире Льюиса Кэррола (см. рис. 39 и 40) игрок 13 выбывает, несмотря на то что он выиграл свой матч в третьем туре?

► 2. [М25] Докажите, что после того, как найден с помощью последовательности сравнений t-й элемент в порядке убывания из п элементов, также известно, какие t - 1 элементов больше него и какие п - t элементов меньше.

3. [20] Докажите, что Щп) > Vt{n - 1) и Wt{n) > Wt(n - 1) при 1 < t < п.

► 4. [М25] (Ф. Фюснегер (F. Fussenegger) и Г. Н. Габов (Н. N. Gabow).) Докажите, что Wtin) >nt+ [Ign].

5. [10] Докажите, что \¥з{п) < Уз(п) -Ь 1.

► 6. [М26] (Р. У. Флойд.) Дано п различных элементов {Al,..., Х„} и набор отношений Хг < Xj для некоторых пар {i,j). Нужно найти второй в порядке убывания элемент. Элемент Xi не может быть вторым, если известно, что Xi < Xj и Х, < Хк при j / к, поэтому его можно исключить. В результате отношения будут иметь вид

>

а именно - образуется т групп элементов, которые можно представить мультимножеством {hth, . ,1т}; j-я группа содержит lj +1 элементов, об одном из которых известно, что он больше остальных. Например, изображенная конфигурация может быть описана мультимножеством {0,1,2,2,3,5}; если ни одно отношение не известно, то имеем вектор из п нулей.

Пусть f{l\ ,h,.--,lm) - минимальное число сравнений, необходимых для определения второго элемента такого частично упорядоченного множества. Докажите что

/(/1,/2,...,/ш) = ш-2 + П§(2 + 2=+----Ь2")1.

[Указание. Покажите, что наилучшая стратегия всегда состоит в том, чтобы сравнивать наибольшие элементы двух самых маленьких групп, пока т не будут сведены к единице; используйте индукцию по Zi + /2 + • • • + т + 2т.]

7. [М20] Докажите (8).

8. [М21 ] Формула Кислицына (6) основана на сортировке посредством выбора из дерева, использующей полное бинарное дерево с п внешними узлами. Может ли выбор из дерева, основанный на некотором другом дереве, дать лучшую оценку для каких-нибудь t и п?

► 9. [20] Нарисуйте дерево сравнений, чтобы найти медиану пяти элементов не более чем за шесть шагов, используя метод выбора с замещением Хадьяна и Собеля [см. (11)].

10. [35] Покажите, что медиана семи элементов может быть найдена не более чем за десять шагов.

11. [38] (К. Ношита (К. Noshita).) Покажите, что медиана девяти элементов может быть найдена не более чем за 14 шагов, из которых первые семь идентичны методу Дорена.

12. [21] (Хадьян (А. Hadian) и Собель (М. Sobel).) Докажите, что Уз{п) < Уз{п- 1)+2. [Указание. Начните с удаления наименьшего из {Х1,Х2,Хз,Ха}.]

► 13. [НМ28] (Р. У. Флойд.) Покажите, что если начать с нахождения медианы {Xi,..., Х„2/з} с помощью рекурсивно определенного метода, то можно найти медиану {Xi,..., Хп}, выполнив в среднем п--0(71 logn) сравнений.

► 14. [20] (М. Собель (М. Sobel)).) Пусть Ut{n) - минимальное число сравнений, необходимых для поиска t наибольших из п элементов, если не важен их взаимный порядок. Покажите, что f/2(5) < 5.

15. [22] (А. Пол (1. Pohl).) Предположим, что нас интересует минимизация объема памяти, а не времени. Какое минимальное количество слов памяти требуется для вычисления t-ro из п элементов, если каждый элемент занимает одно слово и элементы вводятся в особый регистр по одному?

► 16. [25] (И. Пол.) Покажите, что можно найти одновременно максимум и минимум множества из п элементов, использовав не более [п] - 2 сравнений, и это число не может быть уменьшено. [Указание. Любая стадия такого алгоритма может быть представлена четверкой (а, Ь, с, d), где а элементов вообще не сравнивались, b элементов выигрывали, но никогда не проигрывали, с проигрывали, но никогда не выигрывали, d как выигрывали, так и проигрывали. Постройте подходящего соперника.]

17. [20] (Р. У. Флойд.) Покажите, что можно выбрать к наибольших и I наименьших элементов множества из п элементов, использовав не более [п] -k-l+n+i-k<j<n П§ Л + i;„+i-i<i<„ fig Л сравнений.

18. [М20] Если бы в доказательстве теоремы L использовались группы размером 5, а не 7, то какая бы получилась теорема?

19. [М42] Расширьте табл. 2 для п = 8.

20. [М7] Каково значение асимптотического выражения для Vtin) - п при п -> оо?

21. [32] (П. В. Раманан (Р. V. Ramanan) и Л. Хьяфил (L. Hyafil).) Докажите, что Wt{2 + 2*=+i-t) < 2 + 2+~ + {t-l){k-l), если k>t>2; покажите также, что имеется равенство для бесконечно больших к и t, используя результаты упр. 4. [Указание. Постройте два дерева турниров с выбывгшием и разумно скомбинируйте полученные результаты.]

22. [24] (Дэвид Г. Киркпатрик (David G. Kirkpatrick).) Покажите, что в случае 4 • 2* < п-1 < 5-2° верхняя оценка (11) для Уз{п) может быть следующим образом уменьшена на 1. (i) Образуйте четыре "дерева с выбыванием" размером 2". (ii) Найдите минимальный из четырех максимумов и удалите все 2" элементов соответствующего дерева. (Ш) Используя