Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 59
Текст из файла (страница 59)
Ныйал) и Сабель (М. БоЬе!),) Докажите, что !'1(п) < Ъз(п — 1) + 2. [Указание. Начните с удаления наименьшего из (Хм Хю Хз, Хз) ] ь 13. [НМ28] (Р. У. Флойд.) Покажите, что если начать с нахождения медианы (Хы..., Х„ыз) с помощью рекурснвно определенного метода, то можно найти медиану (Х~,..., Х„), выполнив в среднем зп+ 0(пи~ (об и) сравнений.
ь 14. [2д] (М. Собель (Ь4. ЯоЬе!)).) Пусть?А(п) — минимальное число сравнений, необходимых для поиска ! наибольших из и элементов, если не важен их взаимный порядок. Покажите, что Пз(5) < 5. 18. [88] (А. Пол (!. РоЫ).) Предположим, что нзс интересует минимизация объема памяти, а не времени. Какое минимальное количество слов памяти требуется для вычисления г-го из и элементов, если каждый элемент занимает одно слово и элементы вводятся в особый регистр по одному? ь 16. [25] (И. Пол.) Покажите, что можно найти одновременно максимум и минимум множества из и элементов, использовав не более [-и] — 2 сравнений, и это число не может з быть уменьшено. [Указание. Любая стадия такого алгоритма может быть представлена четверкой (а, Ь, с, и), где а элементов вообще не сравнивались, Ь элементов выигрывали, но никогда не проигрывалн., с проигрывали, но никогда не выигрывали, 8 как выигрывали, так и проигрывалн.
Постройте подходящего соперника.] 1?. [2Р] (Р. У. Флойд.) Покажите, что можно выбрать 1 наибольших н ! наименьших элементов множества из и элементов, использовав не более Цп[-к-(+2 4 ы <„[!8?]+ 7:.+, г<!<„[)бу] сравнений. 18. [МЗд] Если бы в доказательстве теоремы Ь использовались группы размером б, а ие?, то какая бы получилась теорема? 19, [М42] Расшнрьте табл. 2 для и = 8. 20. [М4?] Каково значение асимптотического выражения для Гз(п) — и при и -э оо? 21. [У2] (П.
В. Раманан (Р. Ч. Ващвпап) н Л. ХьяФнл (Ь. Нуаб)).) Докажите, что И',(2ь+ 2ь+' ') < 2э+2к ы '+(!-1)(к — 1), если?г > ! > 2; покажите также, что имеется равенство для бесконечно болыпнх й н г, используя результаты упр. 4. [Указание. Постройте два дерева турниров с выбыванием н разумно скомбинируйте пол! ~енные результаты.) 22.
[24] (Дзвид Г. Киркпатрик (ПагЫ 6. К(гйраййс$с).) Покажите, что в случае 4 ° 2ь < и-1 < 5.2" верхняя оценка (11) для Ъд(п) может быть следующим образом уменылена иа 1, (!) Образуйте четыре "дерева с выбыванием" размером 2". (8) Найдите минимальный из четырех максимумов и удалите все 2" элементов соот ~"тствующего дерева. (гй) Используя накопленную информацию, постройте одно дерево с выбыванием размером и — 1 — 2".
((т) Продолжайте, как при доказательстве (11). 23. [М49] Каково асимптотическое значение 1 ыщ (и) при и -+ аау 24. [НМ4д] Докажите, чта Г~(и) < и+1+ О(~/и(айи) при г < |и/2]. Указание. Покажите, что, испальзув столько сравнений, можно фактически найти и [à — Л!пи]-й, н [Г+ ~/) Ьги]-й элементы, восле чего легко выявляется 1-3.
ь 23. [МИ] (В. Кунта (Ж, Санга) п Дж. И. Муагро (Л. 1. Много).) Докаэките, что Ъ'а(и) > и + 1 — 2, если Г < [и/2], 26. [М83] (А. Шенхаж (А. ЯсЬбпЬайе), 1974.) (а) Докажите в обозначениях упр. 14, что (А(и) > ппп(2+ (А(п — 1),2+ Ц ~(гг — 1)) при и > 3. [Укозанае. Скопструнруйте соперника посредством уменьшения количества элементов с и до и — 1 до тех пор, пока частичное упорядочение ие будет состоять полностью нз компонентов вида ° или (Ь) Аналогично докажите, что (с(и) > ппо(2+ Ц(гг — 1),3+ (А ь(и — 1), 3+ (А(и — 2)) прп и > б, сконструировав соперника, который имеет дело с компонентами °, > . (с) Таким образом, гюлучим Ц(и) > и+ 1+ ппп(ии — 1)/2],1) — 3 прн 1 < г < и/2. [Неравенства н (а) и (Ь) относятся также к случаю, когда У илп й' замепнет (/, обеспечивая таким образом оптимальность определенных элементов в табл.
1.] ь 23. [М34] Рендомазороеакнмй соперник — это соперник, алгоритм поведения которого позволяет при принятии решения использовать подбрасывание монеты. а) Пусть А — рандомнзнрованный соперник и пусть Рг(1) — вероятность того, что А достигнет листа( данного дерева сравнений.
Покажите, что, если Рг(1) < р для всех 1, высота дерева сравнений > 13(1/р) . Ь) Проанализируйте поведение следующего соперника для выбора г-го по старшинству из и элементов, причем целочисленные параметры д и г будут выбраны позже. А1. Выбирается случайное множество Т, состоящее из 1 элементов; все (",) вариантов считаются равновероятными. (Будем считать, что обеспечивается условие, при котором 1 — 1 иаиболыпих элементов принадлежат Т.) Пусть 5 = (1,, и) '1 Т— другие элементы и установлено 5з +- 5, Те +- Т; 5е н То будут представлять элементы, которые могут стать Г-ми по старшинству. А2. До' тех пор, пока |То| > г, все сравнения х: у выполняются следующим образом.
Если к б 5 и у б Т, считается, что к < у. Если к б 5 и у б 5, подбрасывается монета н удаляется меньший элемент пз 5е, если ан принадлежит 5з Если к б Т и у б Т, подбрасывается монета и удаляется больший элемент из Те, если он принадлежит Те. АЗ. Как талька получим |Те| = г, элементы разделятся на три класса, Р, Я, Рн еле. дующим образом. Если |5о| < д, считается, что Р = 5, О = Те, Н гз Т 1 Те В противном случае для каждого у б Те счнтается, что С(у) — это элемент из 5, который уже прошел сравнение с у и выбирается уе, такой, что |С(уе)] минимально. Пусть Р = (5 1 5а) 0 С(уе), (г = (5е 1 С(уз)) 11 [уа] 11 = Т ~ [уе).
Все последующие сравнения к: у выполняются так, что элементы из Р считаются меньше элементов из Я, а элементы из 1„1 меньше элементов из Ри если же к и у нриналлежат одному и тому же классу, подбрасывается монета. Докажите что, если 1 < г < 1 и |С(уе)| < д — г в начале шага АЗ, каждый лист ,аостигастся с веронтностыо < (и + 1 — 1)/(2" е(",)), указание. Покажите, что будет сделано не менее и — д подбрасываний монеты.
с) Продолжая (Ь), покажите, что лля всех целочисленных значений е и г. 4) Выведите (14), выбрав соответственно д и г. ~5.3.4. Сети сортировки В настоящем разделе мы будем изучать класс методов сортировки„удовлетворяющих некоторому ограничению. Интерес к таким методам объясняетсл в основном приложениями и солидной теоретической основой. Это новое ограничение требует, чтобы последовательность сравнений ие зависела ош цредмспюрии в том смысле, что если мы сравниваем К; и К,, то последующие сравнения дчя случая К, < К. в точности те же, что и для случая К, > Ку, однако 1 и 1 меняются ролями.
Иа рис. 43, (а) изображено дерево сравнений, в котором зто условие однородности выполнено. Заметны, что на каждом уровне производится одинаковое число сравнений, поэтому после т сравнений имеется 2 результатов. Так как и( не является степелью 2, некоторые сравнения будут излишними в том смысле, что одно из их поддеревьев никогда не встречается на практике. Иными словами, на некоторых ветвях дерева приходится выполнять больше сравнений, чем необходимо, чтобы сортировка была правильной на всех соответствующих ветвях. Поскольку каждый путь на таком дереве сверху донизу определяет все дерево, зту схему сортировки проще изображать в виде геши, как на рис. 43, (Ь).
Прямоугольник в подобной сети представляет "модуль компаратора", имеющий два входа (изображены линиями, входшцимн в модуль сверху) н два выхода (изображены ливиями, выходящими вниз); левый выход — меньший из двух входов, а правый выход --. больший из них. Элемент К', в нижней части сети есть наименьший из (КыКз,Кз, Кя), Кз — — второй в порядке возрастания и т. д. Нетрудно доказать, что любая сеть сортировки соответствует дереву сравнений, обладающему свойством независимости от предыстории (в указанном вылив смысле), и что любое такое дерево соответствует сети модулей компараторов. Между прочны, технически мсзуль компаратора довольно легко изготовить.
Предположим, например, что по линиям связи в модуль поступают двоичные числа по одному разряду в единицу времени, начиная со старшего, Каждый модуль компаратора имеет три состояния и функционирует следующим образом, Момент Ф Момент (1+ 1) Состояние Входы Состояние Выходы О ОО 0 00 0 01 1 01 0 10 2 01 0 11 О 11 1 х д 1 х д 2 ху 2 ух Первоначально все модули находятся в состоянии О и выдают 0 О. Модуль переходит в состояние 1 или 2, как только его входы становятся различными..Числа, которые в момент времени 1 начали поступать сверху в сеть, соответствующую рис. 43, (Ь), К, Ке Ка К К'1 Кт' К( К( (Ь) (а) Рмс. 43. (а) Дерево сравнений, а котором не учнтывается предмсторая.
(Ь) Соответствующая ему сеть. 1 1 1 К,' К! 4 1 1 3 — ~-2 К,' Кз Кз 1 — 1 — 4 4 4 Рнс. 44. Еще один способ представ- ления сортировки последовательности (4, 1, 3, 2) посредством сети, изображен- ной на рис. 43. Кз 3 3 — ~~ — 2 2 К,— 2 — 2 — 1!— 3 — 3 4 — 4 — Кз ьз! с'з сз *з и! — ! Ф з!!+1 с С!!4! из+! С!4! (а) Рис. 43.
Получение (и (Ь) выбор. (Ь) + 1)-элементных сортировшиков из и-элементных: (а) вставка, начнут в момент 1+ 3 выводиться снизу в рассортированном порядке, если включить соответствующий элемент задержки на линиях К', и К'. При разработке теории сетей сортировки удобно изображать их несколько иным способом. На рис. 44 числа поступают слева, а модули компараторов представлены в виде вертикальных соединений между двумя прямыми; каждый компаратор вызывает, если необходимо, перестановку своих входов таким образом, что после прохождения компаратора большее число оказывается на ииозснез).
линии. В правой части диаграммы все числа упорядочены сверху вниз. Ранее, изучая методы оптимальной сортировки, мы уделяли основное внимание минимизации числа сравнений, почти (или совсем) не учитывая перемещение данных либо сложность структуры принятия решений, которые связалты с таким методом сортировки. В этом отношении сети сортировки имеют некоторое преимущество, так как данные могут храниться в и ячейках, а структура принятия решений "прямолинейна"; нет необходимости запоминать результаты предыдущих сравнений — план неизменен и фиксирован заранее. Вше одним важным преимуществом сетей сортировки является то, что часть операций можно совмещать, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
