Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 58
Текст из файла (страница 58)
ЪЧ. Вепз) и Дж. У. Джоном (Л. %. ЛоЬп) (см. упр. 26): = 2+ ~18 ((",)/(. +1- !))1 Эта формула доказывает, в частности, что 1 1 У„„(л) > (1 + а !8 — + (1 — а) !8 — 1 и + 0 (з/л ) . а 1 — а/ (15) Линейный метод. Если и нечетно и ! = )л/2), то $-й в порядке убывания (и 1-й в порядке возрастания) элемент называется медианой. В соответствии с (П) мы можем найти медиану л элементов за ж ~л !8и сравнений, но это лишь приблизительно вдвое быстрее сортировки, хотя в таком случае нам нужно значительно меньше информации.
В течение нескольких лет объединенные усилия множества исследователей были направлены на улучшение формулы (11) для больших значений ! и и; наконец, в 1971 году Мануэль Блум (Манне! Ваш) открыл метод, требующий только 0(и !ой!ой и) шагов. Подход Блума к этой задаче дзл толчок к Таблица 1 ОЦЕНКИ И(п) ПРИ МАЛЫХ и и Ь'~(п) 13(п) Уз(п) Т'1(п) Рэ(п) Ь2(п) 15(п) ~е(п) ьз(п) ьш(в) 1 0 2 1 1 3 2 3 2 4 3 4 4 5 4 6 6 6 5 7 8 7 6 8 10 8 7 9 11 9 8 Ы 12 10 9 12 14 3 6 4 8 7 5 10 10 8 12 12 11 14 14 14 15 16'* 16'" 6 9 7 12 11 8 15 14 12 9 ' Дпя этих случаев в упр.
10-12 приводятся схемы, позволяющие улучшить (11). * См. К, 1зоеЪйа, угала оГ 15е 1ЕСЕ огуарап Е59,12 (11есещЪег, 1976), 17-18. развитию нового класса методов, который привел к следующему построению (см. В. В(теэс, В. Тат)ап, .7. Сотр. апб Яуе. Ясй 7 (1973), 448-461). Теорема Ь. 9~(п) < 15п — 163 прп 1 < 1 < и, когда и > 32.
4е + 3 элементов, о которьгх известно, что они больше х (область В); 4е+ 3 элементов, о которых известно, что они меньше х (область С); 6» элементов, отношение которых к к неизвестно (области А, Э). Выполнив дополнительно 49 сравнений, можно в точности сказать„какие элементы из областей А и Э меньше х. (Сначала сравниваем к со средним элементом каждой тройки.) Шаг 4.
Теперь при некотором г мы нашли г элементов, больших, чем к, а также к и и — 1 — г элементов, меньших, чем х. Вели 1 = г + 1, то х и будет ответом; если 1 < ~ ч-1, то нужно найти 1-й элемент в порядке убывания из г больших элементов; если 1 > г + 1, то нужно найти (1 — 1-г)-й элемент в порядке убывания нз и — 1 — г меньших элементов. Суть дела в том, что и г, и и — 1 — г меньше или равны Щ+ 3 (раз кр областей А и Э плюс В или С), Ицпукцией по е выводим, что этот шаг требует не более 15(10п+ 3) — 163 сравнений.
Докаэашельстео. Когда и малб, теорема тривиальна, так как К~(п) < Я(п) < 10п < 15п — 163 для 32 < и < 2'е. Добавив самое большее 13 фиктивных элементов -сю, можно считать, что и = 7(29 + 1) при некотором целом и > 73. Теперь для выбора 1-го в порядке убывания элемента воспользуемся следующим методом. Шаг 1. Разобьем элементы на 2е+ 1 групп по 7 элементов и отсортируем каждую группу. Это потребует не более 13(2е + 1) сравнений. Шаг 2.
Найдем медиану из 2е+ 1 медиан, полученных на шаге 1, и обозначим ее через к, Проведя индукцию по е, замечаем, что это требует не более Ъг+з(20+ 1) < 30е — 148 сравнений. Шаг 3. Теперь и — 1 элементов, отличных от х, разбиваются на три множества (рис, 41): Область А Область В за+1 Область О Область О Рис.
41. Алгоритм выбора Рлйвеста и Таржана (4 = 4). Общее число сравнений оказывается не больше 13(24+ 1) + 304 — 148+ 44 + 15(104 + 3) — 163 = 15(144 — 6) — 163, Так как мы начали с не менее 149 — б элементов, доказательство завершено.
$ Из теоремы 1 следует, что время выбора всегда может быть линейным, а именно — что 1а(п) = 0(п). Метод, использованный в этом доюьзательстве, не вполне совершеннь|й, поскольку на шаге 4 теряется значительное количество информации. Волее глубокий анализ задачи приводит к уточнению оценок границ. (См., например, работу А.
ЗсЬоп1шйе, М. Рабегэоп, ь(. Р1ррепйег, Х Сотр. Яуэ. Ясй 13 (1976), 184-199, в которой доказано, что максимальное число сравнений, необходимых для поиска медианы, не превосходит Зп+ 0(п 1об и) э~". По поводу нижней оценки числа сравнений обратитесь к упр. 23; в нем же приведены ссылки на более поздние источники.) Среднее число. Вместо минимизации лсакспмальяого числа сравнений можно искать алгоритм, который минимизирует среднее число сравнений, предполагая, что порядок случаен. Как обычно, эта задача значительно труднее и она все еще не решена даже в случае т = 2.
Клод Пикар (С1апс)е Р1сагд) упомянул о ней в своей книге ТБеог!е дел Яиеэболпаиел (1965), Широкое исследование было предпринято Милтоном Собелем (Мйбоп ЯоЬес) (Нп1т. о1 Мпшеэога, Перс. о1 Ясаг1эс1сэ, герогс 113 (Хотеп|Ьег, 1968)]; Ие~ пе ггапдшэе д(4игота119ие, 1пГогтапдие ес Весбегсйе Орегагюппе))е 6, В-3 (ВесешЬег, 1972), 23-68). Сабель построил процедуру, графически представленную на рис. 42, которая находит второй в порядке убывания элемент из шести элементов, в среднем используя только 6 з сравнений. В худшем случае требуется восемь сравнений, и это хуже, чем 1т(6) = 7.
П1юдпринятый Д. Хозем (П. Ноеу) продолжительный компьютерный эксперимент показал, что в наилучшей процедуре решения этой задачи используется в среднем бф сравнений, если ограничить эксперимент семью сравнениями. Таким образом, вероятно, никакая процедура нахождения второго из шести элементов не будет оптимальной одновременно и как минимаксная, и как минимизирующая среднее число сравнений. Рис, 42. Процедура выбора второ~о в порядке убывания элемента нз (Хп Хм Лз, Х», Х», Х»), прв которой нспальзуетсв в среднем б-' сравнений, Каждая "симметричная" ветвь идентична своему собрату, однако имена вереставленм соответствующим образом, Во внешних узлах записано "у й", если известно, что Х» — второй, а Х» — наибольший элемевт; число перестановок, приволяших к этому узлу, записано иепосредственно пад ввм.
Пусть 1'»(и) — минимальное среднее число сравнений, необходимых для определения 1-го элемента в порядке убывания из и элементов. В табл. 2 показаны точные значения для малых и, вычисленные Д, Хозем, Р. У. Флойд (В. %. Г1оус1) в 1970 году обнаружил, что для поиска медианы и элементов может потребоваться в среднем всего зп + 0(пзуз1ойп) сравнений. Хе (Не) и Р. Л. Ривест (К. Е.
К1тезс) спустя несколько лет уточнили этот результат и сформулировали изящный алгоритм доказательства того, что Г»(г») < и+ щ(п(1, и-1) + О(»/п)обп). (Рб) (См. упр. 13 и 24,) Используя несколько отличный подход, который основан на обобщении построения Собеля при $ = 2, Дэвид У. Матула (ПатЫ %. »Мазп1а) (%азЬ(пйсоп Вппс ТесЬ.
Верогс АМСЯ-73-9 (1973)) показал, что Р»(п) < и+т(191)(71+ 1п1пп). (17) Таким образом, для фиксированного 1 средний объем вычислений может быть снижен до а + О(!об 1окп) сравнений. Изящная нижияя оценка У»(п) представлена в упр. 25. Задачи сортировки и поиска представляют собой частные случаи более общей задачи поиска перестановки п заданных элементов, которая имеет заданное частич- Таблица 2 минимлльнОе среднее числО сРАВнений ОРН ВИБОРе и 1»»(п) 1»5(п) 1»5(п) 1»5(п) Рчэ(п) Рве(п) Рч»(п) 1 1 2 25 2 3 4 4 Ьз ЬН Ь б-.' 7— 7 иэ 5»0 3555 55О 3 Ь 4 15 7 7 »5 55 9135 4 61 509 35г»3 Ь 545 7»вЂ »4 нос упорядочение, Н работе А.
С. '5ао, 8»СОМР 18 (1989), 679-689, показано. что если частичное у»юрядочение задано ациклическим диграфом П на и вершинах с )с связанными компонентами, то минимальное число сравнений, необходимых для разрешения проблемы, всегда равно 8 (18(п)/Т(О) ) +и-б), как в худшем случае, так и в среднем, где 1'(с») — суммарное число частично упорядоченных составляющих в перестановках (число топологических сортировок в О). УПРАЖНЕНИЯ 1, (13»» Почему в турнире Льюиса Кэррола (см. рнс. 39 н 40) игрок 10 выбывает, несмотря на то что оп вьп»грал свой матч в третьем туре? 2. (Мйу) Докажите, что после того, как найден с помощью последовательности сравнений 1-й элемент в порядке убывания нз и элементов, также известна, какие 1 — 1 элементов больше него н какие и — 1 элементов меньше.
3. (20) Докажите, что 14(»5) > И»(»5 — 1) и И'»(и) > 1Р»(п — 1) при 1 <1 < и. 4. (Мйб) (Ф, Фюснегер (Р. Рошеаейбег) н Г. Н. Габов (Н. И. СаЬои).) Докажите, что И'(и) > и - 1 т ~18п» -1). б. (101 Докажите, что И'5(п) < Иэ(п) + 1. б. (Мйб) (Р. У. Флойд.) Дано и различных элементов (Х»,...,Х„) и набор отношений х» < х» лля некоторых пар (»,у). нужно найти второй в порядке убывания элемент. Элемент Х; не может быть вторым, если известно, что Х» < Х и Х; < Хь при у Р а» поэтому его можно исключить. В результате отношения будут иметь внд а именно — образуется»п групп элементов, которые можно представить мулам»множеством (1», 15,..., 1и); у-я группа содержит 1» + 1 элементов, об одном из которых известно, что он больше остальных.
Например, изображенная конфигурация может быть описана мультимножеством (О, 1,2,2, 3, Ь); если ни адно отношение не известно, то имеем вектор из и нулей. Пусть 7(1», 15,..., 1„,) --- мнн»»мш»ьное число сравнений, необходимых для определенна второго элемента такого частично упорядоченного мчожества. Докажите что У(1»,15,",1 ) = и — 2+ (18(2П+2" + "+2'")).
[Указание. Покажите, что наилучшая стратегия всегда состоит в том, чтобы сравнивать наибольшие элементы двух самых маленьких групп, нока ш не будут сведены к единице; используйте индукцию по (~ + (з + . + ! + 2ш.] Т. [Мйо] Докажите (8), 8. [М21] Формула Кислицына (б) основана на сортировке посредством выбора из дерева, использующей полное бинарное дерево с и внешними узлами. Может ли выбор из дерева, основанный на некотором другам дереве, дать лучшую оценку длв каких-нибудь ! и и? 9. [20] Нарисуйте дерево сравнений, чтобы найти медиану пяти элементов не более чем за шесть вшгов, используя метод выбора с замещением Хальяиа и Собеля [см.
(11)]. 10. [уб] Покажите, что медиана семи элементов может быть найдена не более чем за десять шагов. 11 [ув] (К. Ношита (К. НоэЬйа).) Покажите, что медиана девяти элементов может быть найдена не более чем за 14 шагов, нз которых первые семь ццентичны методу д и, 12. [2!] (Хадьян (А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
