AOP_Tom3 (1021738), страница 57
Текст из файла (страница 57)
28 показана форма пирамиды из 26 элементов; каждый узел помечен двоичным числом, соответствующим его индексу в пирамиде. Звездочками на этой диаграмме помечены так называемые особые узлы, которые лежат на пути от 1 к Лг. Одна из наиболее важных характеристик пирамиды — множество размеров ее поддеревьев. Например, на рис. 28 размеры поддеревьев с корнями в узлах 1,2,...,26 равны соответственно Рис.
28. Так выглядит пирамида из 26 = (11010)з элементов. Например, количество способов такого расположения 26 букв (А, В,С,..., Я) на рис. 28, чтобы по вертикали сохранялся алфавитный порядок, составляет 20(/(28.10 б 2 1 1" 8' 7' 18') Теперь можно проанализировать фазу построения пирамиды в алгоритме Н, т, е. вычислительные операции, которые завершаются до того, как на шаге Н2 впервые выполнится условие 1 = 1. К счастью, благодаря сформулированной ниже теореме анализ построения пирамиды можно свести к изучению независимых операций "протаскивания". Теорема Н.
Если ггсходнымп даннымп для алгоритма Н служит случайная перестановка множества (1,2,...,У), та в фазе построения пирамиды с одинаковой вероятностью может получиться любая из Х!/ П (э ! э б ЛХм) возможных ггнрамид. Более того, все '1)г'/21 операций протаскивания, выполненных в течение этой фазы, равномерны в том смысле, что по достижении шага Н8 все э~ возможных значений переменной 1 равновероятны. Доказагнельство. Применим метод, который в численном анализе называется методом обратной задачи.
Пусть в качестве одного из возможных результатов выполнения протаскивания задана пирамида Кы .. Кк с корнем в узле 1. Тогда ясно, что имеется точна э~ исходных конфигураций К,'... К,', массива, которые после протаскивания дают такой результат. Все зти исходные конфигурации имеют различные значения К,', следовательно, рассуждая наоборот, можно получить ровно з1 э1чз...
эм исходных перестановок множества (1, 2,, М), которые после завершения протаскивания в позицию 1 дают конфигурацию Кы .. Км. Случай, когда 1 = 1, типичен: пусть К,... Кд — пирамида и пусть К,'... Кч— массив, который преобразуется в Кг... Км в результате протаскивания при 1 = 1, К = К,'. Если К = Ка то должны иметь место равенства К,' = К1;~яр К1;/я) = К1;ы) и т.
д. При этом К' = К для всех г', не лежащих на пути от 1 к 1. Обратно, при любом 1 в результате подобного построения получается массив К,'... К~, такой, что (а) операция протаскивания приводит к преобразованию массива К,'... К~а в КР,.Кн, и (Ь) К1,~з) > К, при 2 < (у/2) < г < Х.
Следовательно, возможна ровно )г' таких массивов К,'...К,'~ и операции протаскивании имеет равномерное распределение. (Пример доказательства этой теоремы приводится в упр. 22.) 1 Обратившись к параметрам А, В, С, В в анализе программы Н, можно видеть, что равномерная операция протаскивания, выполняемая по отношению к поддереву размером в, дает вклад (в/2)/в в среднее значение величины А. Ее вклад в среднее значение величины В равен 1 1 1 -(О+ 1+ 1+ 2+ + (18в)) = — ~~~ (18Ц = — ((в+ 1)(18в) — 2ря'~ к~ + 2) в 3 в к=с (см. упр.
1.2.4-42), и она дает вклад либо 2/в, либо 0 в среднее значение параметра Р в зависимости от того, каким является ж четным или нечетным. Несколько сложнее определить соответствующий вклад в среднее значение параметра С, так что эту задачу мы предлагаем читателю решить самостоятельно (см. упр.
26). Производя суммирование по всем операциям протаскивании, находим, что среднее значение параметра А за время построения пирамиды равно А',ч —— ~ (~ в/2)/в ) в 6 Мм). (17) Аналогичные формулы имеют место и для В, С и В, так что можно без особого труда точно вычислить эти средние значения. В следующей таблице приведены типичные результаты. Что касается асимптотикн, то в Ми можно не обращать внимания на размеры особых поддеревьев, и тогда мы найдем, например, что Х 0 Ас 1 Х 3 А~ — — — + — + — + .+0(1о8АС) = (1 — 1а)Ас+0(1ойдс), (18) 2 1 4 3 8 7 2 где а = ~ — = 1.60669 51524 15291 76378 33015 23190 92458 04805 —.
(19) 1 2к — 1 к>1 (Это значение получил Дж. У. Ренч (мл.) (Я. %'. ЪУгепсЬ, Лг.), пользуясь преобразованием ряда из упр. 27. Пол Эрдеш (Рап! Егс1ов) доказал, что а является иррациональным числом (Х 1пйап МасЛ. Яос. 12 (1948), 63 — 66), а Питер Борвейн (Ресег Вогиесп) продемонстрировал иррациональный характер многих других констант (Ргос. СашЬ. РМ1. Яос.
112 (1992), 141-146].) При больших Ю можно использовать приближенные формулы Ас 99 100 999 1000 9999 10000 10001 10002 А,'ч 19.18 19.93 196.16 196.94 1966.02 1966.82 1966.45 1967.15 в' 68.35 69.39 734.66 735.80 7428.18 7429.39 7430.07 7430.97 С)т 42. 95 42. 71 464.53 464.16 4695.54 4695.06 4695.84 4695.95 Вгс 0.00 1.84 0.00 1.92 0.00 1.97 0.00 1.73 А'„= 0.1067)У+ (-1) 0.3; В~ ш 0.74403Х вЂ” 1.31пА1; С~ — 0.47034Х вЂ” 0.8 1п 1»'; Р,'» (1.8 ж 0.2) [)»' четное]. (20) Нетрудно определить также максимальные и минимальные значении.
Для построения пирамиды требуется всего 0(1»') шагов (см. упр. 23). Этим, по существу, завершается анализ фазы построения пирамиды в алгоритме Н. Анализ фазы выбора — совсем другая задача, которая еще ожидает своего решения! Пусть пирамидальная сортировка применяется к Х элементам; обозначим через Ал~, В~к, Са и Ра средние значения величин А, В, С и Р во время фазы выбора.
Поведение алгоритма Н подвержено сравнительно малым колебаниям около эмпирически установленных средних значений А~~ — 0.152%; Ва ?У 18 Х вЂ” 2.61Х; С,~~ аа з Х 18 Л вЂ” 1.41Х; Р~о ш 18 )У ж 2. (21) Тем нс менее до сих пор не найдено адекватного теоретического объяснения поведения Ро или эмпирически подобранных значений констант 0.152, 2.61 и 1.41. Ведущие члены в выражениях для Вч и Сч, однако, очень изящно обоснованы Р.
Шаффером и Р. Седгевиком (см. упр. 30). Шаффер также доказал, что минимальное и максимальное значения Са равны 1~Т18 Х и 1~Х 1БА1 соответственно. УПРАЖНЕНИЯ б. (МЗУ) (а) Пусть а~ ат...ал — перестановка множества (1,2,...,?»') с С циклами, 1 инверсиями и такая, что при ее сортировке с помощью программы Б выполняется В обменов на правосторонний максимум. Докажите, что 2В < 1 4- Аг — С. [Указание. См, упр. 5.2.2-1.] (Ь) Покажите, что 1+?»' — С < (?р~/2); следовательно, В не превышает (?»~/4]. 1.
]10] Является лн сортировка посредством простого выбора (алгорнтм Б) устойчивой? 2. ]!5] Почему в алгоритме Б более удобно находить сначала наибольший элемент, затем — намбольшнй нз оставшихся и т, д., вместо того чтобы находить сначала наименьший элемент, затем — наименьший нз оставшихся н т. д.? 3. (М21) (а) Докажите, что если алгоритм Б применяется к случайной перестановке множества (1, 2,...,?»), то в результате первого выполнения шагов 82 н БЗ получается случайная перестановка множества (1, 2,...,?у' — 1), за которой стегает 1»'.
(Иначе говоря, массив К~ .. Лк — ~ с одинаковой вероятностью может быть любой перестановкой множества (1,2,,%-1).) (Ь) Следовательно, если через Вл обозначить среднее значение величины В в программе Б, то прн условии, что исходный массив упорядочен случайным образом, имеем Вк = Нл — 1+ Вл ь (Указание. См. выражение 1.2.10-(1б).] 4. ]М25] На шаге БЗ алгоритма Б ничего не происходит, если 1 = 11 Не лучше лн перед выполнением шага БЗ проверить условие 1 = »? Чему равно среднее число случаев выполнения условия ю' = 1 на шаге БЗ, если исходный массив случаен? б. (20] Чему равно значение параметра В в анализе программы Б для исходного массива ?» ..321? 7. [М41] Найдите дисперсию параметра В в программе 8 как функцию от Ю, считая, что исходный массив случаен.
8. [84] 11окажите, что если при поиске шах(Км... „Кз) на шаге 82 просматривать ключи слева направо (Кп Кэ, ..., КЛ), а не наоборот, как в программе Б, то можно сократить число сравнений при слезующих итерациях шага 82. Напишите 811-программу, реализующую этот подход. 8. [МЯ5] Чему равно среднее число сравнений, выполняемых алгоритмом из улр. 8 для случайного исходного массива? 10. [18] Как будет выглядеть дерево, изображенное на рнс. 23, после вывода 14 из 1б первоначальных элементов? 11. [10] Как будет выглядеть дерево, изображенное на рис. 24, после вывода элемента 908? 12.
[МЯО] Сколько раз будет выполнено сравнение -оо с -оо, если применить восходящий метод, представленный на рис. 23, для упорядочения массива из 2" элементов". 13. [ЯО] (Дж. У. Дж. Уильямс (Л. гг'. Л. 17)1)(ашв).) На шаге Н4 алгоритма Н различаются три глучая: 1 < г, 1 = г и 1 > г. Покажите, что егли К > К,зл, то можно так упростить юаг Н4, что разветвление будет происходить лишь ло двум ветвям. Как следует изменить шаг Н2, чтобы обеспечить в процессе пирамидальной сортировки выполнение условия К > К,+~? 14. [10] Покажите, что простая очередь — частный случай приоритетной.
(Объясните, какие ключи нужно присваивать элементам, чтобы процедура "наибазьший нз включенных первым исключается" была эквивалентна процедуре "первым пришел — первым вышел"?) Является ли стек также частным случаем приоритетной очереди? ° 15. [МЯЯ] (Б. Э. Чартрс (В. А, СЬагсгев).) Придумайте быстрый алгоритм построения таблицы простых чисел < )г', в котором используется приоритетная очередь, чтобы избежать операций деления. [Указание. Пусть наименьший ключ в приоритетной очереди будет наименьшим нечетным непростым числом, ббльшим, чем самое последнее нечетное число, рассматриваемое как кандидат в простме числа.
Попытайтесь свести к минимуму количество элементов в этой очереди.) 16. [ЯО] Постройте эффективный алгоритм, который позволяет вставить новый «люч в данную пирамиду из и элементов, порождая пирамиду из и+ 1 элементов. 1?. [ЯО] Алгоритм нз улр. 1б можно использовать для построения пирамиды вместо метода "уменьшать 1 до 1", применяемого в алгоритме Н. Порождают ли оба метода нз одного и того же исходного массива одну н ту же пирамиду? ° 18. [Я1] (Р. У. Флойд (Н. 1Ч. Иоуб).) Во время фазы выбора в алгоритме пирамидальной сортировки ключ К, как правило, принимает довольно малые значения, и поэтому почти при всех сравнениях ла шаге Нб обнаруживается, что К < К,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
