Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 93
Текст из файла (страница 93)
[Вази(от Беги«гизев Вз А18огййтз, 5 (1994), 102-104.] Кь(п) = г„' ~з = Х~ ~ь, Имеем п — 4 — 1 = аз + .. + а„если в дереве г + 1 листьев и (Ь + 1)-й лист имеет аз — 1 предков, отличных от предков первых Ь листьев. (Приведенные семь примеров деревьев соответствуют суммам в правой части 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2 и 3+1.) РАЗДЕЛ 5.4.3 1. Выясняя с помощью табл. 5.4.2-6, сколько раз в среднем обрабатывается каждая запись, видим, что многофазный метод с расщеплением лепт лучше, если имеется б, 7 или 8 лент.
2. Методы, по существу, тождественны, если число начальных серий является числом фибоначчи; в противном случае способ распределения фиктивных серий лучше у многофазного метода. Каскадный алгоритм помещает 1 на Т1, 1 на Т2, 1 на Т1, 2 на Т2, 3 на Т1, 5 на Т2 и т. д. Поэтому на шаге С8 никогда не обнаружится, что В(р — 1) = М(р — 1), если р ж 2. В результате все фиктивные серии оказываются на одной ленте„а это менее эффективно, чем метод алгоритма 5.4.211.
3. (Распределение заканчивается после того, как 12 серий помещаются на Т3 на шаге (3,3).) Т1 Т2 ТЗ Т4 Т5 1" 1ы 1» — 1ы 1»27 1 8' 6'0' 5' 6* — 9' 23' 17' 25' 100 1 2~4ш 4. Доказывается по индукции (см. упр. 5.4.2-28). 5. Если имеется а„начальных серий, то Ь-й проход выводит а„» серий длиной а», затем Ь„» — длиной Ь» и т. д, 1 1 1 1 1 1 1 1 1 0 о о ооо ОООО у. сзс »+с»с -э+ .
+с~со дэнн начальных серий (см. упр. 5), что может быть также записано в виде о»а„з + аза„з + + оа еоо; это коэффипиент при [з" з) в (А(з)»в А(з)), 9. Эти формулы справедливы для всех большов к из (8) и (12), если иметь в виду значение дм(2в)п д»). Чтобы показать, что они справедливы при всех н, необходимо знать, чч о о,„~ (з) есть частное от деления ф-з (з)д (г) на д„(з) — з при 0 < т ( г. Это можно доказать, либо используя (10) и учитывая, что при сокращении степень д„~(з)о„,(з)— ф(з)д ~(з) снижается, либо учитывая„что из результата упр. 5 следует, что А(з) + В(з)" + + Е(в)з -+ 0 при з -+ оо, либо найдя явную формулу для числителей В(з)„ С(з) и т. д. 10. Е(з) = гз(г)А(х); В(х) = гз(з)А(з)-гд(з); С(з) = гз(з)А(з) — гз(з): В(з) = г»(з)А(з)— гз(з); А(з) = г»(з)А(з)+1 — г»(з).
Таким образом, А(з) = (1 — г»(з))/(1 — г»(з)). (Обратите внимание на то, что г (2 в!и 6) = гйв(2глй)/совд„следовательно, г (з) является многочле- ном Чебышева (-1) +'1/~ -~(з/2).) 11 Докажите, что /~(з) = 01~!»1(з) — г1 дп(з) и что /т(з)/~-~(з) = 1 — г~(з).
Затем используйте результат упр. 10. (Это выражение лля знаменателя в явном виде впервые было выведено Девндом Е. Фергюсоном (Рат(6 Е. Регбожш).) 13. См. упр. 5.4.6-6. 8. Знаменатель А(з) имеет различные корни, и его степень выше степени числителя, поэтому А(з) = 2 оз(р)/(1-рз)р(1 — о»(р)), где сумма берепи по всем корням р уравнения о»(р) = р. Этот специальный вид р полезен прн вычислении 33(р) и о»(р). РАЗДЕЛ 5.4.4 1.
Сначала (перед выводом восходящей серии) следует записать концевую запнсзп содержащую -оо. (Запись с ключом +оо по-прежнему должна располагаться в конце серии, если только мы собираемся когда-лпбо считывать ее в прямом направлении, например на последнем проходе,) Для нисходящих серий поменять ролями -оо и +со. 2. Наяменыпее число на уровне и+ 1 равно наибольшему на уровне и; следовательно, столбцы являются неубывающими независимо от того, как переставлены числа в любой отдельной строке. 3. На самом деле в процессе слияния первая серия на Т2-Тб всегда будет нисходящей, а на Т1 — восходящей (по индукции).
4. Такой метод требует нескольких операций "копирования" на втором и третьем проходах; дополнительиме затраты приблизительно равны (!ой 2)/(!обр) проходам, где р— потношение роста" «см. табл. 5.4.2-1). Ь. Если а — цепочка„обозначим через он ее обращение. Т4 Т1 12 1232 1232 323432 12323432 12323432 2323432 3432 Сп Зуп Еп где Яп = Оп-1(44п-4+1)(за-4+ 2)(Я 4+3)Яп-4+ 4), и > 1, ч)е ' О и цепочка (г„ы е при и < О. Цепочки Ап, В, ... содержат те же элементы, что и соответствующие цепочки из раздела 5.4.2, но в другом порядке. Заметим, что соседние числа слияний всегда рвзвичаютгя на 1. Начальная серия должна иметь тип .4 тогда и только тогда, когда число ее слияний четно, 42 — если нечетно.
Простые схемы распределения, такие, как в алгоритме 5.4.20, уступают в эффективности размещению фиктивных серий в позиции с большими числами слияний; поэтому, вероятно, выгодна вычислять 44 между фазами 1 и 2, чтобы облегчить управление процессом размещения фиктивных серий. и+1 й„(АЯ4 Ц Сп(А„"+Ц 42„(А~+И Е„(А„"ч Ц АЯ4-1 Имеем А,",, +1, А,", зА,",, +1, Ал зАЯ зАл, +1, А -4А -з.4„зАп-1+ 1, Ап-зАв-4Ап-зА"-зА"-1+ 1 и-Я„ 2 3 4 3 4 4 3 2 3 4 3 2 3 2 2 3 4 3 4 5 4 3 2 ЗЗ 4 33 2 3 В. уйб=(+1,+1,-1,+1) рыб=(+1, б,-1, О) у"~ = (+1,— 1,+1,+1) у(П = (-1, +1, +1, +1) „ю> 7 Число 34 является, вероятно, наименьшим числом Фибоначчи Р„, для которого многофашюый метод не дает оптимального слиянии с обратным чтением для Г„начальных серий иа трех лентах.
Это дерево имеет длину внешнего пути 178, что на 2 лучше, чем и многофазном методе, для которого соответствующий параметр равен 176, 8. Для Т = 4 дерево с длиной внешнего пути 13 не является ТАИо-деревом, и любое дерево с длиной внешнего пути 14 включает однопутевое слияние. 9. Используя результат упр, 2.3.4.5-6, можно рассмотреть полное (Т вЂ” 1)-арное дерево; степень "последнего" внутреннего узла лежит между 2 и Т вЂ” 1. Если в нем имеется (Т-1)г -т внешних узлов, то ( гл~(Т вЂ” 2)) из них находятся на уровне д — 1, а оставшиеся— на уровне 4.
11. Верно, что доказывается индукцией по числу начальных серий. Если правильное распределение Я сирий и две соседние серии находятся в одщшковом направлении, то существует нужное распределение меньшего, чем Я, числа серий, но его не существует при 8=1. 12. Условия (а) н (Ь) очевидны. Если имеется какая-нибудь конфигурация в (4) для некоторого имени ленты А и некоторых 1 < у ч и, то узел у должен быть в поддереве ниже узла 1 и слева от узла 1 ло определению прямого порядка.
Следовательно, случай "У вЂ” Г не может иметь места и А должно быть "специальным" именем, так как оно появляется на внешней ветви. Бо зто противоречит тому, что специальное имя, как мы предположили, находится на крайней слева ветви ниже узла 1 13. Узлы, пронумерованные 4, 7, 11, 13, можно преобразовать во внешние, и по отношению к ним не нужно использовать олнопутевое слияние. В результате двина внешнего яути будет на единицу больше, чем в случае многофазного дерева. 13. Назовем ленты А, В и С.
Построим несколько видов деревьев, каждый нз которых характеризуется определенной структурой корня и листьев (внешннх узлов). Тип г(А) Тип з(А, С) Тип 1(А) Тип и(А,С) Тнп о(А, С) Тип ю(.4, С) Корень А Корень А; Корень А; Корень А; Корень А; Корень А; нет С-листьев нет А-листьев нет С-листьев,нет составных В-листьев нет С-листьев, нет составных А-листьев нет А-листьев, иет составных С-.чистьев г(н) = и+ вшаь(в(Ь) + г(п — Ь)), в(н) = п+ пнаь(е(Ь) + ю(п — Й)), а(п) = и+ пипа(л(Ь) +1(п — Ь)), е(в) = в+швпь(и(Ь) + ю(н — Ь)), 1(н) = и+ ппвь(и(Ь) + е(н — Ь)), и~(н) = н+ ш1вь(в(Ь) + и(н — Ь)).
Отсюда следует, что г(н) < е(н) < и(п), а(н) < е(в) и г(п) < Ф(п) < ю(н) для всех п; кроме того, а(2н) = 1(2п + 1) = оо. (Последнее было очевидно априори.) Пусть А(н) — функция, определяемая правилами А(1) = О, А(2н) = 2п+ 2А(н), А(2п+ 1) = 2н + 1 + А(я) + А(н + 1); тогда А(2п) = 2п + А(в — 1) + А(п + 1) — (О нли 1) для всех и > 2. Пусть С вЂ” константа, такая, что прн 4 < и < 8 1) для четных и имеем ю(н) < А(п)+ Сп — 1; й) двя нечетных и имеем в( ) и и(п) оба < А(н) + Св — 1. (Это в действительности справедливо для всех С > е.) По индукции получаем, что эти соотношения верны для всех и > 4 (в качестве подходюцего Ь выберем [и/21 ж 1).
Но А(п) является нижней оценкой в (9), если Т = 3 и г(п) < ппп(в(п), о(н), ю(п)); таким образом, мы доказали, что А(п) < Кз(п) < г(п) < А(п) + ел — 1. [Здесь константа ~1 может быть уменьшена.) 17. [Этот метод использовался в программе сортировка для ШЯ!гАС Ш н в 1962 году был представлен на симпозиуме АСМ Ботс Яушроэьпш.[ Тб 0 1 15 Т4 0 2 29 Уровень 0 1 2 Т1 1 5 55 Т2 0 50 ТЗ 3 41 н и~ н+1 5о +45„+ 4о„+45„+ За +ЗЬ + 2а +2Ь„+ Зс +24 +с„Зс„+Зо„+с„Зс„+2о„+е 2с„+24 +е ее ан+Ь + с„+о„+е„ "Составной лист" — это лист, "брат" которого не является листом.
Можно получить 3-Иодерево типа г(А), вырастив сначала его левое поддерево типа а(В, С), а затем — правое поддерево типа г(С). Аналогично тип е(А,С) получается из типов э(В,С) и 1(С)., тип в(А,С) — яз е(В,С) и ю(С,В); тип и(А,С) — из и(В,С) и ю(С,А). Можно вырастить 3-й(о-дерево типа 1(А), левое поддерево которого имеет тип и(В, А), а правое подлерево —. тип в(С, А), позволив вырасти его левому поддереву, за исключением его (несоставных) С-листьев и его правого полдерева. В этот момент левое поддерево имеет только А- и В-листья, так что мы можем вырастить правое поддерево всего дерева, затем выбросить А-листья нз левого-левого поддерева и, наконец, вырастить левое-правое поддерево.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
