Алгоритмы - построение и анализ (1021735), страница 121
Текст из файла (страница 121)
Сложные структуры данных 596 В оставшейся части этого раздела мы полагаем, что исходная последовательность из т' операций МАке Бет, Ыьлом и Р|мп Бет преобразована в последовательность из т операций МАке Яет, Ьпчк и Е!хп Бет. Теперь мы докажем, что время выполнения полученной последовательности равно О (тпа (и)) и обратимся к лемме 21.7 для доказательства времени работы О (тп'о (и)) исходной последовательности из т' операций. Потенциальная функция Используемая нами потенциальная функция присваивает потенциал фч(х) каждому узлу х в лесу непересекающихся множеств после выполнения д операций.
Для получения потенциала всего леса мы суммируем потенциалы его узлов: Фч — — 2; фч (х), где Фч — потенциал всего леса после выполнениЯ д опеРаций. До выполнения первой операции лес пуст, и мы полагаем, что Фс = О. Потенциал Фч никогда не может стать отрицательным. Значение фч (х) зависит от того, является ли х корнем дерева после д-й операции. Если это так или если тапй [х] = О, фд (х) = о (и) тапй [х].
Теперь предположим, что после д-й операции х не является корнем и что тапа [х] > 1. Нам надо определить две вспомогательные функции от х перед тем, как мы определим фч (х). Сначала мы определим 1ече1(х) = шах(1с: татй [р [х]] > Аь (татй [х])), т.е. 1ече1 (х) — наибольший уровень й, для которого Аы примененное к рангу х, не превышает ранг родителя х. Мы утверждаем, что О < !ече1(х) < а(п). (21.1) Это можно подтвердить следующим образом. Мы имеем тапИ [р [х]] > та|й [х] + 1 = Ао (татй [х]), где неравенство следует из леммы 21А, а равенство — по определению Ао(~). Отсюда вытекает, что 1ече1 (х) > О.
Тогда А („1 (тапй [х]) > А,„(„1 (1) > и > тапй [р [х]], где первое неравенство следует из строго возрастающего характера функции Аь (з), второе — из определения а (и), а третье — из леммы 21.6. Из полученного соотношения вытекает, что 1ече! (х) < о (и). Заметим, что поскольку татй [р[х]] монотонно увеличивается со временем, то же происходит и с !ече1 (х). Вторую вспомогательную функцию определим следующим образом: Нег (х) = шах (г: тапй [р [х]] > А~,'~ы< (тап1с [х]) ~, Глава 21. Структуры данных для непересекающихся множеств те. 1тег(х) — наибольшее число раз итеративного применения функции Ам,ы1 1 к исходному рангу х, до того как мы получим значение, превышающее ранг родителя х. Мы утверждаем, что 1 < Нег(х) < тапй[х).
В этом можно убедиться следующим образом. Мы имеем гатй [р [х)1 > Аечы1з1(татй [х]) = А~ „ьц,1 (гапй [х]), где неравенство следует из определения 1ече1 (х), а равенство — из определения функциональной итерации. Из приведенного соотношения вытекает, что Ыег (х) > > 1, и мы получаем в соответствии с определениями Аь (у) и 1ече1 (х) А11, ",Д~ 1(гатй [х)) = Амчм1 )+1(гапй [х]) > гапй [р[х]], откуда 1сег (х) < гапй [х).
Заметим, что поскольку гапй [р[х)] монотонно увели- чивается со временем, для того чтобы значение 11ег (х) уменьшалось, величина 1ече1(х) должна увеличиваться. Если же 1ече1(х) остается неизменной, то значе- ние Иег (х) должно либо увеличиваться, либо вообще не изменяться. Имея описанные вспомогательные функции, мы можем записать потенциал узла х после а операций: (21.2) гз (п) ° тапй [х] если х корень или тапИ [х) = О, (а (и) — 1ече1 (х)) х если х не корень и гапй [х] > 1. х тапй [х] — Ыег (х) В следующих двух леммах представлены полезные свойства потенциала узла.
Лемма 21.8. Для всех а операций и произвольного узла х фд(х) < (а(п) — 0) тапй [х] — 1 = сд(п) . тапИ [х] — 1 < о(п) тапй [х). ° 0 < ф»(х) < сг(п) ° гатй [х]. Доказательство. Если х — корень или гапй [х] = О, то по определению ф» (х) = = сд(п) тапй [х]. Предположим теперь, что х — не корень и что тапИ. [х] > > 1.
Нижнюю границу ф» (х) можно получить, максимизируя 1ече1 (х) и йег (х). Согласно (21.1), 1ече1 (х) < а (и) — 1, а в соответствии с (21.2) — 11ег (х) < тапй [х]. Таким образом, фд (х) > (гз (и) — (сд (и) — 1)) гапй [х) — тапй [х] = тапй [х] — гапй [х] = О. Аналогично получаем верхнюю границу ф» (х), минимизируя 1ечс1 (х) и 1сег (х). Согласно (21.1), 1ече1 (х) > О, а в соответствии с (21.2) — Ыег(х) > 1. Таким образом, 598 Часть Ч. Сложные структуры данных Изменения потенциала и амортизированная стоимость операций Теперь мы готовы к рассмотрению вопроса о влиянии операций над непересекающимися множествами на потенциалы узлов.
Зная, как изменяется потенциал при той или иной операции, мы можем определить амортизированную стоимость каждой операции. Лемма 21.9. Пусть х — узел, не являющийся корнем, и предположим, что в-я операция — либо Ь!МК, либо РаЬЛЭ БЕт. Тогда после выполнения д-й операция фч (х) < ф ь (х). Более того, если тапК [х] > 1 и из-за выполнения д-й операция происходит изменение либо !ече1 (х), либо Нег (х), то фч (х) < фч з (х) — 1. То есть потенциал х не может возрастать, и если он имеет положительное значение, а либо !ече1 (х), либо Нег (х) изменяются, то потенциал х уменьшается как минимум на 1.
Доказаихельство. Поскольку х не является корнем, д-я операция не изменяет тапа [х], и так как и не изменяется после первых гь операций МАКЕ БЕТ, а (п) остается неизменной величиной. Следовательно, эти компоненты формулы потенциальной функции при выполнении 9-й операции не изменяются.
Если гапй [х] = = О, то фч (х) = фч ь (х) = О. Теперь предположим, что гапЕ [х] > 1. Вспомним, что значение функции !ече1(х) монотонно растет со временем. Если д-я операция оставляет 1ече1 (х) неизменной, то функция нег (х) либо возрастает, либо остается неизменной. Если и 1ече1 (х), и нег (х) не изменяются, то фч (х) = фч з (х). Если же 1ече1 (х) не изменяется, а нег (х) возрастает, то Нег(х) увеличивается как минимум на 1, так что фв (х) < фч ь (х) — 1. И наконец, если д-я операция увеличивает 1ече1 (х), то это увеличение составляет как минимум 1, так что значение члена (гх (и) — 1ече1 (х)) . гап1г [х] уменьшается как минимум на величину гаЫ [х].
Так как значение 1ече1 (х) возрастает, значение пег (х) может уменьшаться, но в соответствии с (21.2), это уменьшение не может превышать гапй [х] — 1. Таким образом, увеличение потенциала, вызванное изменением функции нег (х), меньше, чем уменьшение потенциала из-за изменения функции!ече! (х), так что мы можем заключить, что фв (х) < фв ь (х) — 1. ° Наши последние три леммы показывают, что амортизированная стоимость каждой из операций МАке Бет, Ьпчк и Рпчгз Бет составляет О (гх(п)). Вспомним, что, согласно (17.2), амортизированная стоимость каждой операции равна ее фактической стоимости плюс увеличение потенциала, вызванное ее выполнением.
Лемма 21.10. Амортизированная стоимость каждой операции МАке Бег равна О (1). Доказавхельство. Предположим, что д-я операция — МАке Бет. Эта операция создает узел х с рангом О, так что фч (х) = О. Никакие иные ранги и потенциалы Глава 21. Структуры данных для непересекающихся множеств 599 не изменяются, так что Фч —— Фч з.
То, что фактическая стоимость операции МАкв Бит равна О (1), завершает доказательство. Лемма 21.11. Амортизированная стоимость каждой операции Ьпчк равна О (а (и)). Доказаюнельсшво. Предположим, что д-я операция — Ь1мк(х, у). Фактическая стоимость операции Ьпчк равна О (1). Без потери общности предположим, что Ьпчк делает у родительским узлом х.
Для определения изменения потенциала из-за выполнения операции Ьпчк заметим, что множество узлов, чьи потенциалы могут измениться, ограничено узлами х, у и дочерними узлами у непосредственно перед операцией. Мы покажем, что единственным узлом, потенциал которого может увеличиться в результате выполнения операции Ьпчк, — это у, и это увеличение не превышает а (и). ° Согласно лемме 21.9, потенциал любого узла, являющегося дочерним узлом у перед выполнением операции 1лмк, не может увеличиться в результате выполнения этой операции. ° По определению фд (х) мы видим, что поскольку х перед д-й операцией был корнем, фя з (х) = а (и) тапа [х].
Если гапй [х) = О, то фч (х) = фя з (х) = = О. В противном случае, в соответствии с неравенствами (21.1) и (21.2), ° фч (х) = (а (и) — 1ече1 (х)) тапа [х) — Пег (х) < и (и) гапх [х). Поскольку фч з (х) = а (и) гапх [х), мы видим, что потенциал х уменьшается. ° Так как у непосредственно перед выполнением операции Ьпчк был корнем, фя з (у) = а (и) гапй [у]. Операция Ьпчк оставляет у корнем и либо оставляет ранг у неизменным, либо увеличивает его на 1.
Таким образом, либо фч (у) = фч ~ (у), либо фя (у) = фч ~ (у) + а (п). Итак, увеличение потенциала вследствие операции Ьщк не превышает о (п), и амортизированная стоимость операции Ьпчк равна О (1) + а (и) = О (о (и)). ° Лемма 21.12. Амортизированная стоимость каждой операции Рпч0 Бит равна О (о (п)). Доказашельсшво. Предположим, что 9-й операцией является Р1НП Янт и что путь поиска содержит я узлов. Фактическая стоимость операции Р1ьлэ Бит составляет О (а). Покажем, что отсутствуют узлы, потенциал которых возрастает вследствие операции Рпчв Бит, и что как минимум у шах (О, в — (а(п) + 2)) узлов на пути поиска потенциал уменьшается по меньшей мере на 1.
Чтобы увидеть отсутствие узлов с возрастающим потенциалом, обратимся к лемме 21.9 для узлов, не являющихся корнем. Если же узел х — корень, то его потенциал равен а (и) гапй [х) и остается неизменным. бОО Часть Ч. Сложные структуры данных Теперь мы покажем, что как минимум у шазс(О,в — (сх(и)+ 2)) узлов потенциал уменьшается по меньшей мере на 1. Пусть х — узел на пути поиска, такой что гапИ [х] > О, и за х на пути поиска следует другой узел у, не являющийся корнем, где непосредственно перед выполнением операции Рпсп Яет !ече! (у) = !ече1 (х) (узел у не обязательно следует непосредственно за х).
Зтим ограничениям на х удовлетворяют все узлы на пути поиска, кроме сс (и) + 2 узлов. Приведенным условиям не удовлетворяет первый узел на пути поиска (если ов имеет нулевой ранг), последний узел пути (т.е. корень), а также сс (п) узлов се, которые для данного И, где !с = 0,1,..., сс (п) — 1, являются последними узлами на пути, удовлетворяющими условию !ече! (и) = И. Зафиксировав такой узел х, покажем, что потенциал х уменьшается как минимум на 1. Пусть И = 1ече1 (х) = 1ече1 (у).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
