Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 133
Текст из файла (страница 133)
Однако, как показывает следующая теорема, последовательность из гп операций МАке-бег, 1)мюм и Р1мо-Яет, п из которых составляют операции МАке-бег, требует для выполнения время 0(пз+ п!яп). Теорема 21.1 При использовании связанных списков для представления непересекающихся множеств и применении весовой эвристики последовательность из пз операций МАке-Яет, 1)мюм и Р1мо-бег, п из которых составляют операции МАке-бег, требует для выполнения время 0(гп + и 1к п).
Доказательство. Поскольку каждая операция ()М10М объединяет два непересекающихся множества, всего выполняется не более и — 1 операции 1)М1ОМ. Теперь вычислим границу для общего времени, требуемого для выполнения этих операций 1)М1ОМ. Начнем с вычисления верхней границы количества обновлений указателей на объект множества для каждого из и элементов. Рассмотрим конкретный объект х. Мы знаем, что всякий раз, когда происходит обновление б03 Глава 2Е Структуры данные для ненересекаюнрлкся тналкеств указателя в объекте х, он должен находиться в меньшем из объединяемых множеств.
Следовательно, юша происходит первое обновление указателя в обьекте х, образованное в результате множество содержит не менее двух элементов. При следующем обновлении указателя на представителя в объекте х полученное после объединения множество содержит не менее четырех членов. Продолжая рассуждения, приходим к выводу о том, что для произвольного Й ( п, после того как указатель в объекте х был обновлен (1я Ц раз, полученное в результате множество должно иметь не менее й элементов. Поскольку максимальное множество может иметь толью и элементов, во всех операциях 11Х10Х указатель каждого объекта может быть обновлен не более (16 п1 раз.
Мы должны также учесть обновления указателей Гай и длин списков, для выполнения которых при каждой операции ПХюХ требуется Сэ(1) времени. Таким образом, общее время, необходимое для обновления и объектов, составляет 0(п 1к и). Отсюда легко выводится время, необходимое для всей последовательности нз т операций. Каждая операция МАке-Яет и ргхо-Яет занимает время 0(1), а всего их — 0(т). Таким образом, полное время выполнения всей последовательности операций — О(т + п 1к и).
Упражнения 21.2.1 Напишите псевдокод процедур МАке-Яет, Р1хо-Яет и Пхюх с использованием связанных списков и весовой эвристики. Не забудьте указать атрибуты, которые должны быть у объектов множеств и объектов списков. 21.2.2 Покажите, какая образуется структура данных и какие ответы дают операции Ргхо-Яет в следующей программе. Используются представление с помощью связанных списков и весовая эвристика. 1 уоге = 11о16 2 МАке-Яет(х;) 3 1ог 1 = 1 го 16 Ьу 2 4 ПХЮХ(х;, х,+~) 5 1ог 1 = 1 Го 13 Ьу 4 б ПХ1ОХ(хс, х,+г) 7 13х!ох(хо хз) 8 Пхюх(хы, х1з) 9 11хюх(хм х10) 16 Ело-Яет(хг) р[ХО-ЯЕТ(хд) Считаем, что если множества, содержащие х; и х,, имеют один и тот же размер, то операция ПХЮХ(х,, х ) присоединяет список х, к списку х,.
Часто и Сложные структуры данньи 604 21.2.5 Адаптируйте доказательство теоремы 21.1 для получения границ амортизированного времени выполнения процедур Млке-Яет и г1мп-Зет, равного 0(1), и амортизированного времени выполнения процедуры Бм1ом, равного 0(1яп), при использовании связанных списков и весовой эвристики. 21.2.4 Найдите точную асимптотическую границу времени работы последовательности операций на рис. 21.3 в предположении использования связанных списков и весовой эвристики. 21.2.5 Профессор подозревает, что в каждом объекте множества можно поддерживать только один указатель вместо двух (леал и 1ал(), в то время как в каждом элементе списка их количество равно двум.
Покажите, что подозрения профессора небезосновательны, описав, как представить каждое множество связанным списком, таким, что каждая операция имеет то же время работы, что и указанное в тексте раздела. Опишите также, как работают эти операции. Ваша схема должна использовать эвристику с тем же эффектом, что и описанный в тексте раздела. (Указание: используйте в качестве представителя множества хвост списка.) 21.2.6 Предложите простое изменение процедуры Пм1оы для связанных списков, которое избавляет от необходимости поддерживать указатель 1ал( на последний объект каждого списка.
Ваше предложение не должно изменить асимптотическое время работы процедуры П1ч1ом независимо от того, используется ли в ней весовая эвристика. (Указание: вместо присоединения одного списка к другому воспользуйтесь вставкой в начало списка.) 21.3. Леса непересекающихся множеств В более быстрой реализации непересекающихся множеств мы представляем множества в виде корневых деревьев, каждый узел которых содержит один член множества, а каждое дерево представляет одно множество. В лесу непересекающихся множеств (Йа1о(пнзег Гогеаг) (рис.
21,4, (а)) каждый член указывает только на родительский узел. Корень каждого дерева содержит представителя и является родительским узлом для самого себя. Как мы увидим далее, хотя наивное программирование и не приводит к более эффективной работе по сравнению со связанными списками, введение двух эвристик — "объединение по рангу" и "сжатие пути" — позволяет достичь асимптотически оптимального выполнения операций над непересекающимися множествами.
Три операции над непересекающимися множествами выполняются следующим образом. Операция Маке-Бег просто создает дерево с одним узлом. Поиск в операции Рпчгз-Яет выполняется простым перемещением до корня дерева по 605 )лака Л. Сндгукнорм данник для ненересекающнгсл множеств (а) (6) Рис. 21А. Лес непересекаккдился множеств. (а) Дка дерева представляют дяа мнвкестяа, показанных на рис.
21.2. Дерево слева предсгакляет множестао (Ь, с, е, Ц, где с якяяется предсталителем, а дерево спряла представляет множесгко (Н, У, д) с представителем У. (61 Результат ямполнення ()нюн(е, д). указателям на родительские узлы. Посещенные узлы на этом простом пути составляют путь поиска (йпб раб)).
Операция ())(ю)(, показанная на рис. 21.4, (б), состоит в том, что корень одного дерева указывает на корень другого. Эвристики для снижения времени работы Пока что у нас нет никаких особых преимуществ перед реализацией с использованием связанных списков: последовательносп из п — 1 операций Шею)с может создать дерево, которое представляет собой линейную цепочку из и узлов. Однако мы можем воспользоваться двумя эвристиками и достичь практически линейного времени работы от общего количества операций пг.
Первая эвристика, объединение ло рану (нлюп Ьу шл((), аналогична весовой эвристике при использовании связанных списков. Ее суть заключается в том, чтобы корень дерева с меньшим количеством узлов указывал на корень дерева с ббльшим количеством узлов. Вместо явной поддержки размера поддерева для каждого узла можно воспользоввться подходом, который упростит анализ, — использовать ранг (гап)() каждого корня, который представляет собой верхнюю границу высоты узла. При выполнении операции ())ч)о)ч корень с меньшим рангом должен указывать на корень с ббльшнм рангом.
Вторая эвристика, сжатие пути (ра(Ь сошргезя(оп), также достаточно проста и эффективна. Как показано на рис. 21.5, она используется в процессе выполнения операции г поп-Бвт и делает каждый узел указывающим непосредственно на корень. Сжатие пути не изменяет ранги узлов.
Псевдокт)д для работы с лесами непересекающихся множеств Для реализации леса непересекающихся множеств с применением эвристики объединения по рангу мы должны отслеживать ранг узлов. Для каждого узла х нами поддерживается целочисленное значение х. гап(с, которое представляет собой верхнюю границу высоты х (количество ребер на самом длинном простом пути от х к листу, являющемуся его потомком).
При создании множества из одного элемента процедурой Мдкй-КЕт начальный ранг узла в соответствующем Часть и Сложные струюауры данных 16) Рис. 21.5. Сжатие пути в процессе операции Ргмо-Бнт. Стрелки и петли в корнея опугцены. (а) Дерево, представжпогдее множество, ло выполнения оперцпж Рцго-Бпт(о). Треугольники представлжст поддсревья, корнями которых явлжотся показанные узлы. Каждыа узел имеет указатель на своего родителя.
(а) То же множество после выполнения операции арно-Бнт(а). Квждма узел на пути поиска теперь указывает непосредспжнно на корсаж. дереве устанавливается равным О. Операции Р(ыо-Яет оставляют ранги неизменными. При применении процедуры П(чу(6 для обьединения двух деревьев имеются две ситуации, зависящие от того, имеют объединяемые деревья одинаковый ранг или нет. Если ранги деревьев разные, мы делаем юрана с ббльшим рангом родительским узлом по отношению к корню с меньшим рангом, но сами ранги лри этом остаются неизменными. Если же корни имеют одинаковые ранги, то мы произвольным образом выбираем один из корней в качестве родительского и увеличиваем его ранг.
Переведем этот метод в псевдокод. Родительский ло отношению к х узел обозначается как х.р. Процедура Ьнчк, являющаяся подпрограммой, вызываемой процедурой П(ч(о(с, получает в качестве входных данных указатели на два мзрня. МАКЕ-ЗЕТ(х) 1 хр=х 2 х.гап)г = О ()16(О(Ч(х, р) 1 1ХК(РЕЮ-БЕТ(х), Р1Ж-БЕТ()()) б07 Глана 7Ъ Структуры Ьанннт длн ненересекающиксн мнатнсте 1.1мк(х, у) 1 !1 х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
