Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 43
Текст из файла (страница 43)
[Ы] (Р. У, Флойд (Н. %. г!оуб).) Во время фазы выбора в алгоритме пирамидальной сортировки ключ К, как правило, принимает довольно малые значения, и поэтому почти при всех сравнениях на шаге Нб обнаруживается, что К < К . Как можно изменить алгоритм, чтобы кл» ч К не сравнивался с Кз в основном цикле вычислений, и таким образом почти напк нину уменьшить число сравнений? 19. [21] Предложим алгоритм исключеиил данного элемента из пирамиды размером Х, порождающий пирамиду размером Х вЂ” 1. 20. [М20] Покажите, что формулы (14) задают размеры особых поддеревьев пирамиды. 21.
[М94] Докажите, что формулы (1$) задают размеры неосабых поддеревьев пирамиды. ъ 22. [20] Какие перестановки множества (1, 2,3,4, 5) на фазе построения пирамиды в алгоритме Н преобразуются в 53412? 23. [М30] (а) Докажите, что длина пути В в алгоритме протаскивания никогда не превышает [!8(г!'!)]. (Ь) Согласно неравеистввм (8) ни при каком конкретном применении алгоритма Н величина В не может превзойти Х(18Х]. Найдитс максимальное значение Б по всевозможным исходным массивам как функцию от йб (Нужно доказать, что суше- ствует такой исходный массив, на котором В принимает зто максимальное значение.) 24.
(МЯ4] Выведите точную формулу стандартного отклонения величины Вл (суммарная длина пути, пройденного по дереву во время фазы построения пирамиды в алгоритме Н). 26. (МЯО] Чему равен средний вклад в значение параметра С за время первой операции протаскивания, когда 1 = 1 и г =?У, если 1»' = 2» ю — 1? 26. (МЯО] Выполните упр. 25: (а) для?Я = 26, (Ь) для произвольного 1Я. 27.
(МЯЯ] (Т. Клаузен (Т. С!авзев), 1828.) Докажите, что — — „х »21' (Положив х = -', получкте очень быстро сходащийся ряд для вычисления (10).) 28. [ЯЯ] Продумайте идею шернарнмя пирамид, основанных на полных тернарных, а не бинарных деревьях. Будет ли тернарная пнрамвзшльная сортировка выполняться быстрее бинарной? 29. (ЯЯ] (У, С. Браун (%. 8.
Вгопп).) Постройте алгоритм умножения многочленов или степенных рядов (а~в" + агх'» + ... )(Ь|х" + Ьэхэ' + ... ), который порождал бы коэффициенты произведения с~хи+0 +. в том порядке, в котором перемножаются коэффициенты исходных многочленов. (Указание. Воспользуйтесь подходящей приоритетной очередью.] ь 30. [??МЯЯ] (Р. Шаффер (К. Бсйа??ег) и Р. Седгевик (К. 8ег(8ен1сЛ).) Пусть Л,» — число пирамид элементов (1,2,..., и), для которых фаза выбора даст ровно гл продвижений. Докажите, что Л„(2 Д 18Л, ь=з и используйте зто соотношение для того, чтобы показать, что среднее число продвижений, выполняемых алгоритмом Н, равно?У 18?У + 0(?У 1об 1о8 Х), 31.
(37] (Ддг. У. Дж. Уильямс.) Покажите, что есэи две пирамиды подходящим образом совместить 'основание к основанию", то появится возможность поддерживать структуру, в которой в любой момент можно за 0(1обп) шагов исключить либо наибольший, либо наименьший элемент. (Такую структуру можно назвать приоритетным деком.) 32. (МЯЯ] Докажите, что число продвижений В при пирамидальной сортировке всегда оказывается не меньше -'Х 18?У+ О(Ь?), если все сортируемые ключи различны.
Указание. Рассмотрите продвижение (М/2] наибольших ключей. 33. (81] Разработайте алгоритм слияния двух непересекшощихся приоритетных очередей, представленных в виде левосторонних деревьев, в одну. (В частности, если одна из данных очередей содержит всего один элемент, то ваш алгоритм будет вставлять его в другую очередь.) 34. (М41] Сколько можно построить левостороипих деревьев из 1У узлов, если игнориро- вать значения поля КЕ?? Эта последовательность начинается с чисел 1, 1, 2, 4, 8, 1?, 38, 8?, 203, 482, 1160, ...; покажи ш, что данное число аснмптотически стремится к аЬ~)»' э ш при соответствующим образом выбранных константах а и Ь, используя методику, аналогичную примененной в упр.
2.3.4.4-4. Зб. (Зб) Если в левостороннее дерево добавить салан ЗР (ср. с акалнзом деревьев с тремя связями в разделе 6.2.3), то получнм возможность исключать нз приоритетной очереди пронзяольный узел Р следующим образом: слить |.ЕРТ(Р) н ЗХЗЗТ(Р) н поместить полученное лолдерево на место Р, затем исправлять поля РХЗТ предкоа узла Р до тех пор, пока не будет достигнут лнбо корень, либо узел, поле РХЗТ которого не меняется. Докажите, что прн этом никогда не потребуется наменять более чем О(1ой Ж) полей РХЗТ, несмотря даже на то, что дерево может содержать очень длннные яосходящне пути. Зб. (18) (Замещенне наиболее давно использоеанней сгвраницм,) Во многих операцнонных системах нспользуется алгоритм следующего типа: над набором узлов допустимы две операции: (1) нспользованне узла н (б) замещенне нанболее давно нспользованного узла новым. Какая структура данных облегчает нахожленне нанбозее давно нспольэованного узла? ЗТ. (ЛМЗЗ) Пусть ел(я) — предполагаемое расстояние между самым большим л-м элементом н корнем в случайной пнрамнле нз д' элементов н пусть е(З) = йшл ел(л).
Тогда е(1) = О, е(2) = 1, е(3) = 1.5, а е(4) = 1.375. Найдите значение аснмптотнческого яыраження для е((г) через 0(Л 1). ЗЗ, (МУХ) Найдите простое рекуррентное соотношение лля мультнмножества Мн размероя поддеревьев в пирамиде нлн в полном бкнарном дереве, имеющем )ч' внутренннх узлов. $.2.4. Сортировка методом слияния Слилнне* означает объединение двух цлн более упорядоченных массивов в один упорядоченный массив.
Можно, например, слить подмасснвы 503 703 765 н 087 512 677 н получнть 087 503 512 677 703 765. Простой способ сделать зто — сравнить два наименьших элемента, вывести наименьший нз ннх н повторнть зту процедуру. Начав с Е 503 703 765 087 512 677 ' 7 ) 503 703 765 ~ 512 677 087 503 .) 703 765 ~ 512 677 087 503 512 н т. д. Необходимо решить, что делать в случае, когда исчерпается один нз массивов. Весь процесс подробно опнсан в следующем алгоритме. Алгоритм М (Дерхпршееое слияние).
Этот алгоритм осуществляет слияние упорядоченных масснаоа х1 ( хз с ° (х,„н р1 С рз С ° ° . С ря а масона з1 С зз ( ° ° ~ лш+„(рнс. 29). М1. (Начальная установка.),Устпновнты +- 1, у +- 1, 3 ч- 1. ' В знглояэычноа литературе термнну слоеное соотеетствуют Лез равнозначных термнна— ямгз(пя я гайецгм. — При ~. перев. рпэн Рнс. 29. Слияние*~ < < х„с Ю < .. <у„. М2, [Найти наименьший элемент.] Если х; < р~, перейтн к шагу МЗ; в противном случае перейти к пшгу М5.
МЗ. [Вывести х;.] Установить хэ э- хп й е- й + 1„1+- 1+ 1. Если г' < ш, вернуться к шагу М2. М4. [Передать пэ,...,п .] Установить (хы...,х,х+„) +- (уу,...,р„) и завершить выполнение алгоритма Мб. [Вывести р .] Установить хь +- р., й <- й+ 1„1 <- у + 1. Если у < и, вернуться к шагу М2. Ыб.[Передать х;,...,х .] Установить (хэ,...,х +„) е- (т,,...,х ) и завершить выполнение алгоритма. $ В разделе 5.3.2 будет показано, что зта простая процедура, по существу, — наилучший из возможных способов слияния на компьютере с обычной архитектурой, когда ш ж и.
(Но, если ш гораздо меньше и, можно разработать более эффективные алгоритмы сортировки, хотя в общем случае онн довольно сложны.) Алгоритм М без существенной потери эффективности можно немного упростить, добавив в конец исходных массивов искусственных "стражей" (ограничивающие элементы х,„+1 = у„+1 = со) и остановившись перед выводом со. Анализ алгоритма М приведен в упр. 2. Общий объем операций, выполняемых алгоритмом М, по существу, пропорционален ш + и, откуда понятно, почему считается, что слияние — более простая задача, чем сортировка. Однако задачу сортировки можно свести к слияниям, сливая все более длинные подмассивы до тех пор, цока не будет рассортирован весь массив.
Такой подход можно рассматривать как развитие идеи сортировки методом вставок: вставка нового элемента в упорядоченный массив — частный случай слияния при и = 1. Чтобы ускорить процесс вставок, можно рассмотреть вставку нескольких элементов за один рэз, группируя несколько операций, а это естественным образом приведет к общей пдее сортировки методом слияния, С исторической точки зрения метод слпяний — один нз самых первых методов сортировки при помощи компьютеров; он был предложен Джоном фои Нейманом (ЛоЬп гоп .чешпапп) еще в 1945 году (см.
раздел 5.5). Таблица 1 СОРТИРОВКА МЕТОДОМ ЕСТЕСТВЕЕИГОГО ДВУХПУТЕВОГО СЛИЯЕ1ИЯ зе) 251 ь 21 НЗ 655 116 622~ 225 (5624 426 154 5566 5612 542 125 255~ ~~4 612 255 164 225 426~655 1562 666 ПО 087 503 512 877 703 765 154 275 426 653 061 087 170 503 509 512 612 677 703 765 897 908 653 ~677 ~765 703 677 512 087 426 275 154 961 087 154 170 275 426 503 509 512 612 653 677 703 7б5 897 908 Вертикальнымн линиями в табл. 1 отмечены границы между сериями, Это так называемые спбрпезбькзО епиз, где меньший элемент следует за большим.
В общем случае в середняя массива возникает двусмысленная ситуация, когда при движении с обоих концов считывается один и тот же ключ; это не приведет к осложнениям, если проявить чуточку осторожности, как в следующем алгоритме. Такой метод по традиции называется "естественным" слияннем2 потому что в нем используются серии, которые "естественно" образуются в исходном массиве.
Алгоритм 71 (Сортировка методом есяпестпеекноео дерхпугпееого слияния). При сортировке записей ВО..., Вн используются две области памяти, в каждой из которых может сцдержаться ОЧ записей. Для удобства обозначим записи, находящиеся во второй области, через Вьб< О..., Взя, хотя в действительности запись Вк+ я может и не примыкать непосредственно к Вн. Начальное содержимое записей Вь+ы..., Втя не имеет значения. После завершения сортировки ключи будут упорядочены таким образом: К~ < .. < Кн (рис. 30). 1211. (Начальная установка.] Установить е 4 — О.
(При е = О будем пересылать записи из области (Вы..., Вя) в область (Вк+5,..., Вт;д); при е = 1 области по отношению к пересылкам поменяются ролями.) Довольно подробно слияние рассматривается в разделе 5.4 в связи с алгоритмами внешней сортировки, в в настоящем разделе речь пойдет о сортировке в оперативной памяти с произвольным доступом. В табл. 1 проиллюстрирована сортировка методом слияния, когда "свечка сжигается с обоих концов", подобно тем процедурам просмотра элементов массива„которые применялись при быстрой сортировке, поразрядной обменной сортировке и т.
д. Будем анализировать исходный массив слева и справа, двигаясь к середине. Пропустим пока первую строку и рассмотрим переход от второй строки к третьей. Слева мы видим восходящую серию 503 703 765, а справа, если читать справа налево, имеем серию 087 512 677. Слияние этих двух последовательностей дает подмассив 087 503 512 677 703 765, который помещается слева в строке 3. Затем ключи 061 612 908 в строке 2 сливаются с 170 509 897 н результат (061 170 509 612 897 908) записывается справа в строке 3. Наконец, 154 275 426 653 сливается с 653 (перекрытие обнаруживается прежде, чем оно может привести к нежелателнным последствиям) и результат записывается слева. Точно так же строка 2 получается из строки 1 исходного массива.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
