Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 136
Текст из файла (страница 136)
Этим ограничениям на х удовлетворяют все узлы на пути поиска, кроме не более чем а(п) + 2 узлов. Приведенным условиям не удовлетворяют первый узел на пути поиска (если он имеет нулевой ранг), последний узел пути (т.е. корень), а также последний узел ш на пути, для которого 1ече1(нт) = И для каждого /с = О, 1, 2,..., а(п) — 1. Зафиксировав такой узел х, покажем, что потенциал х уменьшается как минимум на 1. Пусть /с = 1ече1(х) = 1ече1(у). Непосредственно перед сжатием пути в процедуре Р//цгз-Бит мы имеем б!7 Глана 11.
Структуры данныи для неиересекающился миоисеста Поскольку после сжатия пути и х, и у имеют один и тот же родительский узел, мы знаем, что после сжатия пути х.р. тппИ = у.р. тапИ и что сжатие пути не уменьшает у.р. тапИ. Поскольку х. тапИ не изменяется, после сжатия пути х.р. тапИ > А~~,'~ 1(х. тапИ). Таким образом, сжатие пути приводит к тому, что либо увеличивается Нег(х) (как минимум до 1 + 1)„либо увеличивается 1ече1(х) (что происходит, когда 11ег(х) увеличивается как минимум до х. тапИ + 1).
В любом случае в соответствии с леммой 21.10 фч(х) ( фч г(х) — 1. Следовательно, потенциал х уменьшается как минимум на 1. Амортизированная стоимость операции Рпчп-Бит равна фактической стоимости плюс изменение потенциала. Фактическая стоимость равна 0(я), и мы показали, что обший потенциал уменьшается как минимум на шах(0, я — (ге(п) + 2)).
Амортизированная стоимость, следовательно, не превышает 0(я) — (я— (сл(п) + 2)) = 0(а) — я + 0(сл(п)) = 0(сл(п)), так как мы можем масштабировать потенциал таким образом, чтобы можно было пренебречь константой, скрытой в 0(я). Теперь, после того как мы доказали все приведенные выше леммы, перейдем к следующей теореме. Теорема 21.14 Последовательность из еп операций МЛКН-БНт, 11Н1ОМ и Р1МП-Бит, п из которых — операции Млкн-бит, может быть выполнена над лесом непересекаюшихся множеств с использованием объединения по рангу и сжатия пути за время 0(т а(п) ) в наихудшем случае. Доказавееаьслево.
Непосредственно следует из лемм 21.7 и 21.11-21.13. ° Упражнения Л.4.1 Докажите лемму 21.4. Л.4.2 Докажите, что каждый узел имеет ранг, не превышающий ~1б п1. 21.4.3 Сколько в свете упр. 21.4.2 битов требуется для хранения х. тап(с для каждого узла х? 21.4.4 Используя решение упр. 21.4.2, приведите простое доказательство того факта, что операции над лесом непересекаюшихся множеств с использованием объединения по рангу, но без сжатия пути, выполняются за время 0(т 1я п). 21.4.5 Профессор полагает, что поскольку ранг узла строго возрастает вдоль простого пути к корню, уровни узлов должны монотонно возрастать вдоль этого пути.
6?8 Часть и Сложные структуры даннык Другими словами, если х. гатй > 0 и х.р — не корень, то 1ечеЦх) < 1ече1(х.р). Прав ли профессор? 21.4.6 * Рассмотрим функцию ек'(и) = пйп (й: Аь(1) > 1я(п+ 1)). Покажите, что для всех практических значений п выполняется неравенство ек'(и) < 3.
Покажите также, воспользовавшись решением упр. 21.4.2, каким образом следует модифицировать функцию потенциала для доказательства того, что последовательность из гп операций Млкп-Зпт, 1)нипч и Гпчп-Зпт, п из которых — операции Млкк-бит, может быть выполнена над лесом непересекающихся множеств с использованием объединения по рангу и сжатия пути за время 0(тп се'(п)) в наихудшем случае. Задачи 21.1.
Минимум в автономном режиме Задача поиска минимума в автономном режиме (ой-11пе ппшпплп ргоЫеш) состоит в следующем. Пусть имеется динамическое множество Т с элементами из области определения (1,2,...,п), поддерживающее операции 1мэпкт и Ехтклст-Мпч. Задана последовательность Я из и вызовов 1нзпкт и т выювов Ехтклст-Мпч, в которой каждый ключ из (1, 2,..., п) вставляется ровно один раз.
Мы хотим определить, какой ключ возвращается каждым вызовом ЕхтклстМпч, т.е. заполнить массив ех1гас1ее111 .. т), где ех1гос1ее)И (для 1 = 1, 2,..., т) представляет собой ключ, возвращаемый 1-м вызовом Ехтклст-Мпч. Задача "автономна" в том смысле, что перед тем как приступить к вычислениям, ей известна вся последовательность Я. а.
В следующем экземпляре задачи каждый вызов 1хзект(1) представлен вставляемым числом г', а каждый вызов Ехтклст-Мпч представлен буквой Е: 4,8,Е,З,Е,9,2,6,Е,Е,Е,1,7,Е,5. Заполните массив ех1гасгеа корректными значениями. Чтобы разработать алгоритм для решения этой задачи, разобьем последователь- ность 3 на гомогенные подпоследовательности, т.е. представим Я в таком виде: 1ы Е, 1з, Е, 1з,..., 1, Е, 1 ез, где каждая буква Е представляет один вызов Ехтклст-Мпч, а 1 представляет (возможно, пустую) последовательность вызовов 1мзпкт.
Для каждой подпоследовательности 1 мы сначала помещаем ключи, вставленные данными операциями в множество Ка (которое является пустым, если подпоследовательность 1, пуста). Затем делаем следующее. 619 Глава 2Л Структуры данные длв неаересекающшсн мнажеств Оер-1.пче-Мпч!мпм (тп, и) 1 (ог 1 = 1 Го и 2 Определяем з, такое, что 1 Е К 3 Ы7' ~ ел+ 1 4 ехйас1есЦ2] = 1 5 Пусть 1 — наименьшее значение, большее, чем з, для которого существует множество К~ 6 К~ = К О Кос уничтожением К, 7 гегнгп ехгтас~ел( б. Докажите корректность массива ехгтас1ед, возвращаемого процедурой Оее11не-Мппмпм. е.
Опишите, как эффективно реализовать процедуру Оее-(,пче-Мпимпм с использованием структур данных для непересекающихся множеств. Дайте точную оценку времени работы вашей реализации в наихудшем случае. 21.2. Определение глубины В задаче но онределению глубины (бер1п-оезепшпайоп ргоЫеш) мы работаем с лесом У = Щ корневых деревьев, в котором поддерживаются следующие три операции. Млке-Ткее(и) создает дерево, состоящее из единственного узла и.
Рп э-Пертн(и) возвращает глубину узла и в его дереве. Оклрт(т, и) (" прививка" ) делает узел т, являющийся корнем, дочерним по отношению к узлу и, который находится в дереве, отличном от дерева т, но при этом не обязательно должен сам быть корнем. а. Предположим, что мы используем представление дерева, аналогичное лесу непересекающихся множеств: и.
р является родительским узлом и, и если и— корень, то и.р = и. Реализуем процедуру Бклег(т,и) путем присваивания т.р = и, а Рпчп-Верти(и) — как следование по пути поиска к корню с подсчетом всех узлов (кроме и), встречающихся на этом пути. Покажите, что время работы последовательности из тп процедур Млке-Ткее, Рпчп-Пертн и Оклет в наихудшем случае равно ку(тз).
Используя объединение по рангу и сжатие пути, мы можем сократить время работы в наихудшем случае. Воспользуемся лесом непересекающихся множеств 8 = (Яе), где каждое множество Я, (представляющее собой дерево) соответствует дереву Т; в лесу У. Структура дерева в Яе не обязательно соответствует структуре дерева Ть Однако хотя реализация Я; не хранит точные отношения "родитель-потомок", она позволяет определить глубину любого узла в То Ключевая идея состоит в хранении в каждом узле и "псевдодистанции" и. Н, которая определена таким образом, что сумма псевдодистанций вдоль простого пути от и к корню его множества Я; равна глубине и в Ть Иначе говоря„если простой путь от и к корню в Я; представляет собой последовательность ио, им..., иь, где ио = и, а иь — корень Яо то глубина и в Т, равна 2' ,о и,.
е(. ь Часть Е Сложные струютуры данник бго б. Приведите реализацию процедуры МАке-Ткее. в. Покажите, как следует изменить процедуру р1м1з-Бег для реализации процедуры г!Х1З-ПЕРТН. Ваша реализация должна осуществлять сжатие пути, а время ее работы должно линейно зависеть от длины пути поиска. Убедитесь в корректности обновления псевдодистанций вашей процедурой. г.
Покажите, как можно реализовать процедуру СзеАРт(т, и), которая объединяет множества, содержащие т и и, модифицируя процедуры Пнзглы и 1лыК. Убедитесь в корректности обновления псевдодистанций вашей процедурой. Не забывайте, что корень множества Бз не обязательно должен быть юрием соответствующего дерева Ть д. Дайте точную оценку времени работы в наихудшем случае для последовательности из т операций МАке-Ткее, Р1мзз-Пегтн и ПЕАРт, и из которых— операции МАке-Ткее. 21.3. Алгоритм Таржана длн автономного поиска нанменынего общего предка Наименьший общий предок (1еаж сопппоп апсеззог) двух узлов и и и в юрневом дереве Т представляет собой узел зс, который среди узлов, являющихся предками как и, так и и, имеет наибольшую глубину.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
