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

Пусть k=D{c-1, 2+!, h+\). По предположению индукции для с число k существует. Все узлы высоты h+l в T(k) имеют по 2+ сыновей каждый, причем все сыновья принадлежат Я. Если удалить из T{k) всех подлинных потомков узлов, входящих в Н, то тем самым каждое поддерево с корнями на высоте h+l заменится деревом высоты 1 с 2+ листьями. По определению D число k=D (с-1, 2+, h+l) достаточно велико, так что операции ЧН длины с-1 можно выполнить на всех листьях, т. е. элементах множества Я.

Теперь, чтобы завершить индукцию по с, осталось сделать шаг индукции по /. В частности, покажем, что для / > 1

D(c, /, /iXD(c-1, 2(-1-)(1+о(.,;-1,й))/2 h)). (4.5)

Чтобы доказать неравенство (4.5), положим k=D{c, I-I, К) и обозначим через k его правую часть. Нам надо найти способ заменить каждый узел высоты h в T{k) деревом с / листьями, а затем на каждом листе выполнить операцию ЧН длины с. Начнем с выполнения операций ЧН на /-1 листьях каждого подставляемого дерева. По предположению индукции по I это сделать можно.

Выполнив ЧН на /-1 листьях, находим, что /-й лист каждого подставляемого дерева теперь имеет отца, отличного от отца /-го листа любого другого подставляемого дерева. Множество таких отцов обозначим через F. Если мы смогли выполнить операции ЧН длины с-1 на этих отцах, то можем вьшолнить ЧН длины с на листьях. Пусть 5 - поддерево с корнем высоты k в T{k). Легко проверить, что 5 содержит 2*(*+i)/2 листьев в T{k). Поэтому после выполнения операций ЧН число узлов в 5, которые также принадлежат F, не превосходит 2*(*+)/2. Множество, оставшееся от 5, можно, следовательно, рассматривать как произвольное дерево с 2*(*+)/2 листьями, которые принадлежат F. По предположению индукции для с и / неравенство (4.5) справедливо. □

Теорема 4.5. Временная сложность алгоритма 4.3 больше сп для любой постоянной с.

Доказательство. Пусть с - такая постоянная, что алгоритм 4.3 выполнит любую последовательность из п-1 операций ОБЪЕДИНИТЬ и п операций НАЙТИ не более чем за сп единиц времени. Выберем с04с и вычислим k=D (d, 1, 1). Построим T(k) с помощью последовательности операций ОБЪЕДИНИТЬ. Так как можно выполнить ЧН длины d на каждом листе вложенного дерева T{k), листья которого занимают более четверти узлов дерева T(k), то эта последовательность операций ОБЪЕДИНИТЬ и ЧН потратит более сп единиц времени; получили противоречие. □

6 А. Ахо, Дж. Хопкрофт, Дж. Ульман 161



4.8. ПРИЛОЖЕНИЯ И ОБОБЩЕНИЯ АЛГОРИТМА ОБЪЕДИНИТЬ - НАЙТИ

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

Приложение 1. Ml N-задача в свободном режиме

Даны два типа операций: ВСТАВИТЬ(г) и H3BJIE4b MIN. Начнем с множества 5, вначале пустого. Каждый раз, когда встречается операция ВСТАВИТЬ(0, целое число i помещается в S. Каждый раз, когда выполняется операция ИЗВЛЕЧЬ МШ, разыскивается и удаляется наименьший элемент в 5.

Пусть а - такая последовательность операций ВСТАВИТЬ и ИЗВЛЕЧЬ МШ, что для каждого /, 1<г<л, операция ВСТА-BHTb(t) встречается не более одного раза. По данной последовательности а надо найти последовательность целых чисел, удаляемых операцией ИЗВЛЕЧЬ МШ. Задача решается в свободном режиме, поскольку предполагается, что вся последовательность о известна до того, как надо вычислить даже первый элемент выходной последовательности.

МШ-задачу в свободном режиме можно решить следующим методом. Пусть k - число операций ИЗВЛЕЧЬ МШ в а. Можно записать а в виде аЕаЕозЕ. . .аЕа, где каждая подпоследовательность Oj, 1/-fl, состоит только из операций ВСТАВИТЬ,

for i -!- 1 until п do begin / -НАЙТИ(0; if /</г then begin

print i "удаляется /-й операцией ИЗВЛЕЧЬ..МШ"; ОБЪЕДИНИТЬ!/, СЛЕД[/], СЛЕД[/]); СЛЕД[ПРЕД[/]] СЛЕД[/]; ПРЕД[СЛЕД[/]]ПРЕД[/] end

Рис. 4.23. Программа для решения МШ-задачи в свободном режиме.



а Е обозначает операцию ИЗВЛЕЧЬ МШ. Промоделируем ст с помощью алгоритма 4.3. Начальная последовательность множеств для работы алгоритма объединения строится так: если в последовательности Cj встречается операция BCTABHTb(i), то считаем, что множество с именем /, содержит элемент i. Для

того чтобы для тех значений /, для которых существует множество с именем /, образовать дважды связанный упорядоченный список, пользуемся двумя массивами ПРЕД и СЛЕД. Вначале ПРЕД[/]= =/-1 для и СЛЕД[/]=/+1 для 0/. Затем выпол-

няется программа, приведенная на рис. 4.23.

Легко видеть, что время выполнения этой программы ограничено временем работы алгоритма объединения множеств. Следовательно, MIN-задача в свободном режиме имеет временную сложность 0{nG{n)).

Пример 4.8. Рассмотрим последовательность операций а= =4 3 £ 2 £ 1 £, где / означает ВСТАВИТЬ(/), а £ -ИЗВЛЕЧЬ. MIN. Тогда 01=4 3, 0=2, (Тз = 1 и - пустая последовательность. Начальная структура данных представляет собой последовательность множеств

1={3, 4}, 2 = {2}, 3={1}, 4 = 0.

При первом выполнении for-цикла выясняется, что НАЙТИ(1)= =3. Следовательно, ответом на третью операцию в ст ИЗВЛЕЧЬ. MIN будет 1. Последовательность множеств превращается в

1={3,4}, 2 = {2}, 4 = {1}.

В этот момент СЛЕД[2]=4 и ПРЕД[4]=2, поскольку множества с именами 3 и 4 были слиты в одно множество с именем 4.

При следующем прохождении с t =2 выясняется, что НАЙТИ(2)= =2. Таким образом, ответом на вторую операцию ИЗВЛЕЧЬ.МШ будет 2. Множество с именем 2 сливается со следующим множеством (с именем 4) и получается последовательность множеств

1={3,4}, 4 = {1,2}.

Два последних прохождения устанавливают, что ответ на первую операцию ИЗВЛЕЧЬ.МШ есть 3 и что 4 никогда не извлекается. □

Рассмотрим другое приложение - задачу определения глубины. В частности, она возникает при "приравнивании" идентификаторов в программе на языке ассемблера. Во многих языках ассемблера есть операторы, описывающие, что два идентификатора представляют одну и ту же ячейку памяти. Как только ассемблер встречает оператор, приравнивающий два идентификатора аир, он должен найти два множества Sa и Sp идентификаторов, экви-

6* 163





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.0039