Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 122
Текст из файла (страница 122)
Каждый вызов Р1мп БЕТ возвращает в строке 3 р [х). Если х— корень, то строка 2 не выполняется и возвращается значение р [х] = х, и на этом рекурсия завершается. В противном случае выполнение строки 2 приводит к рекурсивному вызову с параметром р [х], который возвращает указатель на корень. В той же строке 2 происходит обновление узла х, после которого он указывает непосредственно на найденный корень, и этот указатель возвращается вызывающей процедуре в строке 3. Часть Ч.
Сложные структуры данных 592 Влияние эвристик на время работы Будучи примененными раздельно, обьединение по рангу и сжатие пути приводят к повышению эффективности операций над лесом непересекающихся множеств. Еще больший выигрыш дает совместное применение этих эвристик.
Объединение по рангу само по себе дает время работы О(т1яп) (см. упражнение 21.4-4), причем эта оценка не может быть улучшена (см. упражнение 21.3-3). Хотя мы не будем доказывать это здесь, если имеется п операций МАке Бет (а следовательно, не более п — 1 операций Пм!ом) и г' операций Ричп Бет, то сжатие пути само по себе приводит ко времени работы в наихудшем случае О (и+ ! (!обз+О„п)). При совместном использовании обеих эвристик время работы в наихудшем случае составляет О (ти о (п)), где сх (и) — очень медленно растущая функция, которую мы определим в разделе 21.4. Для любого мыслимого приложения с использованием непересекающихся множеств а (и) < 4, так что можно рассматривать время работы во всех практических ситуациях как линейно зависящее от т.
В разделе 2!.4 мы докажем эту верхнюю границу. Упражнения 2!.3-1. Выполните упражнение 21.2-2 для леса непересекающихся множеств с использованием объединения по рангу и сжатия пути. 21.3-2. Разработайте нерекурсивную версию процедуры Р!мо БЕТ со сжатием пути. 21.3-3. Приведите последовательность из т операций МАКЕ БЕТ„! 1МОМ и Р!НП Бет, и из которых — операции МАке Бет, время выполнения которой составляет Й (т 1я и) при использовании только объединения по рангу.
* 21.3-4. Покажите, что время выполнения произвольной последовательности т операций МАке Бет, Р!мо Бет и аничк, в которой все операции 1!нк выполняются до первой операции Р!мо Бет, равно О (т), если используются как объединение по рангу, так и сжатие пути. Что будет, если воспользоваться только сжатием пути? *21.4 Анализ объединения по рангу со сжатием пути Как отмечалось в разделе 21.3, время работы пз операций над непересекающимися множествами из п элементов при использовании объединения по рангу и сжатия пути равно О (пзо(п)).
В данном разделе мы рассмотрим функцию Глава 21. Структуры данных для непересекающихся множеств 593 а (и) и выясним, насколько медленно она растет. Затем мы докажем приведенное выше время работы с использованием метода потенциала из амортизационного анализа. Очень быстро и очень медленно растущая функция Определим функцию Ая (3) для целых к > О и !' > 1 как з +1 при!с=О, А~~~ ! (у) при к > 1, где выражение А~~~ (т) использует функционально-итеративные обозначения из О +1) раздела 3.2. В частности, А, Ц) = 3 и А~,' (~) = Аь 1 (А~' ! (3)) для г > 1.
Параметр !с будем называть уровнем (!ече!) функции А. Функция Аь (3) — строго возрастающая по 3' и !с. Для того чтобы увидеть, насколько быстро растет данная функция, начнем с записи функций А1 (3) и Аз О) в явном виде. Лемма 21.2. Для произвольного целого 3 > 1 А1 Ц) = 23 + 1. Доказатяельстао. Воспользуемся индукцией по т', чтобы показать, что Ао' (1) = = 3 + г. Начнем с базы индУкции: Ао (з') = 3 = У'+ О. Далее пРедположим, что 1о! Аоб ! ц) = 3+(г — 1).
Тогда Аоо (3) = Ас (Аоб ! ц)) = (3'+ (г — 1))+1 = 7+!. И наконец, А1 (у) = Ао (у) = у'+ (т'+ 1) = 23 + 1. Лемма 21.3. Для произвольного целого 3' > 1 Аз (3) = 23+' (3 + 1) — 1. Доказаюиазьслыо. Воспользуемся индукцией по г, чтобы показать, что А,' Ц) = = 2' (у + 1) — 1. Начнем с базы индукции: А~~ (3) = 3 = 2о (з'+ 1) — 1.
Далее предположим, что А (3) = 2' ~ (~ + 1) — 1. Тогда А~'! (т) = А1 (А1~' ! (3)) = = А1 (2' 1(3'+ 1) — 1) = = 2 (2' ~ (у + 1) — 1) + 1 = = 2' и + 1) — 2 + 1 = 2' Ц + 1) — 1. И наконец, Аз Ц) = А~1~~ ! (з) = 23+1 (3 + 1) — 1. 594 Часть Ч. Сложные структуры данныи Теперь посмотрим, насколько быстро растет функция Аь (з), просто вычисля Аь (1) для уровней к от 0 до 4. Из определения Ао (1) и рассмотренных выше лемм мы имеем Ао(1) = 1+ 1 = 2, А1(1) = 2 1+ 1 = 3 и Аз(1) = 2+' (1+ 1) — 1 = 7.
Продолжая вычисления, получаем: Аз (1) = Аз~~ (1) = Аг(А (1)) = Аз(7) = 2в. 8 — 1 = 2 — 1 = 2047 А4 (1) = Аз (1) = Аз (Аз (1)) = Аз (2047) = Аз (2047) » » 4 (2047) 2зо"в 2048 1 > 2юев (24) ~ 1быз >> 10во что представляет собой оценочное количество атомов в наблюдаемой вселенной. Определим обратную к Аь (7') функцию для п ) )0 следуклцим образом: а(п) = т1п(й: Аь(1) > и).
Другими словами, а (и) — наименьший уровень 1е, для которого Ав (1) не меньше п. Исходя из найденных выше значений функции, 0 приО<п<2, 1 прип=З, 2 при4<п<7, 3 при 8 < и < 2047, 4 при 2048 < и < А4 (1). а(п) = Только для невероятно больших значений и (больших А4 (1)) значение функции ее (и) становится больше 4, так что для практического применения ее (и) < 4. Свойства рангов Лемма 21.4. Для всех узлов х выполняется соотношение тап*к[х] < тапИ [р[х]], причем равенство достигается только при х = р [х]. Значение тапа [х] изначально равно 0 и, пока х ф р [х], увеличивается со временем. По достижении равенства х = р [х] значение тапй [х] больше не изменяется.
Значение тапа [р[х]] монотонно возрастает со временем. В оставшейся части раздела мы докажем, что при использовании объединения по рангам и сжатия пути граница времени работы операций иад непересекающимися множествами равна О (та а (и)). Для этого нам потребуются некоторые простые свойства рангов. Глава 2Ь Структуры данных для непересекающихся множеств 595 Доказашельсшко. Доказательство выполняется простой индукцией по количеству операций, с использованием реализаций процедур МАкв Бет, Ун!он и Р!но Бет в разделе 21.3. Подробности доказательства оставлены в качестве упражнения 21.4-1.
Следствие 21.5. При перемещении вдоль пути от произвольного узла к корню ранг строго возрастает. Лемма 21.6. Ранг любого узла не превышает и — 1. Доказяшельсшво. Начальный ранг каждого узла — О, и он возрастает только при выполнении операции Ь!нк. Поскольку выполняется не более и — 1 операции Умом, операций Ь!нк также выполняется не более чем и — 1. Поскольку каждая операция Ь|нк либо оставляет все ранги неизменными, либо увеличивает один ранг на 1, ни один ранг не может превышать и — 1. Лемма 21.6 дает слабую оценку границы рангов. В действительности ранг любого узла не превосходит 11бп! (см.
упражнение 21.4-2). Однако для наших целей достаточно границы, определяемой леммой 2!.6. Доказательство границы времени работы Для доказательства границы О (та (и)) мы воспользуемся методом потенциала из амортизационного анализа (см. раздел 17.3). При выполнении амортизационного анализа удобно считать, что мы выполняем операцию Ь|нк, а не Ун!Он. Т.е., поскольку параметрами процедуры Ь!нк являются указатели на два корня, мы считаем, что соответствующие операции Р!нп Бег выполняются отдельно. Приведенная ниже лемма показывает, что даже если учесть дополнительные операции Р!нп Бет, инициированные вызовами Ун)он, асимптотическое время работы останется неизменным. Лемма 21.7. Предположим, что мы преобразуем последовательность У из тп' операций Млке Блт, Ун!он и Реп Бег в последовательность из т операций МАкп Бпт, Ьпчк и Рп и Бпт путем преобразования каждой операции Ун!он в две операции Р[мэ Яет, за которыми следует операция Ьпчк Тогда, если последовательность Я выполняется за время О (пза (и)), то последовательность Я' выполняется за время О (т'а (и)).
Доказашельсшао. Поскольку каждая операция Ун!Он в последовательности о' преобразуется в три операции в Я, выполняется соотношение т' < гп < Зт'. Так как тп = О (тп'), из границы времени работы О(та (п)) преобразованной последовательности Я следует граница О(т'а(п)) времени работы исходной последовательности У. Часть Ч. Сложные структуры данных 596 В оставшейся части этого раздела мы полагаем, что исходная последовательность из т' операций МАке Бет, Ыьлом и Р|мп Бет преобразована в последовательность из т операций МАке Яет, Ьпчк и Е!хп Бет. Теперь мы докажем, что время выполнения полученной последовательности равно О (тпа (и)) и обратимся к лемме 21.7 для доказательства времени работы О (тп'о (и)) исходной последовательности из т' операций.
Потенциальная функция Используемая нами потенциальная функция присваивает потенциал фч(х) каждому узлу х в лесу непересекающихся множеств после выполнения д операций. Для получения потенциала всего леса мы суммируем потенциалы его узлов: Фч — — 2; фч (х), где Фч — потенциал всего леса после выполнениЯ д опеРаций. До выполнения первой операции лес пуст, и мы полагаем, что Фс = О. Потенциал Фч никогда не может стать отрицательным. Значение фч (х) зависит от того, является ли х корнем дерева после д-й операции. Если это так или если тапй [х] = О, фд (х) = о (и) тапй [х]. Теперь предположим, что после д-й операции х не является корнем и что тапа [х] > 1.
Нам надо определить две вспомогательные функции от х перед тем, как мы определим фч (х). Сначала мы определим 1ече1(х) = шах(1с: татй [р [х]] > Аь (татй [х])), т.е. 1ече1 (х) — наибольший уровень й, для которого Аы примененное к рангу х, не превышает ранг родителя х. Мы утверждаем, что О < !ече1(х) < а(п). (21.1) Это можно подтвердить следующим образом. Мы имеем тапИ [р [х]] > та|й [х] + 1 = Ао (татй [х]), где неравенство следует из леммы 21А, а равенство — по определению Ао(~). Отсюда вытекает, что 1ече1 (х) > О. Тогда А („1 (тапй [х]) > А,„(„1 (1) > и > тапй [р [х]], где первое неравенство следует из строго возрастающего характера функции Аь (з), второе — из определения а (и), а третье — из леммы 21.6. Из полученного соотношения вытекает, что 1ече! (х) < о (и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
