нами) утверждением о том, что стоимость т операций с непересекающимися множествами, включающих га операций Make-Set, есть @(та(т, га)). В самом деле, эта оценка говорит, что стоимость в расчёте на одну операцию есть а(т, га). Если га фиксировано, а т растёт, то из-за сжатия путей деревья с каждым шагом всё более «упрощаются» (всё больше становится вершин, напрямую связанных с корнем), так что стоимость операции падает.

Во всех практических приложениях можно считать, что а(т, га) 4. В самом деле, поскольку функция Аккермана является возрастающей по каждому переменному и т га, имеем

А(4, [т/п\) > А(4,1) = А(3, 2) = 22** 17,

что много больше числа атомов в наблюдаемой части Вселенной (к, 1080). Поэтому для всех встречающихся на практике значений га имеем А(4, то/га ) lg га и а(т,п) 4.

Мы не доказываем оценки, связанной с функцией Аккермана, а ограничиваемся более слабой оценкой 0(mlg*ra). Вспомним определение функции lg* (с. ??). По определению, lg* 1 = 0 и

lg* га = min { г : lg lg ... lg га 1 )

4-„-

г раз

для га > 1. Неравенство в определении функции lg* можно перепи-]

сать так: га 22 > j (j - число двоек в формуле).

Оценка 0(mlg* га), которую мы докажем ниже, слабее, чем сформулированная без доказательства оценка 0(та(т, га)), но с практической точки зрения разница невелика. В самом деле, lg* 22 = lg* 265536 = 5, так что во всех практических вопросах можно считать, что lg* га 5 - вряд ли нам встретится множество, в котором более 265536 элементов.

Свойства рангов

Чтобы доказать оценку 0(mlg*ra) для времени работы с системой непересекающихся множеств, нам понадобятся некоторые свойства рангов. Напомним, что мы работаем с системой непересекающихся множеств, реализованной с помощью леса, с объединением по рангам и сжатием путей (см. разд. 22.3); через т обозначено суммарное число операций Make-Set, Find-Set и Union, а через га - число операций Make-Set.

Лемма 22.2

Для всякой вершины ж, кроме корня, rank[x] < гага/г[р[ж]] (напомним, что для корня р[х] = ж). При создании множества {ж} имеем rank[x] = 0, далее rank[x] может только возрастать и перестаёт меняться, когда ж перестаёт быть корнем в своём дереве.

Доказательство. Всё это непосредственно следует из описания процедур Make-Set, Union и Find-Set в разделе 22.3. Подробности мы оставляем читателю (упр. 22.4-1).

Пусть ж - вершина одного из наших деревьев. Число вершин в поддереве с корнем х (включая саму ж) назовем ее размером (size) и обозначим size(a:).

Лемма 22.3

Если х - корень одного из деревьев, то size (ж) 2rankx\ Доказательство.

Достаточно проверить, что каждая из операций Make-Set, Find-Set и Link сохраняет истинность утверждения «size(x) 2jrank[x] дЛЯ всех КОрНей ж». Операция Find-Set не меняет ни размеров корней, ни рангов каких бы то ни было вершин. Операция Маке-8ет(ж) также не нарушает утверждения леммы: не меняя рангов и размеров уже существующих деревьев, она создаёт новое дерево с единственной вершиной, для которой неравенство очевидным образом выполнено.

Рассмотрим операцию Link(x,j/) (не ограничивая общности, можно считать, что rank[x] rank[y]). В результате этой операции ранг или размер может измениться только у вершины у. Если rank[x] < rank[y], то размер у увеличивается, а ранг не меняется, так что неравенство size(y) 2гапку\ остаётся верным. Если же гапк[х] = гапк[у], то, обозначая через size[y] и гапк[у] размер и ранг у после операции Link, имеем size[y] = size[x] + size[y] и rank[y] = rank[y] + 1. Отсюда

size[y] = size[x] + size[y] 2rank + 2rank = 2rank+1 = 2rank. Лемма 22.4

Число вершин ранга г не превосходит га/2г (для любого целого г 0).

Доказательство.

Зафиксируем число г. Всякий раз, когда какой-либо вершине у присваивается ранг г (в строке 2 процедуры Make-Set или в строке 5 процедуры Link), будем привешивать метку ко всем вершинам поддерева с вершиной у. Поскольку вершина у в этот момент является корнем одного из деревьев, лемма 22.3 показывает, что число помечаемых вершин не меньше 2Г. Наши процедуры устроены так, что каждая вершина будет помечена не более одного раза. Стало быть,

га (число меток) 2Г • (число вершин ранга г),

откуда всё и следует. Следствие 22.5

Ранг любой вершины не превосходит [lg raj. Доказательство.

См. лемму 22.3 или 22.4

Доказательство оценки для времени работы

При доказательстве оценки нам будет удобнее работать с операцией Link, а не Union. Пусть дана последовательность Si, состоящая из mi операций Make-Set, Find-Set и Union. Заменим каждую операцию Union на две операции Find-Set и одну операцию Link; получится последовательность 5*2 из т2 операций Make-Set, Find-Set и Link.

Лемма 22.6

Если стоимость выполнения последовательности 5*2 в худшем случае есть 0(ra2lg* п), то стоимость выполнения последовательности 5*1 в худшем случае есть О (mi lg* п), где п - число операций Make-Set.

Доказательство.

Немедленно следует из очевидного неравенства mi т2 3rai. Теорема 22.7

Предположим, что над системой непересекающихся множеств (первоначально пустой) произвели т операций Make-Set, Find-Set и Link, из которых п операций были операциями Make-Set. Тогда при использовании реализации с помощью леса со сжатием путей и объединением по рангам общая стоимость этой последовательности операций есть 0(m\g* п).

Доказательство.

Стоимость каждой из операций Make-Set и Link есть, очевидно, 0(1), а их суммарная стоимость есть тем самым О (га). Займемся операциями Find-Set. Очевидно, стоимость операции Find-Set) пропорциональна длине пути поиска от ж к корню (до сжатия). Стало быть, нам надо оценить суммарную длину путей поиска, возникавших в процессе выполнения всех операций Find-Set и доказать, что она есть 0(ralg* п).

В процессе выполнения каждой из операций Find-Set мы двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Заметим, что на каждом шаге ранг вершины строго возрастает: если и - вершина, встретившаяся на пути поиска, a v - следующая вершина, то есть v = р[и], то rank[v] > гапк[и]. Вершина и может неоднократно встречаться в путях поиска при выполнении рассматриваемой в теореме последовательности операций. При этом за ней могут (и скорее всего будут) идти разные вершины: если в некоторый момент за и следовала вершина v, которая не была корневой, то после сжатия путей за и будет следовать уже не v, а корень дерева (на момент первого поиска), то есть вершина большего ранга, чем v. (Это простое наблюдение играет к дальнейшем ключевую роль.)

Наблюдая за ростом ранга при переходе от вершины к её родителю, мы отдельно оценить количество шагов, при которых ранг сильно растёт, и количество шагов, когда он растёт не сильно. Вы-