AOP_Tom3 (1021738), страница 184
Текст из файла (страница 184)
Следовательно, ответ есть -и+ э — э( — -) — (1) пРи и > 1. (ЭтУ тачнУк) фоРмУлУ можно сРавнить с теоретико-информационной оценкой нижней границы 1обэ(2" — 1) 0.6309п.) 11. То, что Я (и) < В(т) + (и — гл)(!6(гл + 1)) при и > пз, можно доказать, используя методику бинарных вставок. С другой стороны, Я (и) > !!6) '",(,")Ы), а предел правой части равен и !6 т»- О(((гл — 1)/гп)") (см. формулу 1.2.6--(53)).
12. (а) Если избыточные сравнения не выполняются, то равным ключам. когда они сравниваются впервые, можно приписать произвольное отношеняе порядка, поскольку это отношение порядка нельзя вывести из предыдущих сравяений. (Ъ) Предположим, что дерево сильна сортирует любую последовательность нулей и единиц.
Покажем, что оно сильна сортирует лкзбую перестановку элементов (1,2,,п). Пусть это не так, т е. существует перестановка, которую она якобы упорядочивает, как Л;, < К„« Л„„, но в действительности существует С прн котором К, > К„,„,. Заменим нулями все элементы < Ксм и единицами — все элементы > К,; по предположению наш метод рассортирует полученную перестановку, если выбрать путь, ведущий к К„< К„« Кь„. Значит, мы получили противоречие. 13. Если и четко, то Р(п) — Р(п — 1) = 1+Р((п/2!) — Г((п/2) — 1) и нам нужно доказать, что шь ~ < (и/2) < шь:, это очевидно, поскольку шь ~ = (»оь/2). Если и нечетна, то Е(п) — Р(п — 1) = Г((п/2)) — Г((п/2) ) и нам нужно доказа~ь, что !ь» < (и/2) < 1гб это очевидно, поскольку !ь» = (щь/2). 14. Согласно упр.
1.2.4-42 эта сумма равна и(!6 1п) — (щ~ + . + ш,), где шз < и < шз» ь Последняя сумма равна шз ~ — (1/2) — 1, Следовательно, Е(п) можно записать в виде и (!6 »и) — (2~~хм"~~/3) + (з !6(бп)) (а также многими другими способами.) и й М о 3 о О, й Е й Ф Ы а а Р. Ю 15. Если [!8 си) = 18(зи) +д, то Е(и) = и!Зи — (3 — !83)и+ и(0 + 1 — 2 ) + О(!об и). Если [!8 и! = 18 п + 6, то В(и) = и !8 и — и + и(6 + 1 — 2 ) + О(!об и).
[Обратите внимание на то, что 18 и! = и!8и — и/(!л2) + О(!оби); 1/(!и 2) 1.443; 3 — !83 1.415.[ 17. Число случаев, когда Ьь < ар < Ььеп равно (т — р+и — й) (р — 1+1) а число случаев, когда ар < Ьс < о, и равно (и — д+т — 1) (д — 1+у) 18. Нет, поскольку мы рассматриваем всегда наименее эффективную ветвь пад каждым узлом-сравнением, Одна из базее эффективных ветвей могла бы оказаться более трудаемкай. 20. Пусть б — максимальный номер уровня, на катарам есть внешние узлы, а ! — такой минимальный номер. Если Е > 1+ 2, то на уровне б можно удалить два узла и поместить их под некоторым узлом на уровне 1; в результате длина внешнего пути сократится на 1+ 2б — (с' — ! + 2(! + 1)) = 7 — 1 — 1 > 1. Обратно, если 2 < 1+ 1, то пусть й внешних узлов находятся на уровне 1 и ссс — Ь узлов — на уровне (+ 1, где 0 < Ь < Ж.
Как показано в упр, 2.3.4.5-3, Ь2 + (7р' — й)2 ' = 1; следовательно, Х 4 Ь = 2с '. Иэ неравенств 2' < 1р' < 2ыл вытекает, что 1 = [!8Х), отсюда определяется значение Ь, а также получается длина внеспнего пути (34). 21. Пусть г(х) — корень правого поддерева узла х. Все поддеревья будут иметь минимальную высоту тогда и талька тогда, когда [!81(1(х))1 < [!8!(х)1 — 1 и [!81(г(х))~[ < [181(х)~! — 1 для всех х Первое из них эквивалентно условию 21(1(х)) — 1(х) < 2цкс!  — 1(х), а второе -- условию 1(х) — 21(!(х)) < 2 "е'Сс0 — 1(х).
22. Согласно упр. 20 четыре условия, [!81(1(х))), [!81(г(х))) > [!81(х)) — 1 и [!8 !(1(х))), [!81(г(х))) < [!81(х)) — 1, необходимы и достаточны. Рассуждая, как в упр. 21, можно доказать, чта ани эквивалентны сформулированным в условии этого упражнения неравенствам. [См. Магсш Банс!е!!не, АММ 68 (1961), 133-134.[ Распространение этога решения на абший случай приводится в упр. ЗЗ. 23. При сортировке посредством вставок в несколько списков предполагается, что ключи равномерно распределены в известном диапазоне, значит, ан не принадлежит к числу методов "чистых сравнений", удовлетворяющих ограничениям, которые рассматриваютсн в этом разделе.
24. Действуйте сначала, как при сортировке пяти элементов, до тех пар, пока не получите одну из конфигураций (6). В первых трех случаях завершите сортировку пяти элементан при помаши еще двух сравнений, послЕ чЕго вСтаньтЕ сиегтой элЕмент 1. В последнем случае нужно сначала сравнить г':Ь, вставить у в главную цепочку, а затем вставить с. [Ргсатд, ТЬеог!е с(ез 1)неэС!анна!гез, раде 116.) 25. Поскольку ср' = 7! = 5040 и 9 = 13, было бы 8192 — 5040 = 3152 внешних узла ва уровне 12 и 5040 — 3152 = 1888 внешних узяов на уровне 13. 26.
В работе 1.. Кайаг, Ъессоге №сее ш Сошр. Ясб 233 (1986), 449 — 457, представлен прекрасный способ проверки утверждения, что оптимальный метод сортировки дает путь длиной 62 416. 27. Это единственный способ распознать две наиболее часта встречающиеся перестановки за два сравнения, несмотря на то что первому сравнению соответствует разбиение с вероятностью .27/.73. 28 Лунь Куань [Ьвп Кжап) составил программу длиной 873 строки, среднее время работы которой равно 38.925в. Максимвлыгое время ее работы равно 43в; по-видимому, оно оптимально, поскольку как раз столько времени требуется ~шя выполнения 7 сравнений, 7 проверок, б эагрузок и 5 записей в память.
29. Не выполнив 5[п) сравнений, невозможна дать однозначный ответ, какой является перестановка: четной или нечетной. В самом деле. если предположить, что в результате выполнения некоторого числа сравнений мы "сузили" задачу до такой степени, что осталось всего два возможных исхода в зависимости от того, будет ли а, меныпе или больше а,, где 1 и 1 — некоторые индексы, то один из этих возможных исходов — четная перестановка, другой — нечетная. [С другой стороны, для решения этой задачи сущесшерет алгоритм с временем работы 0[п); он просто подсчитывает количество циклов и вовсе не содержит сравнений; см, упр.
5.2 2-2.) 30. Возьмите оптимальное дерево сравнений высотой Я[п). Лвигаясь сверху вниз, меняйте местами 1 <-+ 1 в правом поддереве узла 01'. В полученном дереве, которое интерпретируется как дерево сравнений-обменов, каждый концевой узел определяет единственную перестановку, а ее можно рассортировать не более чем за и — 1 дополнительных сравнений- обменов [эта показано в упр. 5.2.2-2).
[Идея дерева сравнений-обменов принадлежит Т. Н. Хиббарду [Т. Х. Н1ЬЬатб).) 31. Необходима не менее 8 сравнений-обменов, поскольку в любом дереве 5 с высотой 7 существует ветвь, которая после 4 шагов приведет к конфигу- е рации, где а ф 1 [или двойственной по отношению к ней). Эту конфигу- 4 рацию нельзя рассортировать за три операции сравнения-обмена. С другой стороны, ниже показано дерево, на котором достшпется искомая нижняя граница оценки [а также, быть может, минимальное среднее число сравнений-обменов). чво ЗЗ.
К любому дереву порядка х с разрепзением 1 можно применить простую операцию для получения другога дерева, длина взвешенного пути которого не превышает длины пути исходного дерева, причем: (а) существует такое чис ю к, что все внешние узлы лежат на уровнях )с и й — 1, (Ь) не более чем алин внешний узел содержит нецелое значение, и если таковой имеется, то он находится на уровне !г. Длина взвешенного пути любога такога дерева имеет указанное значение.
так чта оно должно быть минимальным. Обратно, если в вещественнозначпом дереве поиска выполняются условия (и ) и (т), та, применив индукцию, можно паказатгч что длина взвешенного пути имеет указанное значение, поскольку для этого параметра существует простая формула, выражающая ее через длины путей двух поддеревьев корня.
35. Ключ к решению этой задачи содержится в безуспешных экспериментах, описанных в работе КипСЬ, КаеИег, 1п1огтайоп Ргосевв!п8 1 есвегв 1 (1972), 173 — 176. 36. Слз. Математглческие заметки 4 (1968), 511 518. Обзор достижений в решении этой зюгачи представлен в работе 8, ге!впег, %. Т. Тгосзег, .Сот!з!пвсаг!св,. Раа! ЕИов !в Е!ЗИсу 1 (1993), 145-157. Там же доказано, чта мы всегда можем получить 1 < Т(Слл(Т(Сз) < р, где константа р чуть-чуть меньше 8/3.
РАЗДЕЛ 5.3.2 1. Я(т + а) < Я(т) + Я(п) -Ь М(гл. п) 2. Внутренний узел, который является )с-м па счету при отношении порядка, симметричном к исходному, соответствует сравнению Лл: Вл. 3. Стратегия В(1,1) не лучше стратегии А(1, !+1), а стратегия В'(1,!) не превосходит стратегии А'(1,1 — 1). Слеловательно, нужно разрешить рекурреитнае соотношение .М.(1, и) = ппп щах(шах(1+ М.(1, ! — 1)), плах (1+.М.(1, и — !))), и > 1; л<з< лй~бз з<13 .М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
