Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 119
Текст из файла (страница 119)
20.4 Оценка максимальной степени Для доказательства того факта„что амортизированное время работы процедур Р!в Неав ЕхткАст М!н и Р!в НВАР Реьете равно 0(1ки), мы должны показать, что верхняя граница Р (и) степени произвольного узла в фибоначчиевой пирамиде с и узлами равна 0 (1я и). Согласно упражнению 20.2-3, если все деревья в фибоначчиевой пирамиде являются неупорядоченными биномиальными деревьями, то Р (и) = !1яиг. Однако вырезания в процедуре Р!в НеА!' РескеАзе Кеу могут привести к нарушению свойств неупорядоченных биномиальных деревьев.
В этом разделе мы покажем, что в связи с тем, что мы вырезаем узел у родителя, Часть Ч. Сложные структуры данных 576 как только он теряет два дочерних узла, Р (и) равно О ()би). В частности, мы покажем, что Р (и) < [)оба и), где ф = (1+ чЛ) /2. Для каждого узла х в фибоначчиевой пирамиде определим вззе (х) как количество узлов в поддереве, корнем которого является х, включая сам узел х (заметим, что узел х не обязательно должен находиться в списке корней; это может быть любой узел фибоначчиевой пирамиды).
Покажем, что величина вые (х) экспоненциально зависит от Иедгее [х] (напомним, что поле Ыедгее [х) всегда содержит точную величину степени х). Лемма 20.1. Пусть х — произвольный узел фибоначчиевой пирамиды, и пусть уы уг,..., уь — дочерние узлы х в порядке их связывания с х начиная с более ранних и заканчивая более поздними. Тогда Недгее [у1] > О и Иедгее [у,) > 1 — 2 при 1 = 2, 3,..., Й. Доказательство. Очевидно, что Иедгее [у1) > О. Для 1 > 2 заметим, что когда у; связывается с х, все узлы у1, уг,...,у; 1 являются дочерними узлами х, так что в этот момент дедке [х] > 1 — 1.
Узел у; связывается с х только в том случае, когда Ыедгее [х) = Ыедгее [у;], так что в момент связывания Иедгее [у;] > 1 — 1. С этого момента узел у; мог потерять не более одного дочернего узла, поскольку пря потере двух дочерних узлов он должен быть вырезан у узла х. Отсюда следует, что Иедгее [у;] > 1 — 2. Сейчас мы подошли к той части анализа, которая поясняет название "фибоначчиевы пирамиды". Вспомним, что в разделе 3.2 lс-ое число Фибоначчи определяется при помощи следующего рекуррентного соотношения: при Й = О, при Й = 1, при й > 2.
Гь= 1 Бь ь + рь-г Приведенная далее лемма дает еще один способ для выражения Еь. Лемма 20.2. Для всех целых к > О Доказательство. Докажем лемму при помощи математической индукции по Е При В=О о 1+ ~ г1 = 1+ га = 1+ О = 1 = рг. Глава 20. Фибоначчиевы пирамиды 577 По индукции предполагаем, что гь+1 = 1 + 2 ', О Е;. Тогда ь — 1 ь Рь+з = ~'ь+ б:.н = Еь+ 1+,~ Й = 1+ ~~~ ~'с. с=О с=о Приведенная далее лемма и следствие из нее завершают анализ. Они используют доказанное в упражнении 3.2-7 неравенство .~азиз ~ 3ф ь где ф — золотое сечение, определенное в уравнении 13.22) как ф = (1+ ~/5)/2 = = 1.61803....
Лемма 20.3. Пусть х — произвольный узел фибоначчиевой пирамиды, а 1с = = Ыедгее [х] — ее степень. Тогда 8гее (х) > г ь+з > фь, где ф = (1 + ~/5) /2. Доказаспельсспво. Обозначим через 8ь минимально возможный размер узла степени )с в произвольной фибоначчиевой пирамиде. Случаи 8О = 1 и 81 = 2 тривиальны. Число 8ь не превышает величины 8сае (х) и, поскольку добавление дочерних Узлов к УзлУ не может Уменьшить его РазмеР, значение 8ь монотонно возРастает с возрастанием й. Рассмотрим некоторый узел х в произвольной фибоначчиевой пирамиде, такой что с1едгее [х] = сс и 8гее(х) = 8ь.
Так как 8ь < 8гхе(х), мы вычислЯем нижнюю гРаницУ 8гае (х) пУтем вычислениЯ нижней гРаницы 8ь. Как и в лемме 20Л, обозначим через уы уз, ., уь дочерние узлы " в порядке их связывания с г. При вычислении нижней границы 8ь учтем по единице для самого х и для его первого дочернего узла ус 1для которого 8гхе (ус ) > 1). Тогда 8ие(х) > 8ь > 2+ ~> 88ся,[ж1 > 2+ ~~> 8,— г, сыв где последний переход следует из леммы 20.1 1откуда с1едтее [у;[ > г — 2) и моно- ТОННОСТИ 8Ь (ОТКуда 88 Ы > 8с — 2). Покажем теперь по индукции по Й, что 8ь > Рь+з для всех неотрицательных целых й. База индукции при й = 0 и й = 1 доказывается тривиально.
Далее мы предполагаем, что й > 2 и что 8, > Е;+з при г = О, 1,..., сс — 1. Тогда ь ь ь 8а > 2+ ~) асс-В ~ 12+ ) Г; = 1+ ~ Гс = Р)с+О =з (последний переход сделан на основании леммы 20.2). Таким образом, мы пока- зали, что асхе (х) > 8ь > Рл+з > фь. 578 Часть Ч. Сложные структуры данных Следствие 20.4. Максимальная степень Р (и) произвольного узле в фибоначчи- евой пирамиде с п узлами равна О (18 и). Доказательство.
Пусть х — произвольный узел в фибоначчиевой пирамиде с и узлами, и пусть /с = с1еугее [х]. Согласно лемме 20.3, и > всзе (х) > ф". Логарифмируя по основанию ф, получаем lс < !обои (в действительности, так как )с — целое число, й < [1ойеп)). Таким образом, максимальная степень Р(и) произвольного узла равна 0 (18 и). Упражнения 20.4-1.
Профессор утверждает, что высота фибоначчиевой пирамиды из и узлов равна О (18 и). Покажите, что профессор ошибается и что для любого положительного и имеется последовательность операций, которая создает фибоначчиеву пирамиду, состоящую из одного дерева, которое представляет собой линейную цепочку узлов. 20.4-2. Предположим, что мы обобщили правило каскадного вырезания и что узел х вырезается у родительского узла, как только теряет Й-й дочерний узел, где й — некоторая константа (в правиле из раздела 20.3 использовано значение к = 2).
Для каких значений к справедливо соотношение Р(п) = 0(18п)? Задачи 20-1. Альтернативная реализация удаления Профессор предложил следующий вариант процедуры Р1В НВА1' 13еьете, утверждая, что он работает быстрее для случая удаления узла, не являющегося минимальным. РкОГ тзеьете(Н, х) 1 Ых=тьп[Н] 2 тпеп Р1В НеАР ЕхткАст Меч(Н) 3 ене у — р[х] 4 ЫуФн1ь 5 тпеп СЫТ(Н, х, у) б САЬсАгз1ыО С1п(Н, у) 7 Добавить список дочерних узлов х в список корней Н 8 Удалить х из списка корней Н а) Утверждение профессора о быстрой работе процедуры основано, в частности, на предположении, что строка 7 может быть выполнена за время 0 (1).
Какое обстоятельство упущено из виду? Глава 20. Фибоиаччиевы пирамиды 579 б) Оцените верхнюю границу фактического времени работы процедуры РКОЕ ОЕЕЕТЕ, когда х не является т(п [Н!. Ваша оценка должна быть выражена через Недгее [х] и количество с вызовов процедуры САзсАгих0 Сцт. в) Предположим, что мы вызываем Ркое Овеете(Н, х), и пусть Н'— полученная в результате фибоначчиева пирамида.
Считая, что х не является корнем, оцените потенциал Н', выразив его через сергее [х], с, г(Н) и т(Н). г) Выведите из полученных результатов оценку амортизированного времени работы процедуры РкОе Овеете и покажите, что оно асимптотически не лучше амортизированного времени работы процедуры Р!В НеАР Пееете, даже если х ф тт [Н]. 20-2. Дополнительные операции над фибоначчиевыми пирамидами Мы хотим реализовать поддержку двух операций над фибоначчиевыми пирамидами, при этом не изменяя амортизированное время работы прочих операций над фибоначчиевыми пирамидами.
а) Операция Р)в НВАЕ СнАхбе Кеу(Н,х,)с) изменяет ключ узла х, присваивая ему значение )з Приведите эффективную реализацию процедуры Р~в НеАР СНАхсе КВУ и проанализируйте амортизированное время работы вашей реализации для случаев, когда )г больше, меньше или равно Йеу [х]. б) Разработайте эффективную реализацию процедуры Р1В НВАР Рилче(Н, г), которая удаляет шш(г, и [Н]) узлов из Н. То, какие именно узлы удаляются, не должно приниматься во внимание. Проанализируйте амортизированное время работы вашей реализации. (Указание: вам может потребоваться изменение структуры данных и потенциальной функции.) Заключительные замечания Фибоначчиевы пирамиды были введены Фредманом (Ргейпап) и Таржаном (Таг1ап) (98]. В их статье описано также приложение фибоначчиевых пирамид к задачам о кратчайших путях из одной вершины, паросочетаниях с весами и о минимальном остовном дереве.
Впоследствии Дрисколл (Пг)зсо!1), Габон (ОаЬоа), Шрейрман (88Ьгаптпап) и Таржан [81] разработали так называемые "ослабленные пирамиды" (ге1ахед Ьеарз) в качестве альтернативы фибоначчиевым пирамидам. Имеется два варианта ослабленных пирамид. Один дает то же амортизированное время работы, 580 Часть Ч. Сложные структуры данных что и фибоначчиевы пирамиды, второй же позволяет выполнять операцию 0аскцлзп Кпу в наихудшем случае за (не амортнзированное) время О (1), а процедуры Ехтцлст Мпч и Рн птп в наихудшем случае за время О (15 и). Ослабленные пирамиды имеют также преимущество над фибоначчиевыми пирамидами в параллельных алгоритмах. Обратитесь к материалу главы 6, где рассмотрены другие структуры данных, которые подцерживают быстрое выполнение операции Рпсццлзн Кпу, когда последовательность значений, возвращаемых вызовами процедуры Ехтклст Мщ монотонно растет со временем, а данные представляют собой целые числа в определенном диапазоне.
ГЛАВА 21 Структуры данных для непересекающихся множеств В некоторых приложениях выполняется группировка и различных элементов в набор непересекающихся множеств. Две важные операции, которые должны выполняться с таким набором, — поиск множества, содержащего заданный элемент, и объединение двух множеств.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
