AOP_Tom3 (1021738), страница 58
Текст из файла (страница 58)
Как можно изменить алгоритм, чтобы кле з К не сравнивался с КЛ в основном цикле вычислений, и таким образом почти нала. ~ нину уменьшить число сравнений? 19. [81] Предложиз~ алгоритм исключения данного элемента из пирамиды размером Х, порождающий пирамиду размером М вЂ” 1. 20. [МЯО] Покажите, что формулы (14) задают размеры особых поддеревьев пирамиды. 21. [МЯЛ] Докажите, что формулы (15) задают размеры неособых поддеревьев пирамиды.
ь 22. [ЯО] Какие перестановки множества (1,2,3,4,5] на фазе построения пирамиды в алгоритме Н преобразуются в 53412? 23. [МЯО] (а) Докажите, чта длина пути В в алгоритме протаскивания никогда не превышает [)8(г/1)]. (Ь) Согласно неравенствам (8) ни при каком конкретном применении алгоритма Н величина В не может превзойти л![18 !У]. Найдите максимальное значение В по всевозможным исходным массивам как функцию от?У. (Нужно доказать, что существует такой исходный массив, на котором В принимает это максимальное значение.) 24.
[МЯ4] Выведите точную формулу стандартного отклонения величины В~ (суммарная длина пути, пройденного по дереву во время фазы построения пирамиды в алгоритме Н). 23. [МЯ0] Чему равен средний вклад в значение параметра С за время первой операции протаскивания, когда 1 = 1 и г = !У, если л! = 2а Ы вЂ” 1? 26. [М50] Выполните упр.
25: (а) для?с! = 26, (Ь) для произвольного Л'. 27. [МЯ5] (Т. Клаузен (Т. С!аоэеп), 1828.) Докажите, что >! >! (Положив х = -', получите очень быстро сходящийся ряд для вычисления (19).) 28. [55] Продумайте идею глернаркмх пирямид, основанных на полных тернарных, а не бинарных деревьях. Вудет ли тернарная пирамидальная сортировка выполняться быстрее бинарной? 29.
[Яб] (У. С. Браун (Ъ. 8. Вгоъчп).) Постройте алгоритм умножения многочленов или степенных рядов (а!х" + азх" + )(6|хм + Ьзх!! + ), который порождал бы коэффициенты произведения с!хм+!! + . в том порядке, в котором перемножаются коэффициенты исходных многочленов.
[Указание. Воспользуйтесь подходящей приоритетной очередью.] !' 39. [НМ55] (Р. Шаффер (В,. Бс1гайег) и Р. Седгевик (К. Бедбеп!сй).) Пусть Л„, — число пирамид элементов (1,2,..., и), для которых фаза выбора даст ровно т продвижений. Докажите, что -< П18 э=э и используйте это соотношение для того, чтобы показать, что среднее число продвижений, выполняемых алгоритмом Н, равно !У 18 !У + 0(д! 1об !об Х). 31. [57] (Д!к. У.
Дж. Уильямс.) Покажите, что если две пирамиды подходящим образом совместить "основание к основанию", то появится возможность поддерживать структуру, в которой в любой момент можно за 0(1об и) шагов исключить либо наибольший, либо наименьший элемент. (Такую структуру можно назвать приорошеткмм деком.) 32. [МЯЯ] Докажите, что число продвижений В при пирамидальной сортировке вгегда оказывается ие меньше -'?!!!8 Х+ О(!У), если все сортнруемые ключи различны. Указание. Рассмотрите продвижение [?У/2] наибольших ключей.
33. [Я1] Разработайте алгоритм слияния двух непересекающихся приоритетных очередей, представленных в виде левосторонних деревьев, в одну. (В частности, если одна из данных очередей содержит всего один элемент, то ваш алгоритм будет вставлять его а другую очередь.) 34. [М41) Сколько можно построить левосторонних деревьев !сз Л' узлов, есэи игнорировать значения поля КЕ?? Эта последовательность начинается с чисел 1, 1, 2, 4, 8, 17, 38, 87, 203, 482, 1160,...; покажите, что данное число асимптотически стремится к оЬ Х ! при л -3/2 соответствующим образом выбранных константах а и Ь, используя методику, аналогичную примененной в упр.
2.3.4.4-4. 35. (26] Если в левостороннее дерево добавить связи УР (ср. с анализом деревьев с тремя связями в разделе 6.2.3), то получим возможность исключать из приоритетной очереди произвольный узел Р слелующим образам: слить !.БРТ(Р) и 81ОНТ(Р) и поместить полученное поддерева на место Р, затем исправлять поля Р1БТ предков узла Р до тех пор, пока не будет достигнут либо корень, либо узел, поле РТБТ которого не меняется. Докажите, что при этом никогда не потребуется изменить более чем О(1оБ ?тт) полей Р1БТ, несмотря даже на то, что дерево может содержать очень длинные восходящие пути. 36. (18] (Замещение наиболее давно использованной стораницы.) Во многих операционных системах используется алгоритм следующего типа: над набором узлов допустимы две операции: (!) использование узла и (0) замещение наиболее давно использованного узла новым.
Какая структура данных облегчает нахождение наиболее давно использованного узла? 37. (НМЭЯ] Пусть ея()т) — предполагаемое расстояние между самым большим )т-м элементом и корнем в случайной пирамиде из Ю элементов и пусть е()т) = !)тпя.т ея(?т). Тогда е(1) = О, е(2) = 1, е(3) = 1.5, а е(4) = 1,875. Найдите значение асимптотического выражения для е()т) через О(!с '). 38.
(М31] Найдите простое рекуррентное соотношение для мультимножества Мя размеров поддеревьев в пирамиде илн в полном бинараолт дереве, имеющем ттт внутренних узлов. 5.2.4. Сортировка методом слияния Слилнисэ означает объединение двух или более упорядоченных массивов в один упорядоченный массив. Можно, например, слить подмассивы 503 703 765 и 087 512 677 и полу'чить 087 503 512 677 703 765.
Простой способ сделать это -- сравнить два наименьших элемента, вывести наименьший из ннх и повторить эту процедуру. Начав с < 503 703 765 087 512 677 ' получим 087 ] 03 703 765 1 512 677 затем 087 503 ]< 512 677 087 503 512 ( 677 и т. д, Необходимо решить, что делать в слу'чае, когда исчерпается один нз массивов. Весь процесс подробно описан в следующем алгоритме.
Алгоритм М (Даухпршевос слияние). Этот алгоритм осуществляет слияние упорядоченных массивов хт < хз « . х,„и у, < уз « .. Рп и массив х! < хз « . х,пэ.п (рис. 29). М1. <Начальная установка.],Установиты ( — 1, Э' ( — 1, !т !- 1. т В англоязычной литературе термину слияние соответствуют лвь равнозначных термвна— таегутпд я са(!а!тая. — Прим. перев.
рван Рис. 29. Слияниеш « х сщ « у . М2. [Найти наименьший элемент.] Если х; < у, перейти к шагу МЗ; в противном случае перейти к шагу М5. МЗ. [Вывести яо] Установить вь < — хь й е- й+ 1, ! ~ — 1+ 1. Если ! < т, вернуться к шагу М2. М4. [Передать уу,...,у„.] Установить (хы...,з,„+„) +- (уу,...,у„) и завершить выполнение алгоритма. М5. [Вывести у .] Установить «ь +- у, и ~ — и+ 1, 1 < — 1+ 1. Если 1 < и, вернуться к шагу М2, Мб. [Передать хо...,х„,.] Установить (хы...,в,„.ь„) е- (х„...,х ) и завершить выполнение алгоритма. $ В разделе 5.3.2 будет показано, что эта простая процедура, по существу, — наилучший из возможных способов слияния на компьютере с обычной архитектурой, когда ш ж и.
(Но, если т гораздо меньше и, можно разработать более эффективные алгоритмы сортировки, хотя в общем случае они довольно сложны.) Алгоритм М без существенной потери эффективности можно немного упростить, добавив в конец исходных массивов искусственных "стражей" (ограничивающие элементы х„,з.~ = у„.ю = оо) и остановившись перед выводом оо. Анализ алгоритма М приведен в упр. 2. Общий объем операций, выполняемых алгоритмом М, по существу, пропорционален т + и, откуда понятно, почему считается, что слияние — более простая задача, чем сортировка.
Однако задачу сортировки можно свести к слияниям, сливая все более длинные подмассивы до тех пор, пока не будет рассортирован весь массив. Такой подход можно рассматривать как развитие идеи сортировки методом вставок: вставка нового элемента в упорядоченный массив — частный случай слиянии при п = 1. Чтобы ускорить процесс вставок, можно рассмотреть вставку нескольких элементов за один раз, группируя несколько операций, а это естественным образом приведет к общей идее сортировки методом слияння.
С исторической точки зрения метод слияний — один из самых первых методов сортировки при помощи компьютеров; он был предложен Джоном фон Нейманом (ЛоЬп гоп Хешпапп) еще в 1945 году (см. раздел 5.5). Таблица 1 СОРТИРОВКА МЕТОДОМ ЕСТЕСТВЕННОГО ДВУХНУТЕВОГО СЛИЯНИЯ тт~ 90т утт Вт~~ ~~~~ тттг 126 уту 509 Гтхт 061 612 908 154 275 426 653 897 509 170 677 703 765 154 275 426 653 908 897 612 503 509 512 612 677 703 765 897 908 653 503~ 087 512~~ 677 755 703 503 703 765 087 503 512 061 087 170 677 512 087 э09 170 061 426 275 154 061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908 Вертикальными линиями в табл.
1 отмечены границы между сериями, Эта так называемые сшупемьки вниз, где меньший элемент следует за большим. В общем случае в середине массива возникает двусмысленная ситуация, когда при движении с обоих концов считывается один и тот же ключ; это не приведет к осложнениям, если проявить чуточку осторожности, как в следующем алгоритме. Такой метод по традиции называется "естественным" слиянием, потому что в нем используются серии, которые "естественно" образуются в исходном массиве. Алгоритм Х (Сортпировкв метпвдом естпестпвепнвго двйппутпевога слияния).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
