AOP_Tom3 (1021738), страница 4
Текст из файла (страница 4)
24 показано, что можно построить процедуру сортировки шести элементов, требующую всегда девять или десять сравнений; следовательно, этот метод превосходит метод вставок и слияний в среднем и не хуже него в худшем глучае. Пусть Гч(п) -- среднее число сравнений, выполняемых алгоритмом сортировки посредством вставок и слияния; имеем В работе У. Сезаг(, ТЬегбв (Вшк, о( Райэ, 1968), раде 37, показано, что при и = 7 не существует метода сортировки, при котором достигалась бы нижняя граница длины внешнего пути (62 368). (Используя результат упр.
22, этот факт можно доказать самостлзятельно.) С другой стороны, в указанной работе построены процедуры, для которых достигается нижняя граница (34) при и = 9 или 10. Вообще же, задачу минимизации среднего числа сравнений решить гораздо сложнее, чем найти 5(п). Вполне даже возможно, что при некоторых п все методы, минимизирующие среднее число сравнений, в худшем случае требуют более 5(п) сравнений. УПРАЖНЕНИЯ 1. [20] Нарисуйте деревья сравнений для сортировки четырех элементов методами (а) бинарных вставок; (Ь) простого двухпутевого слияния. Каковы длины внешних путей для этих деревьев? 2.
[М24] Докажите, что В(я) < Х,(п), и найдите все значении и, при которых имеет место равенство. 3. [М22] Если допускаются равные ключи, то при сортировке трех элементов возможвы 13 исходов, Кз=Кз=Кз, К!=Кз<Кз, К~=Кз<Кз, Кз = Кз < Кп К~ < Кз = Кз, Кг < К~ = Кз, Кз<Кз=Кз, %<Кз<Къ, Кз<Кз<Кз, Кз < Кз < Кз, Кз < Кз < Кп Кз < К) < Кю Кз < Кг < % Обозначим через Р, число возможных исходов при сортировке и элементов, если допускаются равные ключи, так что (Ра,РпРз, Рз,Рл,Рм, ) = (1, 1, 3, 13. 75, 541,...). Докажите, что производящая функция Р(з) = 2 „> Р„з"Хп', равна 1/(2 — е*). Указаиие.
Покажите, что прил > О. 4. [ХХМ27] (О. А. Гросс (О. А. Огоев),) Найдите асимптотическое выражение для чисел Р„из упр. 3 при и -+ со. [Указаиис. Рассмотрите разложение сос - на элементарные дроби.) 5. [Хб] Если допускаются равные ключи, то каждое сравнение может иметь не два, з три результата: К, < Км К, = Км Л;. > К,. В этом общем случае алгоритмы сортировки можно представлять в виде расширенных гвериаримз деревьев, в которых каждый внутренний узел 1:Х имеет три поддерева (левое, среднее и правое), соответствующие трем возможвым исходам сравнения.
Нарисуйте расширенное тернарное дерево, определяющее алгоритм сортировки для и = 3, если допускаются равные ключе. В взгвем дереве должна быть 13 внешних узлов, соответствующих 13 возможным исходам, перечисленвым в упр. 3. б. [М2в] Пусть 5'(и) — минимальное число сравнений, необходимое для сортировки и элементов и выявления всех равенств между ключами, если каждое сраввение имеет три возможных результата, как в упр. 5. Нетрудно обобщить "теоретико-информационные" аргументы, приведенные в тексте раздела, и показать, что 5 (и) > [1обз Р„], где Р фуикшгя, проапвлизированная в упр.
3 к 4; докажите, что на самом деле 5'(я) = 5(~). 7. [30] Нарисуйте расширенное тернарное дерево, как в упр. 5, для сортировки четырех элементов, если известно, что все ключи равны либо О, либо 1. (Так, например, если К~ < Кз и Кз < К4, то понятно, что Хз з = Кз и Кз = К4!) Добейтесь минимального числа сравнений в среднеи, считая, что все 2 возможных исходных массивов равновероятны. Обратите внимание на то, что должны быть проанализированы все имеющиеся варианты равенств; например, не прекращайте сортировку, если становится известно, что К~ < Кэ < Кз < Кз. 8. [Об) Нарисуйте расширенное тернарное дерево, как в упр. 7, для сортировки четырех элементов, если известно, что ключи — это либо — 1, либо О, либо +1. Добейтесь мидимального числа сравнений в среднем, считая, что все 3 возможных исходных массннов 4 равновероятны. 9.
[МОО) Каково минимальное число сравнений в наихудшем случае при сортировке и элементов, как в упр. 7, когда известно,что все элементы равны либо О,либо 1? ь 10. [М85) Каково минимальное среднее число сравнений при сортировке 0 элементов, как в упр. 7, когда нзвесттю, чта все ключи равны либо О, либо 1? Резулшат представьте в виде функции от и. 11. [7?М97] Пусть 5 (и) — минимальное число сравнений, необходимое в наихудшем случае для сортировки и элементов, как в упр 5, причем известно, чта все ключи принадлежат множеству (1, 2,..., гл). [Таким образом, согласно упр. б 5„(п) = Я(н).) Докажите, что 5 (и) приближается к и!5 т+ 0(1) при фиксировашюм т и и -э оа. э 12.
[М95] (У. П Буриснус (Ч'. С. Воипсщз), ок. 1954 г.) Предположим, что равные ключи могут встречаться. но наша цель — - рассортировать элементы (Кп Км..., К„) таким образом, чтобы сформировать перестановку а~ аэ .. а, удовлетворяющую условию К, < К„« К,„, нам не важно, имеет ли место равенство между элементами К„, и К„ Будем говорить,что дерево сравнений сильно сортирует последовательность ключей, если опо сортирует ее в вышеуказанном смысле, независимо от тога, какой путь выбран в узлах !.
1, для которых К, = К,. (Дерево бинарное, а не тернарнае ) а) Докажите, что дерево, не содержащее избыточных сравнений, сильно сортирует любую последовательность ключей тогда и только тогда, когда оно сортирует любую последовательность различных ключей Ь) Докажите, что дерево сравнений сильно сортирует любую последовательность ключей тогда и только тогда, когда оно сильно сортирует любую последонательнасть нулей н единиц 13. [М90) Докажите утверждение (17). 14. [М94] Выразите сумму (19) в замкнутом виде 15. [М81) Определите асимптотическое понедение функций В(п) и Е(п) с точностью до О(!об и).
[Указание. Покажите, что в обоих случаях коэффициент при и содержит функцию, изображенную на рис. 37.) 16. [НМЯб) (Ф. Хванг (Р. Нжапб) и Шень Линь (Я. 1лп).) Докажите, что при и > 22 выполняется неравенство В(п) > [!5п!]. 17. [МЮО] Докажите тождество (29). 18. [20) Предположим, что процедура, начало которой изображено на рнс. 36, породила граф с эффективностью 12!/2ы. Доказывает ли это, что В(12) = 29? 19.
[40) Проведите эксперименты со следующим эвристическим правилолг принятия решения, какую пару ключей сравнивать следующей при конструировании дерева сравнений. Пусть на каждой стадии сортировки ключей (Кп..., К,) число ключей, о которых на основании выпавненных да сих пор сравнений известно, чта они < К„обозначается через и„а число ключей, о которых известно, что они > К„обозначается через и„ 1 < ! < и.
Перенумеруем ключи так, чтобы последовательность и,/а, стала возрастакпцей: и~/а~ < иэ/аэ < . < и„/а„. Теперь сравним К,: Кы.м где ! — индекс, минимизирующий 21. [М21] Вмсошой расширенного бинарного дерева называется максимальный номер уровня, на котором есть внешние узлы. Пусть х — внутренний узел расширенного бинарного дерева, обозначим через 1(х) число внешних узлов-потомков узла х, а через 1(х) - — корень левого полдерева узла х. Если з — внешний узел, то положим 1(х) = 1. Докажите, что расширенное бинарное дерево имеет минимальную высоту среди всех бинарных деревьев с тем же числом узлов тогда и только тогда, когда для всех его внутренних узлов х выполняется неравенство ]1(х) — 21[1(х))] < 21 э и<0 — 1(х).
22. [ЛЩ] Продолжение упр. 21. Докажите, что бинарное дерево имеет минимальную длину внешнего пути среди всех бинарных деревьев с тем же числом узлов тогда и только тогда, когда для всех его внутренних узлов х выполняются неравенства и ]1(х) — 21(1(х)П < 1(*) — 2~ э 1 И. ]1(х) — 21(1(х))[ < 2пэц  — 1(х) [Так, например, если 1(х) = б?, то должно выполняться следующее: 1(1(х)) = 32, 33, 34 или 35. Если нужно просто минимизировать высоту дерева, то согласно предыдущему упражнению достаточно, чтобы 3 < 1(1(х)) < 64.] 23.
(10] В основном тексте раздела доказано, что среднее число сравнений, выполняемых любым методом оэртировки и элементов, не может быть меньше [)бп!] о13я. Однако при сортировке методом вставок в несколько списков (программа 5.2.1М) затрачивается в среднем всего 0(п) машинных циклон. Чем это объясняется? 24. [27] (К. Пикар (С. Р!сэгд).) Постройте такое дерево сортировки для шести элементов, чтобы все его внешние узлы располагались на уровнях 10 и 11. 25. [11) Ешли бы существовала процедура сортировки семи элементов, при которой достигался бы минимум среднего числа сравнений, вычисляемый при помощи формулы (34), то сколько внешних узлов было бы на уровне 13 соответствующего дерева? 26. [м42] найдите процедурусортировки для семи элементов, минимизирующую среднее число выполняемых сравнений.
ь 27. [20] Пусть известна, что конфигурации К~ < Кэ < Кэ, Кл < Кэ < Кг, Кэ < Кл < Кэ, Кэ < Кэ < Кы К» < К~ < Кю Кэ < Кэ < Кл встречаются с вероятностями соответственно .01, 25, .01, .24, .25, .24. Найдите дерево сравнений, которое бы сортировала такие три элемента с наименьшим средним числом сравнений. 28. [40] Напишите программу для й1Х, которая сортирует 5 однословных ключей за минимально возможное время, после чего останавливается.
(См. основные правила в начале раздела 5.2.) 29. [М25] (С. ХЕ Чэйз (Б. М. СЬэзе).) Пусть а~ аэ...о — перестановка множества (1, 2,..., и). Докажите, что любой алгоритм, который распознает, является ли данная перестановка четной или нечетной (т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
