Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 134
Текст из файла (страница 134)
топ!с > у. тип)с 2 ур=х 3 е!ае х.р = у 4 И х. та~й == у, таей 5 у.тий = у.тюй+! Процедура г 1м1з-Бет со сжатием пути достаточно проста. р!МП-БЕТ(х) 1 Нхфх.р 2 х.р = Р1МП-БЕт1х.р) 3 ге!цгп х,р Процедура р1мп-Бет является двухвреходной: при первом проходе она ищет путь к корню дерева, а при втором проходе в обратном направлении по найденному пути происходит обновление узлов, которые теперь указывают непосредственно на корень дерева. Каждый вызов г1МП-БЕт(х) возвращает х.р в строке 3. Если х — корень, то строка 2 не выполняется и возвращается значение х.
р, равное х, и на этом рекурсия завершается. В противном случае выполнение строки 2 приводит к рекурсивному вызову с параметром х. р, который возвращает указатель на корень. В той же строке 2 происходит обновление узла х, после которого он указывает непосредственно на найденный корень, и этот указатель возвращается вызывающей процедуре в строке 3. Влияние эвристик иа время работы Будучи примененными раздельно, объединение по рангу и сжатие пути приводят к повышению эффективности операций над лесом непересекающихся множеств. Еще больший выигрыш дает совместное применение этих эвристик.
Объединение по рангу само по себе дает время работы 0(ел !я и) (см. упр, 2!.4.4), причем эта оценка не может быть улучшена (см. упр. 21.3.3). Хотя мы не будем доказывать это здесь„если имеется и операций МАке-Бет (а следовательно, не более и — 1 операций 1)м1ом) и 7' операций р1мп-Бег, то сжатие пути само по себе приводит ко времени работы в наихудшем случае 9(п + 7" (! + !окз+77а и)). При совместном использовании обеих эвристик время работы в наихудшем случае составляет 0(т се(п)), где а(п) — очень медленно растущая функция, которую мы определим в разделе 21.4.
Для любого мыслимого приложения с использованием непересекающихся множеств ск(п) < 4, так что можно рассматривать время работы во всех практических ситуациях как линейно зависящее от тп !хотя„строго говоря, оно сверхлинейиое). В разделе 21.4 мы докажем эту верхнюю границу. бОВ Часть К Саансные сяруктуры данные Упражнения 21.3.1 Выполните упр.
21.2.2 для леса непересекаюшихся множеств с использованием объединения по рангу и сжатия пути. 21.3.2 Напишите нерекурсивную версию процедуры Р1МП-Яцт со сжатием пути. 21.3.3 Приведите последовательность из т операций Мякин-блт, Пмпзм и Р~мп- Зцт, и из которых — операции Млкл-бдт, время выполнения которой составляет Й(т 1я и) при использовании только объединения по рангу. 21.3.4 Предположим, что мы хотим добавить операцию Рк1мт-акт(х), которая для заданного узла х выводит все члены множества х в произвольном порядке.
Покажите, как можно добавить к каждому узлу леса непересекаюшихся множеств по одному атрибуту, так чтобы время работы процедуры Рц1мт-Бцт(х) линейно зависело от количества членов множества х и при этом асимптотические времена работы других операций остались неизменнымн. Считайте, что каждый член множества выводится за время 0(1). 21.3.3 * Покажите, что время выполнения произвольной последовательности т операций Млкц-Здт, Р[мп-Яцт и Ымк, в которой все операции Ымк выполняются до первой операции Р1мп-блт, равно О(т), если используются как объединение по рангу, так и сжатие пути.
Что будет, если воспользоваться толью сжатием пути? * 21,4. Анализ объединения по рангу со сжатием пути Как отмечалось в разделе 21.3, время работы т операций над непересекающимися множествами из и элементов при использовании обьединения по рангу и сжатия пути равно 0(т сь(п)). В данном разделе мы рассмотрим функцию се и выясним, насюлью медленно она растет. Затем мы докажем приведенное выше время работы с использованием метода потенциала из амортизационного анализа. Очень быстро растущая функция и очень медленно растущая функция, обратная к ней Определим для целых к > О и 3 ) 1 функцию Аь(3) как 3 + 1, если к = О, А~~~~ (3), если к ) 1, Гяава УУ.
Структуры даннык дяя неяересекаюнрссся множеств где выражение Аьй (у) использует функционально-итеративные обозначения из В+О раздела 3.2. В частности, Ая,(у) = у, а А~,' у(у) = Аь у(А~,', ~(1)) для 1 > 1. Параметр Ус будем называть уровнем функции А. Функция Ая(у) — строго возрастающая по т' и Ус. Для того чтобы увидеть, насколько быстро растет данная функция, начнем с записи функций Ау(у) и Аз(у) в явном виде.
Лемма 21.2 Для любого целого у > 1 мы имеем Ау (у) = 2у + 1. Доказаасельсавво. Воспользуемся индукцией по г, чтобы показать, что Аоб(у) = у+1. Для базы индукции мы имеем Ас (у) = у = у+О. Для выполнения шага ин(оу дукции предположим, что Аоб (у) = у+(1 — 1). Тогда Ао' (у) = Ас(Ас' (у)) = (у+ (1 — 1)) + 1 = у+1. Наконец заметим, что Ау(у) = А<~ (у) = у + (у + 1) = гу+ 1. Ламма 21.3 для любого целого у > 1 мы имеем Аз(у) = 21+У(у + 1) — 1. Доказаааельсасво.
Воспользуемся индукцией по г, чтобы показать, что А)'~(у) = 2'(у + 1) — 1. Для базы индукции мы имеем А, (у) = у = 2о(у + 1) — 1. Для выполнения шага индукции предположим, что А, (у) = 2' '(1+ 1) — 1. Тогда Ау~(у) = Ау(Ау~ ~(у)) = Ау(2' у(2+1)-1) = 2 (2' у(1+1) — 1)+1 = 2'(у+1)— 2+1 = 2'(2+1) — 1. Наконец заметим, что Аз(у) = А,~~ (у) = 21+'Ц+1) — 1. ° Теперь посмотрим, насколько быстро растет функция Аь(у), просто вычисляя Аь(1) для уровней Ус = О, 1,2,3,4. Из определения Ао(к) и рассмотренных выше лемм мы имеем Ао(1) = 1 + 1 = 2, А1(1) = 2 1 + 1 = 3 и Аз(1) = 2У+У (1+ 1) — 1 = 7. Кроме того, Аз(1) = Аз (1) = Аз (Аз (1) ) = Аз(7) 28 й 1 = 2ы — 1 = 2047 Часть К Саанснте струтнурт данньи 510 А4(1) = Аз (1) = -4з(Аз(1)) = Аз(2047) = А,"""(2047) » Аг(2047) 2го48 2048 — 1 22048 (24)512 = 185'г » 1088 что представляет собой оценочное количество атомов в наблюдаемой Вселенной.
(СИМВОЛ а»" ОЗНаЧаЕт ОТНОШЕНИЕ аП1раэдО бОЛЬШЕ, ЧЕМ".) Определим обратную к Аь(п) функцию для п > 0 следуюшим образом: а(п) = пйп ()с: Аь(1) > п) Другими словами, а(п) — наименьший уровень )с, для которого Аь(1) не мень- ше и. Исходя из найденных выше значений Аь(1) мы видим, что 0 дляО<п<2, 1 дляп=3, 2 для4<п<7, 3 для8<п<2047, 4 для 2048 < п < А4(1) а(п) = Свойства рангов В оставшейся части этого раздела мы докажем, что при использовании объединения по рангам и сжатия пути граница времени работы операций над непересекаюшимися множествами равна 0(тп а(п)).
Для этого нам потребуются некоторые простые свойства рангов. Л 27.4 Для всех узлов х мы имеем х. тап14 < х.р.тап1с, причем при х ф х.р выполняется строгое неравенство. Значение х. таиМ изначально равно 0 и со временем Только для невероятно больших, "астрономических" значений п (ббльших А4(1)) значение функции а(п) превышает 4, так что для всех практических применений а(п) < 4. ГЛава 21. Структуры данных для ненересеканняшся множеств бЛ увеличивается, пока не будет достигнуто х ф х.р; после этого величина х. тои!с не изменяется.
Значение х, р, сои!с монотонно растет со временем. Доказательстевь Доказательство выполняется простой индукцией по количеству операций с использованием реализаций процедур МАке-бет, Ох!ох и Р1х1з-Яет в разделе 21.3. Подробности доказательства оставлены в качестве упр. 21.4.! . Следствие 21.5 При перемещении вдоль простого пути от произвольного узла к корню рант стро- го возрастает. Лемма 21.б Ранг любого узла не превышает и — 1. Доказательстео. Начальный ранг каждого узла — О, и он возрастает только при выполнении операции Ь1ХК. Поскольку выполняется не более и — 1 операции Ых1ох, операций Ыхк также выполняется не более чем и — 1. Поскольку каждая операция Ыхк либо оставляет все ранги неизменными, либо увеличивает ранг некоторого узла на 1, ни один ранг не может превышать п — 1.
Лемма 21.б дает слабую оценку границы рангов. В действительности ранг любого узла не превосходит (!йп)' (см. упр. 21.4.2). Однако для наших целей достаточно границы, определяемой леммой 21.6. Доказательство границы времени работы Для доказательства границы 0(тсе(и)) мы воспользуемся методом потенциала из амортизационного анализа (см. раздел 17.3). В ходе амортизационного анализа удобно считать, что мы выполняем операцию Ь1хк, а не Ых1ох. Иначе говоря, поскольку параметрами процедуры ЫХК являются указатели на два мэрия, мы считаем, что соответствующие операции Р1х1з-Бет выполняются отдельно.
Приведенная далее лемма показывает, что, даже если учесть дополнительные операции Р1хп-бет, инициированные вызовами Ых1ох, асимптотическое время работы останется неизменным. Л 217 Предположим, что мы преобразуем последовательность У из т' операций МАке-Бет, Ых!ох н Р!х1з-Бет в последовательность 5 из т операций МАкеБет, Ь1хк и Р1хп-Вет путем преобразования каждой операции Ых1ох в две операции Р1хп-бет, за которыми следует операция Ыхк. Тогда, если последовательность Я выполняется за время О(тек(п)), то последовательность У выполняется за время 0(т' св(п)). Доказательстео. Поскольку каждая операция Пх1ох в последовательности У преобразуется в три операции в Я, выполняется соотношение т' < т < Зт'. Часть Е Сложные структуры данные Я2 Так как гп = 0(т'), из границы времени работы 0(т сн(п)) преобразованной последовательности Я следует граница 0(т' ск(п)) времени работы исходной по- следовательности У.
В оставшейся части этого раздела мы полагаем, что исходная последовательность из т' операций МАке-бет, 01ч1Ох н г1мп-Бет преобразована в последовательность из т операций МАке-бет, [.1нк и г1хп-Бет. Теперь докажем, что время выполнения полученной последовательности равно 0(т сн(п)), и обратимся к лемме 21.7 для доказательства времени работы 0(т' ск(п)) исходной последовательности из т' операций. 1ече1(х) = шах(й: х.р.гагй > Аь(х.ппй)), т.е.
1ече1(х) — наибольший уровень (с, для которого Аы примененное к рангу х, не превышает ранг родителя х. Мы утверждаем, что О (!ече1(х) ( сн(п) . (21.1) Это можно подтвердить следующим образом. Мы имеем х.р.гагй > х.ганн+1 = Ао(х. гатй) (согласно лемме 21А) (согласно определению Ао (7')), откуда вытекает, что 1ече1(х) > О, и мы имеем А 1„1(х.гапк) > А ОО(1) >п > х.р.
гап1с (поскольку Аь(7') строго возрастающая) (согласно определению сн(п)) (согласно лемме 21.6), откуда вытекает, что 1ече1(х) < ск(п). Заметим, что, поскольку х.р. ганя монотон- но растет со временем, то же происходит и с 1ече1(х). Функция потенциала Используемая нами функция потенциала каждому узлу х в лесу непересекающихся множеств после выполнения а операций присваивает потенциал фд(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
