1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 30
Текст из файла (страница 30)
Эта длина может быть и — 1, оэтому сложность выполнения и — 1 операций ОБЪЕДИНИТЬ, за которыми идут и операций НАЙТИ, может достигать 0(пз), Например, вычислим сложность выполнения последовательности операций ОБЪЕДИНИТЬ (1, 2, 2» ОБЪЕДИНИТЬ (2, 3, 3) ОБЪЕДИНИТЬ(п — 1, п, и) НАЙТИ(1) НАЙТИ(2) НАЙТИ(п) Выполнение и — 1 операций ОБЪЕДИНИТЬ приводит к дереву, изображенному на рис, 4.1б. Сложность выполнения п операций НАЙТИ пропорциональна л-! л (и — !) 2 ! о Однако ее можно уменьшить, если проводить балансировку деревьев.
Для этого можно в каждом дереве считать число узлов и, сливая два множества, всегда присоединять меньшее дерево к корню большего. Этот способ аналогичен вливанию меньшего множества в большее, которое мы применяли в предыдущем разделе. Лемма 4.1. Если при выполнении каждой операции ОБЪЕДИНИТЬ корень дерева с меньшим числом узлов (при равенстве узлов берется любое дерево) преобразуется в сына корня дерева с большим числом узлов, то высота дерева в лесу может достичь значения й, только если оно имеет не менее 2" узлов. Д о к а з а т е л ь с т в о. Доказательство проведем индукцией по А.
Для 6=0 утверждение верно, поскольку каждое дерево имеет л. е стртктиры длнных для злдлч с множвствлми Рис. 4дз. Лерепо после выполнения оперений ОБЪЕДИНИТЬ. по крайней мере один узел. Допустим, что утверждение верно для всех значений параметра, меньших А=. 1. Пусть Т вЂ” дерево высоты Ь с наименьшим числом узлов. Тогда оно должно было получиться п результате слияния деревьев Т, и Т„где Т,— дерево высоты У вЂ” 1 и у него узлов не больше, чем у Тя. По предположению индукцки Т, имеет не менее 2"-' узлов, н, значит, Т, имеет не менее 2л-1 узлов, откуда следует, что Т имеет не менее 2" узлов.
П Оценим время выполнения (в худшем случае) последовательности из и операций ОБЪЕДИНИТЬ и НАЙТИ, если пользоваться структурой данных.в виде леса, модифицированной так, что в операции ОБЪЕДИНИТЬ корень меньшего дерева становится сыном корня большего дерева. Никакое дерево не может иметь высоту, большую 1оя п. Следовательно, сложность выполнения 0(а) операций ОБЪЕДИНИТЬ и НАЙТИ не превосходит 0(п 1оя п). Эта граница точна в том смысле, что существуют последовательности из а операций, занимающие время, пропорциональное а 1оя и. Изложим еще одну модификацию этого алгоритма, называемую сжатием путей. Поскольку в общей сложности преобладает сложность операций НАЙТИ, попробуем уменьшить ее. Всякий раз, когда выполняется операция НАЙТИ(1), мы проходим путь от узла 1 до корня г. Пусть 1, о„п„..., о„, г — узлы на этом пути.
Тогда каждый из узлов 1, п„п„..., о„, делается сыном корня. На рис. 4.17, б отражено влияние операции НАЙТИ(1) на дерево, приведенное на рис. 4.17, а. ЗЛ. ДРЕВОВИДНЫЕ СТРУКТУРЫ ДЛЯ ЗАДАЧИ ОБЪЕДИНИТЬ вЂ” НАЙТИ Рис. 4ЛТ. Результат сжатая путей. Вся процедура слияния деревьев для задачи ОБЪЕДИНИТЬ— НАЙТИ, включая сжатие путей, выражена в следующем алгоритме.
Алгоритм 4.3. Алгоритм быстрого объединения непересекающихся множеств Вход. Последовательность о операций ОБЪЕДИНИТЬ и НАЙТИ, выполняемых на наборе множеств, элементы которых представлены целыми числами от 1 до и. Предполагается, что имена множеств также являются целыми числами от 1 до и и вначале множество с именем 1 состоит из единственного элемента — самого числа 1. Выход. Последовательность ответов на операции НАЙТИ нз а.
Ответ на каждую операцию НАЙТИ надо получить перед просмотром очередной операции в а. Метод. Описание алгоритма состоит из трех частей: организация начальной структуры, выполнение операции НАЙТИ и выполнение операции ОБЪЕДИНИТЬ. 1. Организация начальной ппруюпуры. Для каждого элемента 1, 1: 1(п, образуем узел оь Полагаем СЧЕТ [п,[ 1, ИМЯ [о~[=1 и ОТЕЦ[о~! О. Вначале каждый узел Р~ сам является деревом. Чтобы можно было определять кореньмножества 1, образуемтакой массив КОРЕНЬ, что КОРЕНЬ И указывает на о~. Чтобы определить узел, содержащий элемент Ь образуем массив ЭЛЕМЕНТ; вначале ЭЛЕМЕНТ [11 =Рь 2.
Выполнение операции НАЙТИ (1). Программа приведена на рис. 4.18. Начиная с узла ЭЛЕМЕНТ [11, идем по пути, ведущему к корню дерева, и выписываем встретившиеся узлы. По достижении ГЛ. С СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ С МНОЖВСТНАМН Ье((!п сделать СПИСОК пустым; о -ЭЛЕМЕНТ[!]; вЫ!е ОТЕЦ[о]ныл 4(о Ьен(п добавить о в список; и — ОТЕЦ[о] епб; сотшеп( о теперь корень; рНп! ИМЯ[о]; !ог для каждого си, входящего в СПИСОК бо ОТЕЦ[си] о епб Рис. 4.!8. Выполнение опенации НАЙТИ(1).
корня выдается имя множестви, а каждый узел из пройденного пути делается сыном корня. 3. Выполнении операции ОБЪЕДИНИТЬ(1, 1, й). С помощью массива КОРЕНЬ находим корни деревьев, представляющих множества 1 и !. Затем делаем корень меньшего дерева сыном корня большего дерева. См. рис. 4.19. П Покажем, что сжатие путей значительно ускоряет работу алгоритма. Чтобы подсчитать зто улучшение, введем функции Р и б.
Ьея(п ан!я положить СЧЕТ[КОРЕНЬ[1]] (СЧЕТ[КОРЕНЬ[!]] о(йегв!зе переставить 1' и 1 !и Ьей(п БОЛЬШОЙ - КОРЕНЬ[!]; МАЛЫЙ - КОРЕНЬ[1]; отец[МАЛЫЙ]- Большой; счет[Большой]-счет[Большой]+счет[мА- лый]; ИМЯ[БОЛЬШОЙ] — й; КОРЕНЬ[й] — БОЛЬШОЙ епб епб Рис. 4.19. Выполнение операции ОБЪЕДИНИТЬ(1, 1, А). «.т. дпивовидныи стпнкткры для здддчн оиъидинить — нанти и Р(п) Рис. 4.20.
Несколько значений функции Р. Пусть Р (О) = (, Р(г) = 2пи-0 для (> О. Функция Р растет очень быстро, как видно из таблицы на рис. 4.20. Функция 6(п) определяется как наименьшее число й, для которого Р(й))п. Функция 6 растет очень медленно. Действительно, 6(п)(5 для всех "практических" значений и, а именно для всех п(2«ььз«. Теперь покажем, что алгоритм 4.3 выполнит последовательность а из сп операций ОБЪЕДИНИТЬ и НАЙТИ за время, не большее с'п6 (и), где с и с' — постоянные, причем с' зависит от с. Для простоты предположим, что выполнение операции ОБЪЕДИНИТЬ занимает "единицу времени", а операции НАЙТИ(с) — время, пропорциональное числу узлов, лежащих на пути из узла с меткой г' в корень дерева, содержащего этот узел').
Определение. Удобно определить ранг узла относительно последовательности а операций ОБЪЕДИНИТЬ и НАЙТИ следующим образом: Ь Удалить из о операции НАЙТИ, 2. Выполнить получившуюся последовательность о' операций ОБЪЕДИНИТЬ. 3. Ранг узла о — это его высота в получившемся лесу. Докажем некоторые важные свойства ранга узла. ') Таким образом, «единица временна здесь занимает некоторое постоянное число шагов на РАМ. Так как мы пренебрегаем постоянными множителями, то результаты о порядке величины можно также выражать через «единицы временны гл.
с стьткттеы длнных для злдкч с множвствлми Лемма 4.2. Суиуствует не более п~2' узлов ранга г. Доказательство. По лемме 4.1 каждый узел ранга г имеет по крайней мере 2' потомков в лесу, построенном при выполнении о'. Так как множества потомков любых двух различных узлов одинаковой высоты в лесу не пересекаются, а общее число непересекающихся множеств, содержащих не менее 2' узлов, не превосходит п/2', то узлов ранга г не может быть больше и/2'.
П Следствие. Ранг любого узла не превосходит !од и. Лемма 4.3. Если в какой-то момент выполнения последовательности о узел ш оказался подлинным потомком узла о, то его ранг меныие ранга узла о. Д о к а з а тел ь с т в о. Если в какой-то момент выполнения последовательности и узел ш стал потомком узла о, то и будет по. томкам узла о и в лесу, построенном при выполнении о'.
Поэтому высота узла ш должна быть меньше высоты узла о, так что ранг узла ш меньше ранга узла и. П Разобьем ранги на группы. Отнесем ранг г к группе 0(г). Например, ранги О и 1 находятся в группе О, ранг 2 — в группе 1, ранги 3 и 4 — в группе 2, ранги от 5 до 16 — в группе 3. Для п~! наибольший возможный ранг, т. е. ! !од п ), попадает в группу О( 1оя и й'К0(п) — 1. сследуем сложность выполнения последовательности о из сп операций ОБЪЕДИНИТЬ и НАЙТИ. Так как каждую операцию ОБЪЕДИНИТЬ можно выполнить за единицу времени, то все операции ОБЪЕДИНИТЬ из о можно выполнить за время 0(п). Для того чтобы оценить сложность выполнения всех операций НАЙТИ, применим один важный "бухгалтерский" трюк.
За каждое выполнение операции НАЙТИ наложим штраф как на само выполнение, так и на некоторые перемещаемые узлы. Искомая общая сложность будет равна сумме всех штрафов, налагаемых на выполнение операций НАЙТИ и на перемещаемые узлы. Штрафы за выполнение операции НАЙТИ(!) налагаются следующим образом. Пусть о — узел на пути из узла, представляющего С в корень дерева, содержащего С !.
Если о — корень или ОТЕЦ!о! имеет ранг, который принадлежит не той же группе, что н ранг узла о, то выполнение штрафуется на одну единицу времени. 2. Если ранги узла о и его отца принадлежат одной группе, то на узел о налагается штраф в одну единицу времени. По лемме 4.3 ранг узлов по мере прохождения вверх по пути ьюнотонно возрастает. А так как различных групп рангов не больше 0(в), то по правилу 1 никакое выполнение операции НАЙТИ не еа дивзовидныв ститкттры для здддчи овъвдинить — нанти штрафуется более чем на С(п) единиц времени.
Если применяется правило 2, то узел о будет перемещен и сделан сыном узла с ббльшим рангом, чем его предыдущий отец. Если узел о принадлежит группе у О, то он может перемещаться и штрафоваться не более Р(а)— — Р (д' — 1) раз, прежде чем приобретет отца из группы с более высоким рангом. Если ранг узла принадлежит группе О, то он может перемещаться не более одного раза, прежде чем приобретет отца из более высокой группы. С этого момента перемещение узла о будет штрафоваться по правилу ! сложностью выполнения операции НАЙТИ. Чтобы получить верхнюю границу штрафов, налагаемых на узлы, умножим наибольший штраф, который можно наложить на узел с рангом из данной группы, на число узлов в этой группе и просуммируем по всем группам рангов. Пусть А!(у) — число узлов, ранг которых принадлежит группе у~О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
