Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 121
Текст из файла (страница 121)
Представителем нового множества является элемент, который был представителем множества, содержащего у. К сожалению, при этом мы должны обновить указатели на представителя у каждого объекта, который первоначально находился в списке, содержащем х, что требует времени, линейно зависящего ат длины списка, содержащего х. В действительности, не трудно привести последовательность из т операций над и объектами, которая требует О (из) времени. Предположим, что у нас есть объекты х1,хз ...,х„. Мы выполняем последовательность из и операций МАке Бет, за которой следует последовательность из и — 1 операций 11яо1ч, показанных в табл.
21.2, так что ги = 2и — 1. На выполнение и операций МАКЕ Яет мы тратим время 0(и). Посюльку 1-я операция 1)ы1о1ч обновляет 1 объектов, общее юличество объектов, обновленных всеми и — 1 операциями 1)ы1он, равно и — 1 1= 0(и ) 1=1 Таблица 21.2. Последовательность операций прн использовании связанных списков Операция Количество обновленных объектов МАке Еет(х1) МАке Яет(хз) МАке Бег(х„) ПМ10х(х1 хз) Пн1он(хз, хз) инюн(хз ха) п — 1 шчюн(х 1,х ) Глава 21.
Структуры данных для непересекающихся множеств 587 Общее количество операций равно 2п — 1, так что каждая операция в среднем требует для выполнения времени О (и). Таким образом, амортизированное время выполнения операции составляет 9 (и). Весовая эвристика В худшем случае представленная реализация процедуры 13н!он требует в среднем О (и) времени на один вызов, поскольку может оказаться, что мы присоединяем длинный список к короткому и должны при этом обновить поля указателей на представителя всех членов длинного списка. Предположим теперь, что каждый список включает также поле длины списка (которое легко поддерживается) и что мы всегда добавляем меньший список к большему (при одинаковых длинах порядок добавления безразличен). При такой простейшей весовой зврисгиике (юе181пес1-ил(оп Ьеипз6с) одна операция Бнюн может потребовать Й (и) времени, если оба множества имеют по Й (и) членов.
Однако, как показывает следующая теорема, последовательность из тп операций МАке Бет, БьлОН и Р! П) Зет, п из которых составляют операции МАке Яет, требует для выполнения О (т + и 18 и) времени. Теорема 21.1. При использовании связанных списков для представления непересекающихся множеств и применении весовой эвристики, последовательность из тп операций МАке Бет, Пн!он и Рпчп Бет, и из которых составляют операции МАке Бет, требует для выполнения О (пз+ и18п) времени.
Доказаигеаьстао. Начнем с вычисления верхней границы количества обновлений указателя на представителя для каждого объекта множества из п элементов. Рассмотрим фиксированный объект и. Мы знаем, что всякий раз, когда происходит обновление указателя на представителя в объекте х, он должен находиться в меньшем из обьединяемых множеств. Следовательно, когда происходит первое обновление указателя на представителя в объекте х, образованное в результате множество содержит не менее 2 элементов. При следующем обновлении указателя на представителя в обьекте х полученное после обьединения множество содержит не менее 4 членов.
Продолжая рассуждения, приходим к выводу о том, что для произвольного й < п, после того как указатель на представителя в объекте х обновлен (18 1с) раз, полученное в результате множество должно иметь не менее Й элементов. Поскольку максимальное множество может иметь только п элементов, во всех операциях Ун!он указатель на представителя у каждого объекта может быть обновлен не более (18 и"! раз.
Мы должны также учесть обновления указателей Ьеаа и 1а11 и длины списка, для выполнения которых при каждой операции Пнюн требуется О (1) времени. Таким образом, общее время, необходимое для обновления и объектов, составляет О (и!8п). Часть Ч. Сложные структуры данных 588 Отсюда легко выводится время, необходимое для всей последовательности из т операций.
Каждая операция МАке Яет и Р!хп Бег занимает 0(1) времени, а всего их — О (ги). Таким образом, полное время выполнения всей последовательности операций составляет 0 (ги + и 18 и). Упражнения 21.2-!. Напишите псевдокод процедур МАКЕ ЯЕТ, Рп 0 БЕТ и 11Х!0Х с использованием связанных списков н весовой эвристики. Считаем, что каждый объект х имеет атрибут гер [х], указываю!ций на представителя множества, содержащего х, и что каждое множество Я имеет атрибуты Ьеад [Я], 1ап [э] и а!хе [Я] (который равен длине списка). 21.2-2. Покажите, какая образуется структура данных и какие ответы дают процедуры Р!Х0 5ЕТ в следующей программе. Используется представление при помощи связанных списков и весовая эвристика.
1 !'ог 1 — 1 1о 16 2 !!о МАке Бет(х!) 3 1'ог г' — 1 Со 15 Ьу 2 4 !!о 11х!ох(х1, х,+1) 5 1огг -1го13Ьу4 6 Йо 13х!Ох(х1, х1-!.з) 7 1.1ХЮХ(Х1, хь) 8 13Х!ОХ(хп|х!3) 9 11х!0х(х1, х10) 10 Р!х0 Бет(хз) 11 Р!Хр БЕТ(хд) Считаем, что если множества, содержа!цие х; и х, имеют одинаковый размер, то операция 11х!ох(х1,х ) присоединяет список х к списку хь 21.2-3. Адаптируйте доказательство теоремы 21.1 для получения границ амортвзированного времени выполнения процедур МАке 5ет и Р!хп Бег, равного 0 (1), и амортизированного времени выполнения процедуры 11х!0х, равного О (18 и), при использовании связанных списков н весовой эвристики.
21.2-4. Найдите точную асимптотическую границу времени работы последовательности операций из табл. 21.2 в предположении использования связанных списков и весовой эвристики. 21.2-5. Предложите изменение процедуры 11х!ох для связанных списков, которое избавляет от необходимости поддерживать указатель !а!1 на последний объект каждого списка. Ваше предложение не должно изменить Глава 21. Структуры данных для непересекающихся множеств 589 асимптотическое время работы процедуры 1)ьлон независимо от того, используется ли в ней весовая эвристика. (Указание: вместо присоединения одного списка к другому, воспользуйтесь вставкой в начало списка.) 21.3 Лес непересекающихся множеств В более быстрой реализации непересекающихся множеств мы представляем множества в виде корневых деревьев, где каждый узел содержит один член множества, а каждое дерево представляет одно множество. В лесу непересекающихся множеств (гйз)опп-зет (огезт) (см.
рис. 21.3а, где вы видите два дерева, представляющие множества, ранее представленные на рис. 21.2) каждый член указывает только на родительский узел. Корень каждого дерева содержит представителя и является родительским узлом для самого себя. Как мы увидим далее, хотя наивное программирование и не приводит к более эффективной работе по сравнению со связанными списками, введение двух эвристик — "объединение по рангу" и "сжатие пути" — позволяет достичь асимптотически более быстрого выполнения операций над непересекающимися множествами. Три операции над непересекающимися множествами выполняются следующим образом. Операция Млкн Знт просто создает дерево с одним узлом.
Поиск в операции р1МП Бит выполняется простым передвижением до корня дерева по указателям на родительские узлы. Посещенные узлы на этом пути составляют путяь поиска (бпб ра1л). Операция (1н1Ом, показанная на рис. 21.3б, состоит в том, что корень одного дерева указывает на корень другого. Эвристики для повышения эффективности Пока что у нас нет никаких особых преимуществ перед реализацией с испольюванием связанных списков: последовательность из и- 1 операций ()хюн может создать дерево, которое представляет собой линейную цепочку из п узлов. Однако Й, ~6 ~ Я1 с~ Рис.
21.3. Лес непересекающихся множеств Часть Ч. Сложные структуры данньц 590 -у~ / Рис. 21.4. Сжатие пути в процессе выполнения операции Ршп 5вт мы можем воспользоваться двумя эвристиками и достичь практически линейного времени работы от общего количества операций т. Первая эвристика, объединение по рангу (ипюп Ьу гапк), аналогична весовой эвристике при использовании связанных списков. Ее идея заключается в том, чтобы корень дерева с меньшим количеством узлов указывал на корень дерева с большим количеством узлов. Вместо явной поддержки размера поддерева для каждого узла, можно воспользоваться подходом, который упростит анализ — использовать ранг (гапк) каждого корня, который представляет собой верхнюю границу высоты узла.
При объединении по рангу корень с меньшим рангом должен указывать на корень с большим рангом. Вторая эвристика, сжитие пути (рагЬ сошргезз1оп), также достаточно проста и эффективна. Как показано на рис. 21.4, она используется в процессе выполнения операции рича Бит и делает каждый узел указывающим непосредственно на корень. Сжатие пути не изменяет ранги узлов. Псевдокоды Для реализации леса непересекающихся множеств с применением эвристики обьединения по рангу, мы должны отслеживать ранг узлов. Для каждого узла х нами поддерживается целое значение таей [х], которое представляет собой верхнюю границу высоты х (количество ребер на самом длинном пути от х к листу, являющемуся его потомком). При создании множества из одного элемента Глава 21. Структуры данных для непересекающихся множеств 591 процедурой МАке Бет начальный ранг узла в соответствующем дереве устанавливается равным О.
Операции Р1мп Бет оставляют ранги неизменными. При применении процедуры Бн1он для объединения двух деревьев имеются две ситуации, зависящие от того, имеют объединяемые деревья одинаковый ранг, или нет. Если ранги деревьев разные, мы делаем корень с ббльшим рангом родительским узлом по отношению к корню с меньшим рангом, но сами ранги при этом остаются неизменными.
Если же корни имеют одинаковые ранги, то мы произвольным образом выбираем один из корней в качестве родительского и увеличиваем его ранг. В приведенных псевдокодах родительский по отношению к х узел обозначается как р [х]. Вспомогательная процедура ?лик, использующаяся в процедуре Уяоы, получает в качестве входных параметров указатели на два корня. МАКЕ БЕТ(х) 1 р[х] — х 2 тапк[х) ~- О 0хюм(х, у) Е1мк(Р1м1э Бет(х), Р1ьлз Бет(у)) алик(х, у) 1 !Т тапй[х] ) топя[у] 2 тпеп р[у] +- х 3 е!ве р[х] — у 4 1Т й[х] = апк[у] 5 тЬеп татй[у) — татй[у] + 1 Р1нп Бет(х) 1 Ыхфр[х] 2 тиеп р[х] — Р1НР БЕТ(р[х)) 3 геПзгп р[х] Процедура Р1н1з Бет является двухпроходной: при первом проходе она ищет путь к корню дерева, а при втором проходе в обратном направлении по найденному пути происходит обновление узлов, которые теперь указывают непосредственно на корень дерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
