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