Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 123
Текст из файла (страница 123)
Затем процедура Р1в-НВАР-Ехтклст-Мвч удаляет узел х из фибоначчиевой пирамиды. Амортизированное время работы Р1В-НВАР-Рн.ете представляет собой сумму амортизированного времени работы 0(1) процедуры Р1в-НВАР-Рескелее-Кеу и амортизированного времени работы 0(Р(п)) процедуры Р1в-НВАР-ЕхткАстМ1н. Поскольку в разделе 19.4 мы увидим, что Р(п) = 0(!ли), аморгизированное время работы процедуры Р1В-неАР-Рн.ете составляет 0(!ли).
Упражнения 19.3.1 Предположим, что корень х в фибоначчиевой пирамиде помечен. Поясните, как узел х мог стать помеченным корнем. Покажите, что тот факт, что х помечен, не имеет никакого значения для анализа, даже если это не юрень, который сначала был привязан к другому узлу, а затем потерял один дочерний узел. 19.3.2 Докажите оценку О(1) амортизированного времени работы процедуры Р1вНВАР-РескеАзе-Кеу как средней стоимости операции с использованием группового анализа. 19.4.
Оценка максимальной степени Для доказательства того факта, что амортизированное время работы процедур Р1в-НВАР-ЕхткАст-Мпч и Р1в-НеАР-Рееете равно О(!кп), необходимо показать, что верхняя граница Р(п) степени произвольного узла в фибоначчиевой пирамиде с п узлами равна О(!кп). В частности, следует показать, что Р(п) ( ~!оба п~, где ф — золотое сечение, определяемое формулой (3.24) как ф = (1 + ъ'5)/2 = 1.61803 .. Часть К Сложные структуры данньи 5бО Ключевым моментом анализа является следующее.
Для каждого узла х в фибоначчиевой пирамиде определим з1ге(х) как количество узлов в поддереве, корнем которого является х, включая сам узел х (заметим, что узел х не обязательно должен находиться в списке корней; это может быть любой узел фибоначчиевой пирамиды). Покажем, что величина з(ге(х) экспоненциально зависит от х.
Недсее (напомним, что атрибут х. Иедгее всегда содержит точное значение степени х). Лемма 19.1 Пусть х — произвольный узел фибоначчиевой пирамиды, и предположим, что х. Недгее = lс. Обозначим через ум уз,...,уь дочерние узлы х в том порядке, в котором они связаны с х, начиная с более ранних и заканчивая более поздними. Тогда у1. Йедгее > О и у,. Йедгее > ( — 2 для ( = 2, 3,..., (с. Доказательство. Очевидно, уп с1едгее > О.
Для ( > 2 заметим, что, когда у, связывается с х, все узлы ум уз,..., у; 1 являются дочерними узлами х, так что в этот момент должно выполняться х. с(едгее > ( — 1. Узел у, связывается процедурой СомзощпАтн с х только в случае, когда х. Недгее = у,. с(едгее, так что в этот момент мы должны также иметь у;. Недгее > ( — 1. С этого момента узел у; мог потерять не более одного дочернего узла, поскольку при потере двух дочерних узлов он должен быть вырезан у узла х процедурой Слзслппчс-Сит.
Отсюда следует, что у;. Иедгес > ( — 2. Сейчас мы подошли к той части анализа, которая поясняет название "фибоначчиевы пирамиды". Вспомним, что в разделе 3.2 й-е число Фибоначчи (к О, 1, 2.....) определяется с помощью рекуррентного соотношения если 1 = О, если к = 1, + Гь-з, если lс > 2 Приведенная далее лемма дает еще один способ выражения е~,. Л 19.2 Для всех целых чисел к > О Рььз =1+ ~ ~'~;. с=о Доказательсаьво. Доказательство выполняется по индукции по сс. Когда к = О, о 1 + ~~', е) = 1 + го с=о = 1+0 !!сава !Д Фибоначчиеаы иирамиды зб! По индукции предполагаем, что Р'в+1 = 1 + 2;1 О Гс, и имЕЕм Ь-1 6~с+2 = Р'Ь + Ей+1 =1+,'ГК,.
с=о Лемма 19.3 (!с+2)-е число Фибоначчи для всех целых к > О удовлетворяет условию Гь.1.2 > ф". -ев+2 = с" в+1 + ев > ФЬ вЂ” 1+ф!с — 2 = Ф~ '(Ф+1) Фь-г Фг =Ф" (согласно гипотезе индукции) (согласно уравнению (3.23)) Следующая лемма и следствие из нее завершают анализ. Лемма 19.4 Пусть х — произвольный узел фибоначчиевой пирамиды и пусть к = х. с(едгее. Тогда в12е(х) > Еь1.2 > ф", где ф = (1+ Л)/2. Доказааеельеаево.
Обозначим через вь минимально возможный размер любого узла степени к в произвольной фибоначчиевой пирамиде. Случаи во = 1 и в1 = 2 тривиальны. Число вь не превышает величины в12е(х) и, поскольку добавление дочерних узлов к узлу не может уменьшить его размер, значение вь монотонно возрастает с возрастанием )с. Рассмотрим некоторый узел 2 в произвольной фибоначчиевой пирамиде, такой, что 2. с(едгее = )с и в1ге(2) = вь.
Так как вь < в!ге(х), мы вычисляем нижнюю границу в12е(х) путем вычисления нижней границы вы Как и в лемме 19.1, обозначим через уз,уг,...,уь дочерние узлы г в порядке их связывания с 2. При вычислении нижней границы вь учтем по единице для Доказавеельсасво, Докажем лемму с помощью математической индукции по !с. Базой индукции служат значения )с = О и !с = 1. При 1 = О мы имеем Ег = 1 = ФО, а при к = 1 — Ез = 2 > 1.619 > Ф1.
Шаг индукции выполняется для )с > 2, и мы считаем, что Г,+2 > Ф' для с = О, 1,..., к — 1. Вспомним, что Ф— положительный корень уравнения (3.23), хг = х + 1. Таким образом, мы имеем Часть и Схажные структуры данных 562 самогб 2 и для его первого дочернего узла уз (для которого агае(уз) > 1). Тогда в(яе(х) > вь к > 2+~~ь в„, д ь=2 й > г+')" в;,, где последний переход следует из леммы 19.1 (так что уы Недтее > 1 — 2) и монотонности вь (так что в„,. д, > в, 2). Покажем теперь по индукции по )с, что вь > Раз.з для всех неотрицательных целых к.
База индукции при )г = О и )г = 1 доказывается тривиально. В качестве шага индукции мы предполагаем, что )е > 2 и что в, > Е,+2 при 1 = О, 1,..., к — 1. Тогда ь вь > 2+ ~ вз-2 З=2 ь >2+Х, 'Г; с=2 ь ен1+~Г, =о = ГЬ~2 > фь (согласно лемме 19.2) (согласно лемме 19.3) . Таким образом, мы показали, что в)яе(х) > вь > Еь+2 > ф". Следсаевие 19.5 Максимальная степень Р(п) произвольного узла в фибоначчиевой пирамиде с и узлами равна 0(1к и). Упражнения 19.4.1 Профессор утверждает, что высота фибоначчиевой пирамиды из и узлов равна О(1к п). Покажите, что профессор ошибается и что для любого положительно- Даказааеельслевв. Пусть х — произвольный узел в фибоначчиевой пирамиде с и узлами и пусть к = х.
«(едтее. Согласно лемме 19.4 и > з1ае(х) > ф". Логарифмируя по основанию ф, получаем /с ( 1ояд п (в действительности, так как Й вЂ” целое число, )е < ~1ойе п)). Таким образом, максимальная степень Р(п) произвольного узла равна 0(1к и). 563 Глава !я Фибаиаччиввы иЧииииды го п имеется последовательность операций, которая создает фибоначчиеву пирамиду, состоящую из одного дерева, которое представляет собой линейную цепочку узлов.
19.4.2 Предположим, что мы обобщили правило каскадного вырезания, н что узел х вырезается у родительского узла, как только теряет Й-й дочерний узел, где Й— некоторая константа (в правиле из раздела 19.3 использовано значение к = 2). Для каких значений к справедливо соотношение Р(п) = 0(1й и)? Задачи 19.1.
Альтернативная реализация удаления Профессор Пизано предложил следующий вариант процедуры Р1в-НвАРРн.нтн, утверждая, что он работает быстрее для случая удаления узла, не являющегося тем, на который указывает Н. т1п. Р!ЗАХО-РЕйЕТЕ (Н, х) 1 Кх == Н.гп1п 2 Р!н-НеАР-ЕхткАст-М1х(Н) 3 е1аед = х.р 4 1в д ф Х11, 5 Сит(Н,х,д) б САвОАО1хО-С От (Н, у) 7 Добавить дочерний список х к списку корней Н 8 Удалить х из списка корней Н а. Утверждение профессора о быстрой работе процедуры частично основано на предположении, что строка 7 может быть выполнена за время 0(1).
Что неверно в этом предположении? б. Оцените верхнюю границу фактического времени работы процедуры Р1зАхоРн.нтв, когда х не является Н. т)п. Ваша оценка должна быть выражена через х. Иедгее и количество с вызовов процедуры САВОАО1ХО-СОТ, а Предположим, что мы вызываем Р1ВАХО-РВ1.ВТЕ(Н, х) н что Н' — полученная в результате фибоначчиева пирамида. Считая, что х не является корнем, оцените потенциал Н', выразив его через х, аедгее, с, 1(Н) и гп(Н). * Сделайте вывод о том, что амортизнрованное время работы процедуры Р!ЯАхО-Реьете асимптотически не лучше времени работы процедуры Р1вНдА9-Рд1.нтн, даже когда х ~ Н. т1п.
565 Глава!я Фибаиаччиевы вираииды Бинамиальная пирамида (Ь1пош(а! леар) Н представляет собой множество биномиальных деревьев, удовлетворяющее следующим свойствам. 1. Каждый узел имеет атрибут кеу (как и фибоначчиева пирамида). 2. Каждое биномнальное дерево в Н подчиняется свойству неубывающей пирамиды. 3. Для любого неотрицательного целого числа к в Н имеется не более одного биномиального дерева, корень которого имеет степень /с. б. Предположим, что биномиальная пирамида Н всего имеет и узлов. Рассмотрите взаимосвязь между биномиальными деревьями, из которых состоит Н, и бинарным представлением п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
