Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 53
Текст из файла (страница 53)
7. [20) Нарисуйте расширенное тернарное дерево, как в упр. 5, для сортировки четырех элементов, если известно, что все ключи равны либо О, либо 1. (Так, например, если К~ < Кз н Кз < Кю то понятно, что К~ — — Кэ н Кэ = Кэ() Добейтесь минимального числа сравнений в среднем, считая, что все 2 возможных исходных массивов равновероятны. Обратите внимание на то, что должны быть проанализированы все имеющиеся варианты равенств; например, не прекршцайте сортировку, если становится известно, что К, < Кэ < К, <к4.
В. [26] Нарисуйте расширенное тернарное дерево, как в упр. 7, для сортировки четырех элементов, если известно, что ключи — это либо -1, либо О, либо +1. Добейтесь мини- мального числа сравнений в среднем, считая, что все 3 возможных исходных массивов равновероятны. 9. [М20] Каково минимальное число сравнений в наихудшем случае прн сортировке и элементов, как в упр.
7, когда известно, что все элементы равны либо О, либо 1? э 10. [М25] Каково минимальное среднее число сравнений при сортировке и элементов, как в упр. 7, когда известно, что все ключи равны либо О, либо 1? Результат представьте в виде функции от и. 11. [КМ27] Пусть Я (и) — минимальное число сравнений„необходимое в наихудшем случае для сортировки и элементов, как в упр. 5, причем известно, что все ключи принад- лежат множеству (1, 2,..., т), [Таким образом, согласно упр, б Я„(п) = Я(п).] Докажите, что Я~а(п) приближается к и 15 го+ 0(1) при фиксированном гл и и -+ оо.
ь 12. [М25] (У. Г. Бурисиус (%. О, Воайс1ав), ок. 1954 г.) Предположим, что равные ключи могут встречаться, но наша цель — рассортировать элементы (КмКэ,, К„» таким образом, чтобы сформировать перестановку а~ аэ... а„, удовлетворяющую условию К, < Кь « К „; иам не важно, имеет ли место равенство между элементами К„, н К,,„,. Будем говорить, что дерево сравнений сильно сортирует последовательность ключей, если оно сортирует ее в вышеуказанном смысле, независимо от того, какой путь выбран в узлах 1:/, для которых К, = К-.
(Дерево бинарное, а не тернарное.) а) Докажите, что дерево, не содержащее избыточных сравнений, сильно сортирует любую последовательность ключей тогда н только тогда, когда оно сортирует любую последовательность различных ключей. Ь) Докажите, что дерево сравнений сильно сортирует любую последовательность ключей тогда и только тогда, когда оно сильно сортирует любую последовательность нулей и единиц. 13. [М26] Докажите утверждение (17). 14. [М24] Выразите сумму (19) в замкнутом виде, 15. [М21] Определите асимптотическое поведение функций В(п) и Р(п) с точностью до О()обп).
[Указание. Покюкнте, что в обоих случаях коэффициент прн и содержит функцию, изображенную на рис. 37.) 16. [?/М26] (Ф. Хванг (Р. Ниапб) н Шень Линь (Я. 15п),) Докажите, что при п > 22 выполняется неравенство г (и) > [)Вп!]. 17. [М20] Докажите тождество (29). 1В. [20] Предположим, что процедура, начало которой изображено на рис. 36, породи- ла граф с эффективностью 12!/2ю. Доказывает ли зто, что Я12) = 29? 19. [40] Проведите эксперименты со следующим эвристическим правилом принятия ре- шения, какую пару ключей сравнивать следующей при конструировании дерева сравне- ний. Пусть на каждой сталин сортировки ключей (К,,..., К„) число ключей, о которых на основании выполненных до снх пор сравнений известно, что они < К„обозначается через и,„а число ключей, о которых известно, что они > К;, обозначается через еь 1 < 1 < и, Перенумеруем ключи так, чтобы последовательность н,/о, стала возрастающей: и1/е1 < иэ/еэ « и„/о„.
Теперь сравним К,. К;+м где 1 — индекс, минимизирующий [1(Х) — 21(1(Х))[ < 21'Зцкц 1(Х), 22. [М24[ Продолжение упр. 21. Докажите, что бинарное дерево имеет минимальную длину внешнего пути среди всех бинарных деревьев с тем же числом узлов тогда и только тогда, когда для всех его внутренних узлов х выполняются неравенства и [1(х) — 28(1(х)) [ < Г(х) — 21 з 1 [Е(х) — 21(1(я)) [ < 21'з и*1 — т(я) [Так, например, если Г(я) = 67, то должно выполняться следующее; 1(1(х)) = 32, 33., 34 нлн 35.
Если нужно просто минимизировать высоту дерева, то согласно предыдущему упражнению достаточно, чтобы 3 < 1(1(к)) < 64.] 23. [10[ В основном тексте раздела доказано, что среднее число сравнений, выполняемых любым методом сортировки и элементов. не может быть меньше [16п1) п!бп. Однако при сортировке методом вставок в несколько списков (программа 5.2,154) затрачивается в среднем всего О(п) машинных циклов. Чем это объясняется? 24. [2?[ (К, Пикар (С. Р1сагд).) Постройте такое дерево сортировки для шести элементов, чтобы все его внешние узлы располагались на уровнях 10 и 11. 25.
[11[ Если бы существовала процелура сортировки семи элементов, при которой достатался бы минимум среднего числа сравнений, вычисляемый при помощи формулы (34), то сколько внешних узлов было бы на уровне 13 соответствующего дерева? 26. [М42) Найдите процедуру сортировки для семи элементов, минимизирующую среднее число выполняемых сравнений. ь 22.
[20) Пусть известно, что конфигурации К~ < Кз < Кз, К~ < Кз < Кг, Кз < К~ < Кз, Кз < Кз < Км Кз < К~ < Кз, Кз < Кз < К~ встречаются с вероятностями соответственно .01, .25, .01, .24, .25, .24. Найдите дерево сравнений, которое бы сортировало такие три элемента с наименьпгим средним числом сравнений. 28 [401 Напишите программу для 611, которая сортирует о однословных ключей за минимально возможное время, после чего останавливается.
(См. основные правила в начале раздела 5.2.) 29. [М25) (С. М. Чейз (Б. М. Славе).) Пусть о~аз...а„— перестановка множества [1.,2„...,п). Докажите, что любой алгоритм, который распознает, является лн данная перестановка четной или нечетной (т. е, содержит ли она четное илн нечетное число инверсий), и основанный исключительно иа сравнениях элементов а, должен выполнить не менее и 16 и сравнений, хотя он имеет всего два возможных исхода. выражение [и,е;+з — и;+зш[, (Хотя этот метод использует гораздо меньше информации, чем содержится в полной матрице сравнений, подобной (24), ои, как оказывается, во многих случаях дает оптимальные результаты.) ь 20. [М20[ Докажите, что расширенное бинарное дерево имеет минимальную длину внешнего пути тогда и только тогда, когда существует такое число 1, что все внешние узлы находятся на уровнях 1 и 1+ 1 (илн, быть может, только на уровне 1).
21. [М21[ Высотой расширенного бинарного дерева называется максимальный номер уровня, на котором есть внешние узлы. Пусть х — внутренний узел расширенного бинарного дерева; обозначим через т(к) число внешних узлов-потомков узла х, а через 1(х) — корень левого поддерева узла х. Если х — внешний узел, то положим 1(х) = 1.
Докажите, что расширенное бинарное дерево имеет минимальную высоту среди всех бинарных деревьев с тем же числом узлов тогда и только тогда, когда для всех его внутренних узлов х выполняется неравенство ЗО. [МЗУ[ (Опганмальнал обмвннав соршираеко.) Любой алгоритм обменной сортировки в оютветствни с определением, данным в разделе а.2.2, можно представить в виде дерева сравнений-обменов, а именно — в виде сгруктуры бинарного дерева, внутренние узлы которого имеют вид 1.1, где 1 < у, и интерпретируются следующим образом; "'Если К, < К, то продвинуться по левой ветви дерева; если К, > К„та поменять местами записи » и у и продвинуться по правой ветви дереве", По достижении внешнего узла должны выполняться условия К~ < Кз < .
< К„. Таким образом, дерево сравнений-обменов отличается ат дерева сравнений тем, что оно описывает не только операции сравнения, но и операции перемещения данных. Обозначим через 5,(п) лшнимальное число сравнений-обменов, необходимых в наихудшем случае для сортировки элементов при помощи дерева сравнений-обменов. Докажите, что 5„(п) < В(п) + и — 1, 31.
[МУЗ[ Продолжение упр. 30. Докажите, чта Я,(З) = 3. 32. [МЗЗ[ Прололжение упр. 31. Исследуйте значения функции 5,(»») при малых и > 5. ЗЗ. [МЮ0) (Т. Н. Хиббард (Т. Х. Н1ЬЬаг»)).) Всщвсгавенновначннм деревом поиска порядка х с разрешением З называется расширенное бинарное дерево, каждый узел которого содержит неотрицательное действительное значение, такое, что: (») значение в любом внешнем узле < 3; (б) значение в любом внутреннем узле не превышает суммы значений двух его потомков; (й!) значение в корне равно х.
Данна евевшвннагв пуши такого дерева определяется как сумма по всем внешним узлам номеров уровней этих узлов, умноженных на содержащиеся в них значения, Докажите, что вещественнозначнае дерево поноса порядка х с разрешением 1 имеет длину взвешенного пути, минимальную среди всех таких деревьев того же порядка и с тем же разрешением тогда и талька тогда, когда в (Й) имеет место равенство и для всех пар значений хе и хм принадлежащих узлам-братьям, выполняются следующие условия, (»т) не существует целого числа й > О, такого, что хв < 2" < х~ или х~ < 2 ' < хо; (т) [хв) — хе+ [х») — х» < 1. (В частнаст»», е» зи х — целое чисг»а, то из условия (т) следует, что все значения в дереве — целые, а условие (Ь ) эквивалентно результату упр.
22.) Докажите также, что соответствующая минимальная длина взвешенного пути равна х[13х) + [х) — Зря*), 34. [М50) Определите точные значения функции Я(п) для бесконечного множества аргументов и. Зб. [39) Определите точное значение функции 8(!3), 36. [МЗ0[ (С. О.
Кислилын. 1963.) Докажите илн опровергните следующее утверждение: любой ориентированный ациклический граф С, в котором Т(С) > 1, имеет две вершины, а и «, такие, что диграфы С» и Сю полученные из С в результате добавления луг и»- «и и -» «, также ацикличны и удовлетворяют условию 1 < Т(С»)/Т(С») < 2. (Таким образом, Т(С~)/Т(С) всегда лежит между -' и = при некоторых и и «.) е5.3.2. Слияние с минимальным числом сравнений Рассмотрим теперь вопрос, имеющий отношение к предыдущему разделу: каков наилучший способ слияния упарядочениога множества т элементов с упорядоченным множествам п элементаиу Обозна»им элементы сливаемых множеств А!<Аз«'''А ив»<ВЗ«''"В (1) Как и в разделе 5.3,1, будем предполагать, чта все и» + и элементов различны.
Элементы А» среди элементов Вь могут распада»аться ["'+«) способами. Таким образом, из анализа, которым мы воспользовались в задаче о сортировке, следует, что необходимо выполнить, по крайней мере, (2) сравнений. Если положить гп = оп и устремить и -э оо, оставив о неизменным, то по формуле Стирлинга !8( ) =п((1+а)!8(1+а) — а!йа) — ф!йп+О(1). (3) Обычная процедура слияния (алгоритм 5.2.4М) выполняет в худшем случае гп+ и— 1 сравнений. Обозначим через М(гп, и) функцию, аналогичную Я(п), а именно минимальное число сравнений, заведомо досткгочное для слияния гл элементов с и элементами.
Из только что сделанного вывода следует, что г ч(""")~ и(...) Г-"-1 ° -,»э ~. (4) Формула (3) показывает, насколько далеко могут о.гсгокгь друг от друга нижняя и веРхнЯЯ оценки. ПРи а = 1 (т. е. гп = п) нижнЯЯ оценка Равна 2п — з 1йп + 0(1), так что обе оценки — величины одного порядка, ио разность между ними может быть скаль угодно велика. При а = 0.5 (т. е. гп = -'и) нижняя оценка равна зп(!83 ~~) .~ О(1ойп) что составляет примерно !к3 — 3 ж 0.918 от верхней оценки. С убыванием о разница между верхней и нижней оценками все увеличивается, поскольку стандартный алгоритм слияния разработан, главным образом, для массивов с гл ж и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
