AOP_Tom3 (1021738), страница 10
Текст из файла (страница 10)
Разобьем элементы на 29+ 1 групп по 7 элементов и отсортируем каждую группу. Это потребует ие более 13(29 + 1) сравнений. Шаг 2. Найдем медиану из 29+ 1 медиан, полученных на шаге 1, и обозначим ее через х. Проведя индукцию по о, замечаем, что это требует не более $'+, (29+ 1) < 309 — 148 сравнений, Шаг 3. Теперь п — 1 элементов, отличных от х, разбиваются на трн множества (рнс.
41): 40+ 3 элементов, о которых известно, что они больше х (область В); 49+ 3 элементов, о которых известно, что они меньше х (область С); 69 элементов, отношение которых к х неизвестно (области А, П). Выполнив дополнительно 49 сравнений, можно в точности сказать, какие элементы из областей А и 0 меныпе я. (Сначала сравниваем я со средним элементом каждой тройки.) Шаг 4. Теперь при некотором г мы нашли г элементов, больших, чем х, а также х и п — 1 — г элементов, меньших, чем я. Егли 1 = г + 1, то х и будет ответом; если 1 < е -ф.
1, то нужно найти 1-й элемент в порядке убывания из г больших элементов; если 1 > г + 1, то нужно найти (1 — 1 — г)-й элемент в порядке убывания из и — 1 — г меньших элементов. Суть дела в том, что и г, и и — 1 — г меньше или равны 109+ 3 (раз .р областей А и П плюс В или С). Инлукцией по 9 выводим, что этот шаг требует не более 15(109 + 3) — 163 сравнений. Область А Область В Область С Область 0 Рис. 41. Алгоритм выбора Райвеста и Таржана (л = 4). Общее число сравнений оказывается не больше 13(2п + Ц + 399 — 148 + 4с7+ 15(19л + 3) — Р33 = 15(149 — 6) — 163.
Так как мы начали с не менее 14о — 6 элементов, доказательство завершено. 1 Из теоремы Е следует, что время выбора всегда может быть линейным, а именно — что !'ч(п) = 0(п), Метод, использованный в этом доказательстве, не вполне совершенный, поскольку на шаге 4 теряется значительное количество информации. Более глубокий анализ задачи приводит к уточнению оценок границ. (См., например, работу А.
БсЬбпЬайе, М. Расегэоп, Х. Р!ррепйег, Х Сошр. Буэ. Яп1 13 (1976), 184-199, в которой доказано, что максимальное число сравнений, необходимых для поиска медианы, не превосходит 3п+ 0(п, !о8 п)г74. По поводу нижней оценки числа сравнений обратитесь к упр. 23; в нем же приведены ссылки на более поздние источники.) Среднее число. Вместо минимизации максимального числа сравнений можно искать алгоритм, который минимизирует среднее число сравненин, предполагая, что порядок случаен. Как обычно, эта задача значительно труднее и она все еще не решена даже в случае ! = 2. Клод Пикар (С!апс!е Р!сагс!) упомянул о ней в своей книге ТЛеог1е с!еэ Опал!!оппшгеэ (1965).
Широкое исследование было предпринято Милтоном Собелем (М!1!оп ВоЬеч) [(чшс. о(М!ппеэоса, Пера о! 8гаНэбсэ, герог! 113 (ччоч ешЬсг, 1968)); Весне Етапоа!эе д'Аигошаг!9пе, 1п1огшас!9пе е! ВесЛегсЛе Орегаь!оппеПе 6, В;3 (Песет!чег, 1972), 23 — 68). Собель построил процедуру, графически представленную на рис.
42, которая находит второй в порядке убывания элемент из шести элементов, в среднем используя только 6-„' сравнений. В худшем случае требуется восемь сравнений, и это хуже, чем Ъг(6) = 7. Предпринятый Д. Хозем (П. Ноеу) продолжительный компьютерный эксперимент показал, что в наилучшей процедуре репчения этой задачи используется в среднем 6 —, сравнений, если ограничить эксперимент семью сравнениями.
Таким га образом, вероятно, никакая процедура нахождения второго из шести элементов пе будет оптимальной одновременно и как миннмаксная, и как минимизирующая среднее число сравнений. Рне. 42. Процедура выбора второго в порядке убывания элемента нз (Х1, Хэ, Хэ., Л 4, Л 4, Хе), прв которой используется в среднем б-' сравнений. Каждая "симметричная" ветвь идентична своему собрату, однако имена перестввлены соответствующим образом.
Во внешних узлах записано "У й", если известно, что Մ— второй, а Хь — наибольший элемент; число перестановок, приводящих к этому узлу, записано непосредственно под ннм. Пусть Г4(п) — минимальное среднее число сравнений, необходимых для определения 1-го элемента в порядке убывания из и элементов, В табл. 2 показаны точные значения для малых пэ вычисленные Д.
Хозем. Р. У. флойд (Н. 1з'. Р!оуг!) в 1970 голу обнаружил, что для поиска медианы и элементов может потребоваться в среднем всего зп+ О(пэгэ!ойп) сравнений. Хе (Не) и Р. Д. Ривест (Н. 1. Н!1ев1) спустя несколько лет уточнили этот результат и сформулировали изящный алгоритм доказательства того, что Г1(п) < и+ 1гйп(1, и — 1) + О(зlи1обп). (16) (См. упр. 13 и 24.) Используя несколько отличный подход, который основан на обобщении построения Собеля при ! = 2, Дэвид У.
Матула (Пну!4! Ж. У1агп!а) (ЪЪвэЫпйтоп Ншш ТесЬ. Нерогг АМСБ-73-9 (1973)] показал, что Ъ~4(п) < и + 1(131)(11 + 1п!пи). (17) Таким образом, длн фиксированного ! средний объем вычислений может быть снижен до и + О(1о31ойп) сравнений. Изящная нижняя оценка г'1(п) представлена в упр.
25. Задачи сортировки н поиска представляют собой частные случаи более общей задачи поиска перестановки и заданных элементов, которая имеет заданное частич- Таблица 2 МИНИМАЛЬНО17 СРЕДНЕЕ ЧИСЛО СРАВНЕНИЯ НРИ ВЫБОРЕ и Р 1(71) 1' г(п) 1 3(п) 1 4(п) 1 5(п) 1 б(п) 1 7(п) 23 3 4 4 0— 15 7 — ' 13 9— 33 105 4 15 6- ! г 7 —. 140 110 5!3 15 7— 7 13 3— 500 530 6.1 530 5 110 ное упорядочение. В работе А.
С. Уао, 81СОМР 18 (1989), 679-689, показано, что если частичное упорядочение задано ациклическим диграфом С на п вершинах с й связанными компонентами, то минимальное число сравнений, необходимых для разрешения проблемы, всегда равно О(!8(п1/Т(С)) +и — й), как в худшем случае, так н в среднем, где Т(47) — суммарное число частично упорядоченных составляющих в перестановках (число топологических сортнровок в С).
УПРАЖНЕНИЯ 1. (15) Почему в турнире Льюиса Кэррола (см. рнс. 39 и 40) игрок 15 выбывает, несмотря на то что он выиграл свой матч в третьем туре? 2. (М25) Докажите, что после того, как найден с помошью последователыюсти сравнений 1-й элемент в порядке убывания из и элементов, также известно, какие С вЂ” 1 элементов больше него и какие и — г элементов меньше. 3. (25) Докажите, что И(п) > И(п — 1) и И'1(п) > И'!(и — 1) при 1 < 1 < и.
4. (М25) (Ф. Фюснегер (Р. Е7155евеббег) и Г. Н. Габон (Н. 4Ч. СаЬ04ч).) Докажите„что И1(п) >'л '1+ !13п1 5. (!О) Докажите, что И73(п) < 173(п) -1-1 6. (М25) (Р. У. Флойд.) Дано и различных элементов (Х1,..., Х„) и набор отношений х1 < х„длл некоторых пар (г„у). нужно найти второй в порядке убывания элемент. Элемент Х! не может быть вторым, если известно, что Х; < Х! и Х1 < ХУ при 5 ,-ь 15, поэтому его можно исключить. В результате отношения будут иметь вид а именно — образуется т групп элебгентов, которые бюжно представить мультимножеством (11, 13,...,1,0); 1'-я группа содержит 1! + 1 элементов, сб одном из которых известно, что он больше остальных.
Например, изображенная конфигурация может быть описана м1льтимножеством (О, 1, 2, 2, 3, 5); если ни одно отношение не известно, то имеем вектор из и нулей. Пусть г" (11, 13,, 1 7) . — минимальное число сравнений, необходимых для определения второго элемента такого частично упорядоченного мчожества. Докажит1 чтс П11,13,..., 1ж) = гп — 2 + (18(211 + 2 г + ° + 21 )1.
[Указание. Покажите, что наилучшая стратегия всегда состоит в том, чтобы сравнивать наибольшие элементы двух самых маленьких групп, пока ш не будут сведены к единице; используйте индукцию по !г + !г + .. + ! ~ + 2иг.] 7, [М20] Докажите (8). В. [М2! [ Формула Кислицына (б) основана на сортировке посредством выбора из дерева, использующей полное бинарное дерево с и внешними узлами. Может ли выбор из дерева, основанный на некотором другом дереве, дать лучшую оценку для каких-нибудь Г и и? 9. [20[ Нарисуйте дерево сравнений, чтобы найти медиану пяти элементов не более чем за шесть шагав, используя метод выбора с замещением Хэдьяна и Собеля [см.
(11)[. 10. [25] Покажите, что медиана семи элементов может быть найдена не более чем за десять шагов. 11. [Яд[ (К. Нашита (К. ХоэЬ1еа).) Покажите, что медиана девяти элементов может быть найдена не более чем за 14 шагов, из которых первые семь идентичны методу Дорена. 12. [21] (Хадьян (А. Найал) и Сабель (М.
ЯоЬе1).) Докажите, что Уэ(и) < Ъз(и — 1) + 2. [Указание. Начните с удаления наименьшего из (Хг, Хг, Хэ, Х<И э 13. [НМ22] (Р. У. Флойд.) Покажите, что если начать с нахождения медианы (Х,, Х„ггэ) с помощью рекурсивно определенного метода, то можно найти медиану (Хм..., Х„), выполнив в среднем 1и+ 0(и~~~ 1об и) сравнений. э 14. [20[ (М. Сабель (М. ЯоЬе!)).) Пусть 1?г(и) — минимальное число сравнений, необходимых для поиска 1 наибольших из и элементов, если не важен их взаимный порядок. Покажите, что??г(5) < 5.
15. [22] (А. Пол (!. РоЫ).) Предположим. что нас интересует минимизация объема памяти, а не времени. Какое минимальное количество слов памяти требуется для вычисления 1-го из и элементов, если каждый элемент занимает одно слово и элементы вводятся в особый регистр по одному? э 16. [25] (И. Пол.) Покажите, что можно найти одновременно максимум и минимум множества из и элементов, использовав не более [1и] — 2 сравнений, и это число не может быть уменьшено.
[Указание. Любая стадия такого алгоритма может быть представлена четверкой (а, 5, с, 0), где а элементов вообще не сравнивались, 5 элементов выигрывали, но никогда не проигрывали, с проигрывали, но никогда не выигрывали, 4 как выигрывали, так и проигрывали. Постройте подходящего соперника.] 17.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
