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

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

65536

265536

Рис. 4.20. Несколько значений функции F.

Пусть

f (i) = 2(-) для

f >0.

Функция F растет очень быстро, как видно из таблицы на рис. 4.20. Функция G{n) определяется как наименьшее число k, для которого Р{Щп. Функция G растет очень медленно. Действительно, G (rt)5 для всех "практических" значений п, а именно для всех /г<2«5бзв.

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

Определение. Удобно определить ранг узла относительно последовательности о операций ОБЪЕДИНИТЬ и НАЙТИ следующим образом:

1. Удалить из о операции НАЙТИ.

2. Выполнить получившуюся последовательность а операций ОБЪЕДИНИТЬ.

3. Ранг узла v - это его высота в получившемся лесу.

Докажем некоторые важные свойства ранга узла.

Таким образом, «единица времени» здесь занимает некоторое постоянное число шагов на РАМ. Так как мы пренебрегаем постоянными множителями, то результаты о порядке величины можно также выражать через «единицы времени».



Лемма 4.2. Существует не более п/2 узлов ранга г.

Доказательство. По лемме 4.1 каждый узел ранга г имеет по крайней мере 2 потомков в лесу, построенном при выполнении а. Так как множества потомков любых двух различных узлов одинаковой высоты в лесу не пересекаются, а общее число непересекающихся множеств, содержащих не менее 2 узлов, не превосходит п/2, то узлов ранга г не может быть больше п/2. □

Следствие. Ранг любого узла не превосходит log п.

Лемма 4.3. Если в какой-то момент выполнения последовательности а узел W оказался подлинным потомком узла v, то его ранг меньше ранга узла v.

Доказательство. Если в какой-то момент выполнения последовательности а узел w стал потомком узла v, то w будет потомком узла у и в лесу, построенном при выполнении о. Поэтому высота узла W должна быть меньше высоты узла и, так что ранг узла w меньше ранга узла v. □

Разобьем ранги на группы. Отнесем ранг г к группе G(r). Например, ранги О и 1 находятся в группе О, ранг 2 - в группе 1, ранги 3 и 4 - в группе 2, ранги от 5 до 16 - в группе 3. Для /г>»1 наибольший возможный ранг, т. е. L og J > попадает в группу G(LlogftJKG(n)-l.

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

Штрафы за выполнение операции НАЙТИ (t) налагаются следующим образом. Пусть и - узел на пути из узла, представляющего I, в корень дерева, содержащего i.

1. Если V - корень или ОТЕЦ (и) имеет ранг, который принадлежит не той же группе, что и ранг узла v, то выполнение штрафуется на одну единицу времени.

2. Если ранги узла v и его отца принадлежат одной группе, то на узел v налагается штраф в одну единицу времени.

По лемме 4.3 ранг узлов по мере прохождения вверх по пути монотонно возрастает. А так как различных групп рангов не больше G(n, то по правилу 1 никакое выполнение операции НАЙТИ не



.+1+1+...

) По поводу сложности задачи, рассматриваемой в данном разделе, см. работу Тарьяна [1977].- Прим. перее.

штрафуется более чем на G{n) единиц времени. Если применяется правило 2, то узел v будет перемещен и сделан сыном узла с большим рангом, чем его предыдущий отец. Если узел v принадлежит группе g>0, то он может перемещаться и штрафоваться не более F (g) - -F {g-1) раз, прежде чем приобретет отца из группы с более высоким рангом. Если ранг узла принадлежит группе О, то он может перемещаться не более одного раза, прежде чем приобретет отца из более высокой группы. С этого момента перемещение узла v будет штрафоваться по правилу 1 сложностью выполнения операции НАЙТИ.

Чтобы получить верхнюю границу штрафов, налагаемых на узлы, умножим наибольший штраф, который можно наложить на узел с рангом из данной группы, на число узлов в этой группе и просуммируем по всем группам рангов. Пусть N (g) - число узлов, ранг которых принадлежит группе g>0. Тогда по лемме 4.2 (g)

{gX X rt/2-(n/2<-x)+i)

/=F(g-l) + l

<7г/2г-1)7г/ (g).

Наибольший штраф на узел с рангом из группы g>0 не превосходит F{g) - F(g-1). Поэтому наибольший штраф для узлов, ранги которых принадлежат группе g, ограничен числом п. Это утверждение, очевидно, верно и для g=0. Поскольку групп рангов не больше 0(/г), то суммарный штраф, налагаемый на все узлы, не превосходит nG{n). Следовательно, общее время, требуемое для выполнения СП операций НАЙТИ, состоит из времени, не большего cnG{n), на которое оштрафовано выполнение этих операций, и времени, не большего nG{n), на которое оштрафованы узлы. Таким образом, мы доказали следующую теорему.

Теорема 4.4. Пусть с - произвольная постоянная. Найдется другая постоянная с, зависящая от с и такая, что алгоритм 4.3 выполнит последовательность а из сп операций ОБЪЕДИНИТЬ и НАЙТИ на п элежнтах не более чем за cnG{n) единиц времени.

Доказательство. Рассуждать, как выше. □

В качестве упражнения предлагаем показать, что если в последовательности а наряду с операциями ОБЪЕДИНИТЬ и НАЙТИ допускаются основные операции ВСТАВИТЬ и УДАЛИТЬ, то ее все равно можно выполнить за время 0{nG{n)).

Неизвестно, точна ли оценка времени работы алгоритма 4.3, даваемая теоремой 4.4 ). Однако в оставшейся части раздела мы докажем, поскольку это теоретически интересно, что время работы ал-





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