Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 123
Текст из файла (страница 123)
Заметим, что поскольку татй [р[х]] монотонно увеличивается со временем, то же происходит и с !ече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. Таким образом, либо фч (у) = фч ~ (у), либо фя (у) = фч ~ (у) + а (п).
Итак, увеличение потенциала вследствие операции Ьщк не превышает о (п), и амортизированная стоимость операции Ьпчк равна О (1) + а (и) = О (о (и)). ° Лемма 21.12. Амортизированная стоимость каждой операции Рпч0 Знт равна О (о (п)). Доказашельсшво. Предположим, что 9-й операцией является Р1НП Япт и что путь поиска содержит я узлов. Фактическая стоимость операции Р1ьлэ Бит составляет О (а). Покажем, что отсутствуют узлы, потенциал которых возрастает вследствие операции Рпчв Бит, и что как минимум у шах (О, в — (а(п) + 2)) узлов на пути поиска потенциал уменьшается по меньшей мере на 1. Чтобы увидеть отсутствие узлов с возрастающим потенциалом, обратимся к лемме 21.9 для узлов, не являющихся корнем.
Если же узел х — корень, то его потенциал равен а (и) гапй [х) и остается неизменным. бОО Часть Ч. Сложные структуры данных Теперь мы покажем, что как минимум у шазс(О,в — (сх(и)+ 2)) узлов потенциал уменьшается по меньшей мере на 1. Пусть х — узел на пути поиска, такой что гапИ [х] > О, и за х на пути поиска следует другой узел у, не являющийся корнем, где непосредственно перед выполнением операции Рпсп Яет !ече! (у) = !ече1 (х) (узел у не обязательно следует непосредственно за х). Зтим ограничениям на х удовлетворяют все узлы на пути поиска, кроме сс (и) + 2 узлов. Приведенным условиям не удовлетворяет первый узел на пути поиска (если ов имеет нулевой ранг), последний узел пути (т.е.
корень), а также сс (п) узлов се, которые для данного И, где !с = 0,1,..., сс (п) — 1, являются последними узлами на пути, удовлетворяющими условию !ече! (и) = И. Зафиксировав такой узел х, покажем, что потенциал х уменьшается как минимум на 1. Пусть И = 1ече1 (х) = 1ече1 (у). Непосредственно перед сжатием пути в процедуре Рпс!з Янт мы имеем: гапИ [р [х]] > Аьб " * (тап!с [х]) тапИ [р[у]] > Аь (гапИ [у]) гапИ [у] > тапИ [р [х]] по определению Ыег (х), по определению 1ече1 (х), согласно следствию 21.5, поскольку у следует за х. Объединяя приведенные неравенства и обозначая через г значение !сег (х) перед сжатием пути, получаем: тапИ [р[у]] > Аь(тапИ [у]) > Аь(татй [р[х]]) > > Аь (А!ь' '~*~! (гатй [х])) = А~,'~ ! (тапИ [х]), где второе неравенство следует из того, что Аь Ц) — строго возрастающая функция.
Поскольку после сжатия пути и х, и у имеют один и тот же родительский узел, мы знаем, что после сжатия пути татй [р[х]] = тапИ [у[у]] и что сжатие пути ие уменьшает тапИ [р[у]]. Поскольку татй [х] не изменяется, после сжатия пути тапИ [р[х]] > Аьб+ (гаиИ [х]). Таким образом, сжатие пути приводит к тому, что либо увеличивается !1ег (х) (как минимум до с + 1), либо увеличивается 1ече1 (х) (как минимум до гапИ [х] + 1).
В любом случае, в соответствии с леммой 21.9, фе (х) < фс г (х) — 1. Следовательно, потенциал х уменьшается как минимум на 1. Амортизированная стоимость операции Р!нп Япт равна фактической стоимости плюс изменение потенциала. Фактическая стоимость равна О (в), и мы показали, что общий потенциал уменьшается как минимум на шах (О, в — (сх (и) + 2)). Амортизированная стоимость, таким образом, не превышает О (в) — (в — (сс(и) + + 2)) = 0 (в) — в + 0 (сх (и)) = 0 (сх (и)), так как мы можем масштабировать потенциал таким образом, чтобы можно было пренебречь константой, скрытой в 0(в).
Глава 21. Структуры данных для непересекающихся множеств 601 Теперь, после того как мы доказали все приведенные выше леммы, мы можем перейти к следующей теореме. Теорема 21.13. Последовательность из т операций МлкЕ БЕт, 1)ион и ймп Бет, и из которых — операции Млкн Бит, может быть выполнена над лесом непересекающихся множеств с использованием объединения по рангу и сжатия пути за время О (тгг (и)) в наихудшем случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
