Алгоритмы - построение и анализ (1021735), страница 122
Текст из файла (страница 122)
Непосредственно перед сжатием пути в процедуре Рпс!з Янт мы имеем: гапИ [р [х]] > Аьб " * (гап!с [х]) папИ [р [у]] > Аь (гапИ [у]) гапИ [у] > тапИ [р [х]] по определению Ыег (х), по определению 1ече1 (х), согласно следствию 21.5, поскольку у следует за х. Объединяя приведенные неравенства и обозначая через г значение !сег (х) перед сжатием пути, получаем: тапИ [р[у]] > Аь(тапИ [у]) > Аь(татй [р[х]]) > > Аь (А!ь' '~*~! (гатй [х])) = А~,'~ ! (гапИ [х]), где второе неравенство следует из того, что Аь(1) — строго возрастающая функция.
Поскольку после сжатия пути и х, и у имеют один и тот же родительский узел, мы знаем, что после сжатия пути татй [р[х]] = тапИ [у[у]] и что сжатие пути ие уменьшает тапИ [р[у]]. Поскольку гагй [х] не изменяется, после сжатия пути тапИ [р[х]] > Аьб+ (гаиИ [х]). Таким образом, сжатие пути приводит к тому, что либо увеличивается !1ег (х) (как минимум до с + 1), либо увеличивается 1ече1 (х) (как минимум до гапИ [х] + 1).
В любом случае, в соответствии с леммой 21.9, фе (х) < фс г (х) — 1. Следовательно, потенциал х уменьшается как минимум на 1. Амортизированная стоимость операции Р!нп Япт равна фактической стоимости плюс изменение потенциала. Фактическая стоимость равна О (в), и мы показали, что общий потенциал уменьшается как минимум на шах (О, в — (сх (и) + 2)). Амортизированная стоимость, таким образом, не превышает О (в) — (в — (сс(и) + + 2)) = 0 (в) — в + 0 (сс (и)) = 0 (сх (и)), так как мы можем масштабировать потенциал таким образом, чтобы можно было пренебречь константой, скрытой в 0(в).
Глава 21. Структуры данных для непересекающихся множеств 601 Теперь, после того как мы доказали все приведенные выше леммы, мы можем перейти к следующей теореме. Теорема 21.13. Последовательность из т операций МлкЕ БЕт, 1)ион и ймп Бет, и из которых — операции Млкн Бит, может быть выполнена над лесом непересекающихся множеств с использованием объединения по рангу и сжатия пути за время О (тгг (и)) в наихудшем случае. 21.4-1. 21.4-2. 2 1.4-3. Докажите лемму 21.4. Докажите, что ранг произвольного узла не превышает [1к и].
С учетом решения упражнения 21.4-2, сколько битов требуется для хра- нения поля гаик [х] узла х? 21.4-4. Используя решение упражнения 21.4-2, приведите простое доказательство того факта, что операции над лесом непересекающихся множеств с использованием объединения по рангу, но без сжатия пути, выполняются за время О (т 1я и). Профессор полагает, что поскольку ранг узла строго возрастает вдоль пути к корню, уровни узлов должны монотонно возрастать вдоль этого пути. Другими словами, если гаик [х] ) 0 и р[х] — не корень, то 1ече1 (х) < 1ече1 (р [х]).
Прав ли профессор? Рассмотрим функцию гг'(и) = ппп(й: Аь(1) > 1к(и+1)). Покажите, что для всех практических применений гг' (и) < 3. Покажите также, воспользовавшись решением упражнения 21.4-2, каким образом следует модифицировать аргумент потенциальной функции для доказательства того,что последовательность изтопераций Млке Янт,1)н1онирп и Бег, и из которых — операции Млнн Бнт, может быть выполнена над лесом непересекающихся множеств с использованием объединения по рангу и сжатия пути за время О (т гг' (и)) в наихудшем случае.
2 1.4-5. * 21.4-6. Задачи 21-1. Минимум в автономном режиме Задача лоиска минимума в автоаамиом режиме (ой-11ле пппппшп ргоЬ1еш) состоит в следующем. Пусть имеется динамическое множество Т с элементами из области определения (1,2,...,и), поддерживающее операции 1нзвкт и Ехтклсг Мпч. Задана последовательность Я из и Доказательство. Непосредственно следует из лемм 21.7, 21.10, 21.11 и 21.12. ° Упражнения Часть Ч. Сложные структуры данных 602 вызовов 1нзккт и т вызовов Ехтклст Мпч, в юторой каждый ключ из (1,2,...,п) вставляется ровно один раз.
Мы хотим определить, каюй ключ возвращается каждым вызовом Ехтклст Мпч, т.е. мы хотим заполнить массив ех$гас1ей [1..т], где ех~гасгей [г) (1 = 1, 2,..., т) представляет собой ключ, возвращаемый 1-м вызовом Ехтклст Мпч. Задача "автономна'* в том смысле, что перед тем как приступить к вычислениям, ей известна вся последовательность Я полностью. а) В следующей последовательности каждый вызов 1нзккг представлен вставляемым числом, а каждый вызов Ехтклст Мпч представлен буквой Е: 4, 8, Е, 3, Е, 9, 2, 6, Е, Е, Е, 1, 7, Е, 5. Заполните массив ехЬ асилей.
Для разработки алгоритма для решения этой задачи разобьем последовательность Е на гомогенные подпоследовательности, т.е. представим 8 в таюм виде: 1ы Е, 1з, Е, 1з,..., 1, Е, 1 +3 где каждая буква Е представляет один вызов Ехтклст Мпч, а 1 — последовательность (возможно, пустую) вызовов 1нзпкт. Для каждой подпоследовательности 1 мы сначала помещаем ключи, вставленные данными операциями, в множество К (которое является пустым, если подпоследовательность 1, пуста). Затем сделаем следующее: Огг 1пчн М~ммим[пз, и) 1 хогг' -1гоп 2 йо Определяем 3, таюе что г е Ку 3 113 от+1 4 гйеп ехгтас~ей Ц вЂ” ю' 5 Пусть 1 — наименьшее значение, большее 3 для которого существует множество К~ 6 К~ +- Ку 0 Кп уничтожаем К.
7 геФнгп ехйас1еИ б) Покажите корректность массива ех$гас1еа, возвращаемого процедурой Огг 1пчп Мммим. в) Опишите, как эффективно реализовать процедуру Огг 1.!нв М~ммсм с использованием структур данных для непересекающихся множеств. Дайте точную оценку времени работы вашей реализации в наихудшем случае.
Глава 21. Структуры данных для непересекающихся множеств 603 21-2. Определение глубины В задаче по определению глубины 1дердз-де1епшпа6оп ргоЫет) мы работаем с лесом Т = (Т;) корневых деревьев, в котором поддерживаются следующие три операции. МАке Тнее(е) создает дерево, состоящее из единственного узла е. Р1НР РЕРТН(с) возвращает глубину узла и в его дереве. ОЕАет(т, е) ("прививка") делает узел г, являющийся корнем, дочерним по отношению к узлу с, который находится в дереве, корень которого отличен от г, но при этом не обязательно должен сам быть корнем.
а) Предположим, что мы используем представление дерева такое же, как и в случае непересекающихся множеств: р [с] является родительским узлом е, и если о — корень, то р [с] = е. Реализуем процедуру Оклет(г, и) путем присвоения р [т] + — и, а Р1нп Регтн(п) — как поиск пути к корню с подсчетом всех узлов (кроме п), встречающихся на этом пути. Покажите, что время работы последовательности из гп процедур Млке Ткее, Р!х0 РеРтн и Оклет в худшем случае равно г) Используя объединение по рангу и сжатие пути, мы можем снизить время работы в наихудшем случае. Воспользуемся лесом непересекающихся множеств 8 = (Яз), где каждое множество о1 (представляющее собой дерево) соответствует дереву Т; в лесу Т.
Структура дерева в Яг не обязательно соответствует структуре дерева Т;. Однако хотя реализация Яг не хранит точные отношения родитель-потомок, но тем не менее она позволяет нам определить глубину любого узла в Ть Ключевая идея состоит в хранении в каждом узле е "псевдодистанции" Ы [е], которая определена таким образом, что сумма псевдодистанций вдоль пути от е к корню его множества 51 равна глубине п в Т;; т.е. если путь от е к корню Яг представляет собой последовательность по,пм, еь, где по = еь и сь — корень Я;, то глубина е в Т, равна 2.з=о д [ьу].
б) Приведите реализацию процедуры МАКЕ ТНЕЕ. в) Покажите, как следует изменить процедуру Р1 в Бет лля реализации процедуры Р1хп дегтя. Ваша реализация должна осуществлять сжатие пути, а время ее работы линейно зависеть от длины пути. Убедитесь в корректности обновления псевдодистанций вашей процедурой. 604 Часть Ч. Сложные структуры данных г) Покажите, как можно реализовать процедуру ОКАет(т, и), которая объединяет множества, содержащие т и и, модифицируя процедуры Бн1он и Ь1нк.
Убедитесь в корректности обновления псевдодистанций вашей процедурой. Не забывайте, что корень множества Я; не обязательно должен быть корнем соответствующего дерева Т,. д) Дайте точную оценку времени работы в наихудшем случае последовательности из тп операций МАке Ткее, Р1н0 1)еетн и ОЕАР, и из которых — операции МАке Ткее. 21-3. Алгоритм Таржана для автономного поиска наименьшего общего предка наименыиий общий предок (1еам сопппоп апсез1ог) двух узлов и и и в корневом дереве Т представляет собой узел ю, который среди узлов, являющихся предками как и, так и и, имеет наибольшую глубину. В задаче автономного ноиска наименыиего общего предка (ой'-1ше !еаз1- сопппоп-апсез1ог ргоЫет) дано корневое дерево Т и произвольное множество Р = ((и, иЦ неупорядоченных пар узлов в Т.
Для каждой пары узлов нз Р требуется найти их наименьшего общего предка. Для решения задачи автономного поиска наименьшего общего предка осуществляется обход дерева Т путем вызова приведенной ниже процедуры 1 СА(тиос [Т]). Предполагается, что перед вызовом процедуры все узлы помечены как тин1те 1белые): 1.СА(и) 1 МАКЕ БЕТ(и) 2 апсевсот[Р1Х0 БЕТ(и)] — и 3 Рог (для) каждого и, дочернего по отношению к и 4 до ЬСА(и) 5 ЫН1ОН(и, и) 6 апсевтот[Р1Н0 БЕт[и)] + — и 7 со1от[и] — НЬАСК 8 1ог (для) каждого и, такого что (и, и) Е Р 9 Йо 11 со1от[и] = В1.АСК 1О Феп рпп1 "Наименьшим общим предком" и" и "и "является" апсев1от[Р1но бег[и)] а) Покажите, что строка 10 выполняется в точности по одному разу для каждой пары (и, и) Е Р. б) Покажите, что при вызове ЬСА[и) количество множеств в структуре данных для непересекающихся множеств равно глубине и в Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
