Главная Промышленная автоматика.

4.6. ПРОСТОЙ АЛГОРИТМ для НАХОЖДЕНИЯ ОБЪЕДИНЕНИЯ

Пример 4.6. Пусть п=8 и у нас есть набор из трех множеств {1, 3, 5, 7}, {2, 4, 8} и {6} с внешними именами 1, 2 и 3 соответственно. Структуры данных для этих трех множеств показаны на рис. 4.13, где 2,3 и 1 - внутренние имена для 1,2 и 3 соответственно. □

Операция НАЙТИ (i) выполняется, как и раньше, обращением к R[i] для установления внутреннего имени множества, содержащего элемент г в данный момент. Затем ВНЕШ ИМЯ1/?[г]] дает настоящее имя множества, которому принадлежит /.

Операцию объединения вида ОБЪЕДИНИТЬ(/, /, К) выполняем следующим образом. (Номера строк относятся к рис. 4.14.)

1. Определяем внутренние имена для множеств / и J (строки 1,2).

2. Сравниваем относительные размеры множеств I и J, справляясь в массиве РАЗМЕР (строки 3, 4).

3. Проходим список элементов меньшего множества и изменяем соответствующие компоненты в массиве R на внутреннее имя большего множества (строки 5-9).

4. Вливаем меньшее множество в большее, добавляя список элементов меньшего множества к началу списка для большего множества (строки 10-12).

5. Присваиваем полученному множеству внешнее имя К (строки 13, 14).

Вливая меньшее множество в большее, мы делаем время выполнения операции ОБЪЕДИНИТЬ пропорциональным мощности меньшего множества. Все детали приведены в процедуре на рис.4.14.

Пример 4.7. После выполнения операции ОБЪЕДИНИТЬ (1,2,4) структура данных рис. 4.13 превратится в структуру данных, изображенную на рис. 4.15. □

Теорема 4.3. С помощью алгоритма рис. 4.14 можно выполнить /г-1 (максимально возможное число) операций ОБЪЕДИНИТЬ за О {п log п) ишгов.

Доказательство. За каждое выполнение операции ОБЪЕДИНИТЬ будем налагать на перемещаемые элементы одинаковые штрафы, в сумме равные сложности этого выполнения. Так как сложность пропорциональна числу перемещаемых элементов, то величина штрафа, налагаемого на один элемент, будет всегда одна и та же. Основное здесь - это заметить, что всякий раз, когда элемент перемещается из списка, он оказывается в списке, по крайней мере в два раза длиннее прежнего. Поэтому никакой элемент нельзя переместить более чем log п раз и, значит, суммарный штраф, налагаемый на один элемент, составляет О (log п).



R следующий

СЛИСОК

РЛЗМЕР

ВНЕШ ИМЯ

2 3 4

Множества (с виешииш именами)

3 = {6}

4 = {1,2, 3,4, 5, 7,8}

ВНЭТР ИМЯ

1 2 3 4

Рис. 4.15. Структура данных после выполнения операции ОБЪЕДИНИТЬ.

Общая сложность получается суммированием штрафов, наложенных на отдельные элементы. Таким образом, общая сложность есть О (п log я). □

Из теоремы 4.3 вытекает, что если выполняется т операций НАЙТИ и до п-1 операций ОБЪЕДИНИТЬ, то тратится время О (МАХ (т, п log ft)). Если m имеет порядок п log ft или больше, то этот алгоритм действительно оптимален с точностью до постоянного множителя. Однако во многих ситуациях т есть О (ft), а в таком случае, как мы увидим в следующем разделе, можно добиться лучшего времени, нежели О (МАХ (лг, ft log ft)).

4.7. ДРЕВОВИДНЫЕ СТРУКТУРЫ ДЛЯ ЗАДАЧИ ОБЪЕДИНИТЬ - НАЙТИ

В предыдущем разделе мы познакомились со структурой данных для.задачи ОБЪЕДИНИТЬ - НАЙТИ, позволяющей выполнить л-1 операций ОБЪЕДИНИТЬ и О (ft log ft) операций НАЙТИ за время О (ft log ft). В данном разделе будет описана структура данных, которая состоит из деревьев, образующих лес, и предназначена для представления набора множеств. Эта структура данных позволит выполнить О (ft) операций ОБЪЕДИНИТЬ и НАЙТИ за почти линейное время.



Однако ее можно уменьшить, если проводить балансировку деревьев. Для этого можно в каждом дереве считать число узлов и, сливая два множества, всегда присоединять меньшее дерево к корню большего. Этот способ аналогичен вливанию меньшего множества в большее, которое мы применяли в предыдущем разделе.

Лемма 4.1. Если при выполнении каждой операции ОБЪЕДИНИТЬ корень дерева с меньшим числом узлов (при равенстве узлов берется любое дерево) преобразуется в сына корня дерева с большим числом узлов, то высота дерева в лесу может достичь значения h, только если оно имеет не менее 2 узлов.

Доказательство. Доказательство проведем индукцией по h. Для /1=0 утверждение верно, поскольку каждое дерево имеет

Допустим, что каждое множество А представлено корневым неориентированным деревом Г, узлам которого поставлены в соответствие элементы из А. Корню этого дерева приписано имя самого множества. Операцию ОБЪЕДИНИТЬ (Л, В, С) можно выполнить, преобразуя корень дерева в сына корня дерева и заменяя имя в корне дерева Тд на С. Операцию НАЙТИ (J) можно выполнить, определяя положение узла, представляющего элемент i в некотором дереве Т из леса, и проходя путь из этого узла в корень дерева Т, где помещено имя множества, содержащего i.

В такой схеме сложность слияния двух деревьев равна постоянной. Однако сложность выполнения операции НАЙТИ (г) имеет порядок длины пути из узла i в корень. Эта длина может быть п-1. Поэтому сложность выполнения п-1 операций ОБЪЕДИНИТЬ, за которыми идут п операций НАЙТИ, может достигать 0(п). Например, вычислим сложность выполнения последовательности операций

ОБЪЕДИНИТЬ (1, 2, 2) ОБЪЕДИНИТЬ (2, 3, 3)

ОБЪЕДИНИТЬ(/г -1, п, п)

НАЙТИ(1)

НАЙТИ(2)

НАЙТИ{7г)

Выполнение п-1 операций ОБЪЕДИНИТЬ приводит к дереву, изображенному на рис. 4.16. Сложность выполнения п операций НАЙТИ пропорциональна





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 [46] 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0022