Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 42
Текст из файла (страница 42)
К счастью, благодаря сформулированной ниже теореме анализ построения пирамиды можно снести к изучению независимых операций "протаскивания". Теорема Н. Если нсхаднымп даннымн для алгоритма Н служит случайная перестановка множества (1,2,...,Ф), та в фазе построения пирамиды с одинаковой вероятностью мажет получиться любая из Ф!/ П (з ~ и 6 Мл) возможных пирамид. Более того, все )Ф/21 операций протаскивания, выполненных в течение этой фазы, равномерны в том смысле, чта по достижении шага Н8 все сч возможных значений переменной 1 равновероятны. Доказательство.
Применим метод, который в численном анализе называется методом обратной задачи. Пусть в качестве одного из возможных результатов выполнения протаскивания задана пирамида К~... Кч с корнем в узле Е Тогда ясно, чта имеется точна сч исходных конфигураций К,'... К)ч массива, которые после протаскивании дают такой результат. Все эти исходные конфигурации имеют различные значения К~, следовательно, рассуждая наоборот, можно получить ровно сч з1+~... зл исходных перестановок множества (1,2,..., Ж), которые после завершения протаскивания в позицию 1 дают конфигурацию Кэ... Кл. Случай, когда 1 = 1, типичен: пусть К1., Кч — пирамида и пусть К)...
Кл— массив, который преобразуется в К~... Кл в результате протаскивания при 1 = 1, К = К,', Если К = Ка то должны иметь место равенства К, = Крут), К~,уя) = К(йм) и т. д. При этом К' = Кз для всех з, не лежащих на пути от 1 к 1. Обратна, при любом ( в результате подобного построения получается массив К,'... Кл', такой, что (а) операция протаскивания приводит к преобразованию массива К,'... К~я в К~ ° Кл, и (Ь) К11за) > Кэ при 2 'с (1/2) с 1 < Х.
Следоважльно, возможно ровно У таких массивов К',... К)ч и операция протаскивания имеет равномерное распределение. (Пример доказательства этой теоремы приводится в упр. 22,) 8 Обратившись к параметрам А, В, С„Х> в анализе программы Н, можно видеть, что равномерная операция протаскивания, выполняемая по отношению к поддереву размером а, дает вклад (е/2) /з в среднее значение величины А. Ее вклад в среднее значение величины В равен -(О+ 1+ 1+ 2+ ° ° ° + (!8а)) = — ~~~ (!8я) = -((а+ 1)(!8в) — 2(~х'1+' + 2) 1 1 ' 1 е Ю э (см. упр.
1.2.4-42), и опадает вклад либо 2/з, либо 0 в среднее значение параметра В в зависимости от того, каким является ат четным или нечетным. Несколько сложнее определить соответствующий вклад в среднее значение параметра С, так что эту задачу мы предлагаем читателю решить самостоятельно (см. упр. 26). Производя суммирование по всем операциям протаскивания, находим, что среднее значение параметра А за время построения пирамиды равно А~д = ~~~ ((э/2)/з ! а б Мл) (17) Аналогичные формулы имеют место и для В, С и Ю, так что можно без особого труда точно вычислить эти средние значения. В следующей таблице приведены типичные результаты.
Что касается асимптотики, то в Ми можно не обращать внимания на размеры особых поддеревьев, и тогда мы найдем, например, что Л 0 Ф 1 Ж 3 А,'~ — —. — + —. — + — +" +0(!обХ) = (1 — 1п)В+0(!обМ), (18) 2 1 4 3 8 7 з где о = ~~~ — = 1.6066951524152917637833015231909245804805-. (19) 1 2" -1 (Это значение получил Дж. У. Ренч (мл.) (Л. %. 'ттгепсп, Лг.), пользуясь преобразованием ряда из упр. 27. Пол Эрдеш (Ран! Егбое) доказал, что а является иррациональным числом (Х 1лйап Май. Яос. 12 (1948), 63-66], а Питер Ворвейн (Ресег Вогтгеш) продемонстрировал иррациональный характер многих других констант (Ргос. СашЬ, РЛ!1 Яос.
112 (1992), 141 — 146).) При больших Ю можно использовать приближенные формулы Х 99 100 999 1000 9999 10000 10001 10002 А',т 19Л8 19.93 196.16 196.94 1966.02 1966.82 1966 Ао 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 (21) А~~ ш 0.1967Ю+ ( — 1)»0.3; В]» ш 0.74403Х вЂ” 1.3 1п Аг; С]» ш 0.47034Х вЂ” 0.8 1и Ю; Ц» ш (1.8 ш 0.2) [Аг четное). Нетрудно определить также максимальные и минимальные значения. Для построения пирамиды требуется всего 0()»') шагов (см.
упр. 23). Этим, по существу, завершается анализ фазы построения пирамиды в алгоритме Н. Анализ фазы выбора — совсем другая задача, которая еще ожидает своего решения! Пусть пирамидальная сортировка применяется к»» злемектам; обозначим через А',(„Вл, Сф и с»Д средние значения величин А, В, С и В во время фазы выбора.
Поведение алгоритма Н подвержено сравнительно малым колебаниям около эмпирически установленных средних значений А~я~~ ш 0.152Ю; В~~ ш Ю 16 Ф вЂ” 2.61»'»'; С~а и 1р7 18 Х вЂ” 1.41Ю; ВЯ ш1БЮ~2. Тем не менее до сих пор не найдено адекватного теоретического объяснения поведения Вл нли эмпирически подобранных значений констант 0.152, 2.61 и 1.41. Ведущие члены в выражениях для В~~, и С](, однако, очень изящно обоснованы Р. 1Паффером и Р. Седгевиком (см. упр.
30). Шаффер также доказал, что минимальное и максимальное значения СД равны -'Ю18 Ю н 1Х 16г7 соответственно. УПРАЖНЕНИЯ 1. [10] Является ли сортировка посредством простого выбора (алгоритм 8) устойчивой? 2, [15] Почему в алгоритме Б более удобно находить сначала наибольший элемент, затем — наибольший иэ оставшихся н т. д., вместо того чтобы находить сначала наименьший элемент, затем — наименьший из оставшихся и т. д.7 3. [МИ] (в) Докажите, что если алгоритм Б применяется к случайной перестановке множества (1,2,..., К), то в результате первого выполнения шагов 82 и БЗ получается случайная перестановка множества (1,2,...,К-1), за которой следует М. (Иначе говоря, массив Кь .. Кл ~ с одинаковой вероятностью может быть любой перестановкой множества (1,2,..., Ж-Ц.) (Ь) Следовательно, если через Вл обозначить среднее значение величины В в программе Б, то при условии, что исходный массив упорядочен случайным образом, имеем Вл = Нл — 1+ Вл-ь [Указание.
См. выражение 1.2.10-(16).] 4, [М05] На шаге БЗ алгоритма Б ничего не происхсдит, если 1 = у. Не лучше лн перед выполнением шага БЗ проверить условие 1 = 1"? Чему равно среднее число случаев выполнения условия 1 = у иа шаге БЗ, если исходный массив случаен? 5. [20] Чему равно значение параметра В в анализе программы Б для исходного массива К...
3217 6. [М00] (а) Пусть а~ аэ...ал — перестановка множества (1,2,...,Х) с С циклами, 1 инверсиями и такая, что при ее сортировке с помощью программы Б выполняется В обменов иа правосторонний максимум. Докажите, что 2В < 7+ К вЂ” С. (Указание. См. упр, 5.2.2-Ц (Ь) Покажите, что 1+ К вЂ” С < (»»~/2]; следовательно, В не превышает (Хэ/4]. Т. [М4!] Найдите дисперсию параметра В в программе Б как функцию от А!, считая, что исходный массив случаен. 8. [24] Покажите, что если при поиске щах(Км..., К!) на шаге 82 просматривать ключи савва направо (Км Л з,..., К! )., а не наоборот, как в программе 8, то можно сократить число сравнений при следующих итерациях шага 82. Напишите И11-программу, реализующую этот подход.
9. [М30] Чему равно среднее число сравнений, выполняемых алгоритмом из упр. 8 для случайного исходного массива? 19. [!2] Как будет выглядеть дерево, изображенное на рис. 23, после вывода 14 из 16 первоначальных элементов? 11. [10] Как будет выглядеть дерево, изображенное на рис. 24, после вывода элемента 908? 12. [М20[ Сколько раз будет выполнено сравнение -оо с -оо, если применить восходящий метод, представленный на рис. 23, для упорядочении массива из 2' элементов? 13. [20! (Дж.
У, Дж. Уильямс (Л. %. Л. ЪУ!))!ащэ).) На шаге Н4 алгоритма Н различаются три случая: 2 < г, у = г и з > г. Покажите, что если К > К,ъм то можно так упростить шаг Н4, что разветвление будет происходить лщпь по двум ветвям. Как следует изменить шаг Н2, чтобы обеспечить в процессе пирамидальной сортировки выполнение условия К > К» ы? 14. [!О] Покажите, что простая очередь — частный случай приоритетной. (Объясните, какие ключи нужно присваивать элементам, чтобы процедура "наибольший из включенных первым исключается" была эквивалентна процедуре»первым пришел — первым вышел"?) Является ли стек также частным случаем приоритетной очереди? ъ 16. [Мйй] (В.
Э, Чаргрс (В. А. СЪщсгев).) Придумайте быстрый алгоритм построения таблицы простых чисел < Х, в котором используется приоритетная очередь, чтобы избелщть операций деления. [Указание. Пусть наименыпий ключ в приоритетной очереди будет наименьшим нечетным непростым числом, ббльшим, чем самое последнее нечетное число, рассматриваемое как кандидат в простые числа.
Попытайтесь свести к минимуму количество элементов в этой очереди.] 16. [30] Постройте эффективный алгоритм, который позволяет вставить новый ключ в данную пирамиду нз и элементов, порождая пирамиду нз и + 1 элементов. 1?. [20] Алгоритм из упр. 16 можно использовать для построения пирамиды вместо метода "уменьшать ! до 1", применяемого в алгоритме Н. Порождают ли оба метода нз одного и того же исходного массива одну и ту же пирамиду? ъ 18.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
