Этот тип данных применяется в таких задачах, как поиск минимального остовного дерева для заданного взвешенного неориентированного графа, построение компонент связности графа, минимизация конечного автомата, и многих других, требующих динамического поддержания некоторого отношения эквивалентности. Примеры таких задач будут рассмотрены ниже.
Как правило, в таких задачах вычисления начинаются с пустой коллекции подмножеств ( $$k = 0$$ ). Затем по мере вычислений формируются новые подмножества, включаемые в коллекцию. Формирование новых подмножеств происходит либо путем создания одноэлементного подмножества, либо путем объединения уже существующих в коллекции подмножеств. Для осуществления таких действий используются имена включенных в коллекцию подмножеств. В качестве имени подмножества будем использовать один из его элементов (главный элемент), выбираемый по определенному правилу. Поскольку в коллекции всегда будут находиться попарно непересекающиеся подмножества множества $$U$$, такое имя будет однозначно определять требуемое подмножество.
СОЗДАТЬ ( $$x$$ ). Эта операция предназначена для введения в коллекцию нового подмножества, состоящего из одного элемента $$x$$, при этом предполагается, что $$x$$ не входит ни в одно из подмножеств коллекции, созданной к моменту выполнения этой операции. Элемент $$x$$ указывается в качестве параметра. Именем созданного подмножества будет считаться сам элемент $$x$$.
ОБЪЕДИНИТЬ ( $$x,y$$ ). С помощью этой операции можно объединить два подмножества коллекции, имеющие, соответственно, имена $$x$$ и $$y$$, в одно новое подмножество, при этом оба объединяемые подмножества удаляются из коллекции, а вновь построенное подмножество получает некоторое имя. Во всех рассматриваемых нами случаях именем нового полученного в результате этой операции подмножества будет одно из имен $$x$$ или $$y$$. Имена объединяемых подмножеств указываются в качестве параметров.
НАЙТИ ( $$x, y$$ ). Эта операция позволяет определить имя $$y$$ того подмножества коллекции, которому принадлежит элемент $$x$$. Если элемент $$x$$ до выполнения операции не входил ни в одно из подмножеств коллекции, то в качестве $$y$$ берется 0.
Последовательность $$\sigma$$, составленную из операций типа
СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ, назовем
Мы рассмотрим несколько способов представления коллекции разделенных множеств в памяти компьютера и алгоритмической реализации перечисленных операций. А именно, будут описаны представления
Последний из перечисленных способов является наиболее эффективным по времени выполнения произвольных корректных последовательностей операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ. Строго говоря, во всех перечисленных случаях будут использоваться массивы, но интерпретации их содержимого будут различными. Каждый раз при описании очередной реализации мы будем обсуждать оценки трудоемкости рассматриваемых операций.
Пример 1. Рассмотрим задачу выделения компонент связности неориентированного графа. Напомним, что компонентой связности называется максимальное по включению подмножество вершин графа такое, что любые две его вершины связаны цепью. Полагаем, что вершины графа пронумерованы числами $$1, 2 \dts n$$ и каждое ребро представлено парой ( $$i, j$$ ) номеров вершин. Предполагаем также, что множество ребер не пусто.
Алгоритм выделения компонент связности неориентированного графа
$$\formula{ 1. \ \t{Создать коллекцию из } n\ \t{синглетонов множества}\ \{1, 2\dts n\};\\ 2. \ \t{Прочитать очередное ребро } (i, j);\\ 3. \ \t{Найти имя } a\ \t{подмножества коллекции, содержащего элемент } i;\\ 4. \ \t{Найти имя } b\ \t{подмножества коллекции, содержащего элемент}\ j;\\ 5. \ \t{Если}\ a \ne b,\ \t{то объединить подмножества с именами } a\ \t{и } b; \\ 6. \ \t{Если есть еще непрочитанные ребра, перейти к п.}\,2,\\ \mbox{}\q\, \t{в противном случае закончить вычисления.} }$$Очевидно, построенные подмножества коллекции будут представлять искомые
компоненты связности. Используя названия основных операций над коллекцией
Пример 2. Рассмотрим неориентированный связный граф без петель, ребрам которого приписаны в качестве весов положительные вещественные числа. Требуется построить остовное дерево, накрывающее все вершины графа и имеющее минимальный суммарный вес входящих в него ребер. Итак, пусть заданный граф $$G$$ имеет множество $$V$$ вершин, пронумерованных числами $$1, 2\dts n$$, и множество $$E$$ ребер. Каждому ребру $$e$$ из множества $$E$$ поставлена в соответствие пара $$(N(e), K(e))$$ его концевых вершин и число $$C(e)$$ — его вес. Для решения этой задачи были предложены различные алгоритмы. Мы рассмотрим алгоритм, который разработал Крускал.
Алгоритм Крускала
$$\formula{ 1. \ \t{Создать коллекцию из}\ n\ \t{одноэлементных подмножеств}\\ \mbox{}\q\, \t{множества}\ \{1, 2\dts n\};\\ 2. \ \t{Создать пустое множество}\ T;\\ 3. \ \t{В множестве}\ E\ \t{найти ребро}\ e\ \t{с минимальным весом и удалить его}\\ \mbox{}\q\, \t{из множества}\ E;\\ 4. \ \t{Найти имя}\ a\ \t{подмножества коллекции, содержащего элемент}\ N(e);\\ 5. \ \t{Найти имя}\ b\ \t{подмножества коллекции, содержащего элемент}\ K(e);\\ 6. \ \t{Если}\ a \ne b, \t{то объединить подмножества с именами}\ a\ \t{и}\ b,\ \t{а ребро}\ e\\ \mbox{}\q\, \t{добавить к множеству}\ T;\\ 7. \ \t{Если множество}\ E\ \t{не пусто и}\ |T| < n - 1,\ \t{перейти к п.}\,3,\\ \mbox{}\q\, \t{в противном случае закончить вычисления.} }$$
Заметим, что в процессе работы алгоритма в множестве $$T$$ будут находиться ребра, составляющие ациклический подграф исходного графа, являющийся лесом, состоящим из некоторого числа деревьев. Отсутствие циклов гарантируется проверкой "Если $$a \ne b$$ " в пункте 6 описанного алгоритма. Фактически при $$a \ne b$$ происходит объединение двух поддеревьев в одно дерево с помощью ребра $$e$$, найденного на шаге 3.
Если исходный граф связен, как сказано в постановке задачи, то построенное с помощью такого алгоритма множество $$T$$ будет, очевидно, представлять дерево, накрывающее все вершины исходного графа. Доказательство того, что суммарный вес входящих в него ребер будет минимальным, можно найти в разделе "Графы".
В алгоритме естественным образом используется структура разделенных множеств. Обратим внимание на операцию поиска в множестве $$E$$ ребра $$e$$ с минимальным весом. Эффективность этой операции во многом зависит от выбора структуры данных для хранения множества $$E$$. Приемы эффективного выполнения этой операции рассмотрены в разделе "Приоритетные очереди".
Пусть $$U = \{1, 2\dts n\}$$ — множество, из элементов которого будет строиться коллекция разделенных подмножеств. Одним из очевидных способов представления коллекции является представление ее с помощью массива. При таком способе для каждого элемента $$i$$ в соответствующей ( $$i$$ -й) ячейке массива помещаем имя (канонический элемент) того подмножества, которому принадлежит элемент $$i$$. Если элемент $$i$$ не принадлежит ни одному из подмножеств коллекции, то в $$i$$ -ю ячейку записываем 0.
Обозначим через $$f$$ массив длины $$n$$, с помощью которого будем представлять коллекцию. Пустая коллекция представляется массивом, заполненным нулями.
Операция СОЗДАТЬ ( $$x$$ ) осуществляется записью элемента $$x$$ в ячейку с номером $$x$$. Время выполнения операции — $$O(1)$$.
Операция ОБЪЕДИНИТЬ ( $$x,y$$ ) осуществляется следующим образом. Просматриваются элементы массива $$f$$, и в те ячейки, в которых было записано имя $$x$$, заносится новое имя — $$y$$. Следовательно, именем вновь образованного подмножества будет $$y$$, а $$x$$ перестанет быть именем какого-либо подмножества. Очевидно, время выполнения этой операции — $$O(n)$$.
Операция НАЙТИ ( $$x, y$$ ) выдает в качестве $$y$$ содержимое элемента с номером $$x$$ в массиве $$f$$. Время выполнения операции — $$O(1)$$.
При такой реализации
Пусть, по-прежнему, $$U = \{1, 2\dts n\}$$ — множество, из
элементов которого будет строиться коллекция. Каждое подмножество
коллекции представляется
Фактически в памяти компьютера это дерево будем представлять массивом $$p[1\ldots n]$$ так, что $$p(x)$$ будет предком узла $$x$$, если $$x$$ не является корнем, и $$p(x) = x$$, если $$x$$ — корень. Если же $$x$$ не входит ни в одно из подмножеств коллекции, то $$p(x) = 0$$.
Рассмотрим пример. Пусть $$U = \{1, 2\dts 7\}$$ и коллекция состоит из двух подмножеств $$\{1, 2, 3, 7\}$$ и $$\{4, 6\}$$. Деревья, представляющие эти подмножества, могут быть такими, как на рис.3.1. Кружочки обозначают узлы дерева; указатели на родителей представлены при помощи стрелок. Именем одного из этих подмножеств является 3, другого — 6:
(рис 3.1) Операция СОЗДАТЬ ( $$x$$ ) назначает в качестве родителя узла $$x$$ сам узел $$x$$ с помощью присваивания $$p[x] := x$$. Таким образом, время выполнения операции есть $$O(1)$$. В результате выполнения операции СОЗДАТЬ( $$x$$ ) образуется новое одновершинное дерево с петлей в корне, изображенное на рис. 3.2.
(рис 3.2) Если к коллекции подмножеств, изображенных на рис. 3.1, применить операцию СОЗДАТЬ (5), то получим коллекцию, изображенную на рис. 3.3.
(рис 3.3) Операция ОБЪЕДИНИТЬ ( $$x, y$$ ) назначает узел $$y$$ родителем узла $$x$$ с помощью присваивания $$p[x]:= y$$. Заметим, что $$x$$ и $$y$$ должны быть до выполнения рассматриваемой операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет $$y$$, а $$x$$ перестанет быть именем какого-либо множества. Время выполнения этой операции есть $$O(1)$$.
(рис 3.4) Если применить операцию ОБЪЕДИНИТЬ $$(3, 6)$$ к коллекции, представленной на рис. 3.3, то получим коллекцию, состоящую из двух подмножеств $$\{1, 2, 3, 4, 6, 7\}$$ и $$\{5\}$$, — изображенную на рис. 3.4. Именем первого из этих подмножеств будет 6, второго — 5.
Операция НАЙТИ ( $$x,y$$ ) осуществляется продвижением по указателям на родителей от узла $$x$$ до корня дерева. В качестве $$y$$ берется этот корень. Описанные действия можно реализовать с помощью операторов
$$\formula{ \t \while\ p[x] \ne x\ \t \do\ x := p[x];\ y := x; }$$
Очевидно, что время выполнения данной операции есть $$O(h)$$, где $$h$$ — длина пути из узла $$x$$ в корень соответствующего дерева. Но заметим, что при выполнении операций СОЗДАТЬ и ОБЪЕДИНИТЬ возможно образование дерева в виде линейной цепочки из $$n$$ узлов, изображенной на рис. 3.5.
(рис 3.5) К такой цепочке может привести, например, следующая последовательность операций
СОЗДАТЬ ( $$\bs 1$$ );
СОЗДАТЬ ( $$\bs 2$$ );
$$\dots$$ $$\dots$$ $$\dots$$
СОЗДАТЬ ( $$\bs n$$ );
ОБЪЕДИНИТЬ ( $$\bs 1, \bs 2$$ );
ОБЪЕДИНИТЬ ( $$\bs 2, \bs 3$$ );
$$\dots$$ $$\dots$$ $$\dots$$
ОБЪЕДИНИТЬ ( $$\bs n-{\bs 1},{\bs n}$$ );
Как видим, $$h$$ может достигать величины $$n$$, поэтому трудоемкость операции НАЙТИ является величиной $$O(n)$$.
Худший случай применения операции НАЙТИ в данной ситуации — это НАЙТИ ( $$1,y$$ ). В этом случае необходимо сделать $$n - 1$$ переход по ссылкам на родителей, чтобы дойти от узла $$1$$ к корню дерева $$n$$, и один переход, чтобы узнать, что родитель узла $$n$$ есть сам узел $$n$$.
Если операция СОЗДАТЬ выполняется $$n$$ раз, то время выполнения
последовательности, составленной из $$m$$ операций ОБЪЕДИНИТЬ
и/или НАЙТИ, при рассматриваемой реализации
Предыдущую реализацию
Для такой реализации
Операция СОЗДАТЬ ( $$x$$ ) назначает в качестве родителя узла $$x$$ тот же самый $$x$$, а высотой узла $$x$$ считает 0. Таким образом, время выполнения данной операции есть $$O(1)$$. В результате выполнения операции СОЗДАТЬ ( $$x$$ ) образуется новое дерево, изображенное на рис. 3.6. Число, расположенное рядом с узлом, обозначает его высоту. Описанные действия реализуются с помощью операторов
$$\formula{ p[x]:= x;\ h[x]:= 0; }$$
(рис 3.6) Операция ОБЪЕДИНИТЬ ( $$x, y$$ ) назначает корень большего по высоте дерева родителем корня другого дерева. Если деревья имеют одинаковую высоту, то узел $$y$$ назначается родителем узла $$x$$, после чего значение высоты узла $$y$$ увеличивается на единицу. Заметим, что $$x$$ и $$y$$ должны быть до выполнения операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет имя того из объединяемых подмножеств, у которого корень имел большую высоту, а имя другого из объединяемых подмножеств перестанет быть именем какого-либо из подмножеств. Очевидно, время выполнения этой операции есть константа. Выполнить описанные действия можно с помощью следующей процедуры:
$$\formula{ \t{Procedure ОБЪЕДИНИТЬ (x, y)};\\ \t begin\\ \mbox{}\q if (h[x] < h[y])\ \t then\ p[x] := y\ \t else if\ (h[x] > h[y])\ \t then\ p[y] := x\ \t else\\ \mbox{}\qq \{p[x] := y;\ h[y] := h[y] + 1\}\\ \t end; }$$На рис. 3.7 и рис. 3.8 показано применение операции ОБЪЕДИНИТЬ $$(3,6)$$ к коллекции, изображенной на рис. 3.3, с учетом высот объединяемых поддеревьев. Рядом с кружочками, изображающими узлы, показаны их высоты. Так как $$h(3) = 2 > h(6) = 1$$, то родителем узла 6 становится узел 3.
Операция НАЙТИ ( $$x,y$$ ) осуществляется, как и в предыдущей реализации, продвижением по указателям на родителей от узла $$x$$ до корня дерева. В качестве $$y$$ берется найденный корень.
(рис 3.8) (рис 3.7) Очевидно, что время выполнения данной операции, как и ранее,
пропорционально длине пути из узла $$x$$ в корень соответствующего
дерева. Однако длина такого пути в данном случае может быть оценена иначе.
Для
Лемма 1. В результате выполнения любой последовательности операций из набора $$\{$$ СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ $$\}$$ над пустой коллекцией разделенных множеств для любого узла $$x$$ выполняется неравенство $$n[x]\ge 2^{h(x)}$$, где $$n[x]$$ — количество узлов в поддереве с корнем $$x, h[x]$$ — высота узла $$x$$.
Доказательство Очевидно, перед первым применением операции ОБЪЕДИНИТЬ для любого узла $$x$$ имели $$n[x] = 1$$, $$h[x] = 0$$ и, следовательно, $$n[x] \ge 2^{h(x)}$$. Операции СОЗДАТЬ и НАЙТИ не могут нарушить доказываемого неравенства, поэтому доказательство можно провести индукцией по количеству применений операции ОБЪЕДИНИТЬ.
Предположим, что перед очередным применением операции ОБЪЕДИНИТЬ ( $$x,y$$ ) доказываемое неравенство все еще остается верным, тогда если высота узла $$x$$ меньше высоты узла $$y$$, то дерево, полученное с помощью ОБЪЕДИНИТЬ ( $$x, y$$ ), имеет корень $$y$$, а высоты узлов $$x$$ и $$y$$ не изменились. Количество узлов в дереве с корнем $$x$$ не изменилось, а количество узлов в дереве с корнем $$y$$ увеличилось. Таким образом, как для узлов $$x$$, $$y$$, так и для всех остальных неравенство сохраняется. Случай, когда высота узла $$x$$ больше высоты узла $$y$$, аналогичен рассмотренному.
Если же высоты деревьев с корнями $$x$$ и $$y$$ до выполнения операции были одинаковы ( $$h[x] = h[y] = h)$$, то узел $$y$$ становится родителем узла $$x$$, высота узла $$y$$ увеличивается на 1, а высота узла $$x$$ не изменяется. Пусть после выполнения операции величины $$h[x]$$, $$h[y]$$, $$n[x]$$, $$n[y]$$ становятся равными соответственно $$h'[x]$$, $$h'[y]$$, $$n'[x]$$, $$n'[y]$$, тогда имеем $$h'[y] = h [y] + 1$$, $$h'[x] = h[x]$$, $$n'[x] = n[x]$$, $$n'[y] = n[y] + n[x]$$. По предположению индукции, имеем $$n[y] \ge 2^{h[y]}$$ и $$n[x] \ge 2^{h[x]}$$. Следовательно, после выполнения рассматриваемой операции для узлов $$x$$ и $$y$$ имеем соотношения$$\eqa*{ n'[x] = n[x] \ge 2^{h[x]} = 2^{h' [x]}\q \t{и }\\ n'[y] = n[y] + n[x] \ge 2^{h [y]} + 2^{h [x]} = 2^{h + 1} = 2^{h' [y]}. }$$ Таким образом, утверждение леммы остается верным и в этом случае.
Лемма 2. Если за время работы, начавшейся с пустой коллекции, операция СОЗДАТЬ применялась $$n$$ раз, то для любого $$h \ge 0$$ число $$k$$ узлов высоты $$h$$ удовлетворяет неравенству $$k \le n/2^h$$.
Доказательство Пусть $$x_1,x_2\dts x_k$$ — все узлы высоты $$h$$, тогда по лемме 1 при $$i \!=\! 1, 2\dts k$$ справедливы неравенства $${n[x_i] \!\ge\! 2^h}$$. Таким образом,$$\eq*{ n \ge n[x_1] + n[x_2] + ... + n[x_k] \ge k2^h, }$$ откуда и следует требуемое неравенство $$k \le n/2^h$$.
Следствие 3.
В результате выполнения любой последовательности
операций из набора $$\{$$ СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ $$\}$$ над
пустой коллекцией
Доказательство Дерево максимальной высоты образуется, очевидно, лишь тогда, когда все $$n$$ элементов объединяются в одно множество. Для такого дерева количество $$k$$ узлов максимальной высоты $$h$$ равно 1, по лемме 2 имеем $$1 = k \le n/2^h$$, откуда $$2^h \le n$$ и, следовательно, $$h \le \log n$$.
Следствие 4. Время выполнения операции НАЙТИ есть $$O(\log n)$$.
Следствие 5.
При реализации
Замечание
При реализации операции объединения подмножеств в
качестве
Предыдущий способ реализации
$$\formula{ \t begin p[x]:= x;\ r[x] := 0\ \t end; }$$
В качестве родителя узла $$x$$ берется тот же самый $$x$$, а его рангом считаем $$0$$. Таким образом, время выполнения операции есть константа.
Для анализа трудоемкости выполнения операций нам потребуются две функции. Одна из них, $$b(n)$$, является суперэкспонентой и определяется следующим образом:
$$\eq*{ b(0) = 0,\q b(n) = 2^{b(n-1)}\q \t{при } n > 0. }$$Вторая — суперлогарифм $$\log^\ast n$$, по основанию 2, определяемая соотношением
$$\eq*{ \log^\ast n = \max\{k: b(k) \le n\}. }$$Суперлогарифм является в некотором смысле обратной функцией к суперэкспоненте, $$\log^\ast (b(n)) = n$$. Значения функций $$\log^\ast n$$ и $$b(n)$$ при нескольких значениях аргументов приведены в следующих таблицах:
| $$n$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ |
| $$b(n)$$ | $$0$$ | $$1$$ | $$2$$ | $$4$$ | $$16$$ | $$65536$$ | $$2^{65536}$$ |
| $$n$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$\dots$$ | $$15$$ | $$16$$ | $$\dots$$ | $$65535$$ | $$65536$$ | $$\dots$$ | $$2^{65536}-1$$ |
| $$\log^\ast n$$ | $$0$$ | $$1$$ | $$2$$ | $$2$$ | $$3$$ | $$3$$ | $$\dots$$ | $$3$$ | $$4$$ | $$\dots$$ | $$4$$ | $$5$$ | $$\dots$$ | $$5$$ |
Ребро $$(x, p(x))$$ при текущем состоянии коллекции назовем корневым, если $$p(x)$$ — корень и $$p(x) = x$$ (петля); назовем его прикорневым, если $$p(x)$$ — корень и $$p(x) \ne x$$, в противном случае — внутренним.
Отметим следующие свойства коллекции на множестве из $$n$$ элементов. Прикорневое ребро может превратиться во внутреннее, а корневое — в прикорневое только при выполнении операции ОБЪЕДИНИТЬ.
Если при выполнении очередной операции ОБЪЕДИНИТЬ $$(x,y)$$ узел $$y$$ становится родителем узла $$x$$, то после ее выполнения справедливо неравенство $$r(y) > r(x)$$.
При выполнении операции НАЙТИ
Если перед выполнением операции НАЙТИ узел $$x$$ был родителем узла $$y$$, а после выполнения этой операции родителем узла $$y$$ стал узел $$x' \ne x$$, то выполняется неравенство $$r(x) < r(x')$$. Следовательно, даже после изменения леса в результате выполнения операции НАЙТИ ранги вдоль любого пути от листа к корню будут строго возрастать.
При выполнении операции ОБЪЕДИНИТЬ ранг любого некорневого элемента не изменяется, а ранг корня либо сохраняется, либо увеличивается на 1.
Теорема 1. Время выполнения последовательности операций, состоящей из $$n$$ операций СОЗДАТЬ, $$u \le n - 1$$ операций ОБЪЕДИНИТЬ и $$f$$ операций НАЙТИ, при использовании рангов и сжатия путей является величиной $$O((f + n)\log^\ast\!u)$$.
Доказательство Пусть $$s_1, s_2\dts s_m$$ — все операции вида СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ, объявленные в формулировке теоремы и выписанные в порядке их следования, $$m = n + u + f$$. Очевидно, суммарная трудоемкость всех операций СОЗДАТЬ есть $$O(n)$$, суммарная трудоемкость всех операций ОБЪЕДИНИТЬ есть $$O(u)$$. Остается оценить суммарную трудоемкость операций НАЙТИ.
Через $$r_t(x)$$ обозначим
Поскольку
Оценим теперь суммарное время, требуемое для выполнения $$f$$ операций НАЙТИ; очевидно, оно пропорционально числу ребер, ведущих от сыновей к отцам и встречающихся при выполнении всех таких операций. Для оценки времени, затрачиваемого на реализацию этих операций, применим бухгалтерский прием. Отнесем расход времени на прохождение очередного ребра $$(x, y)$$ от узла $$x$$ к его родителю $$y$$ при выполнении операции $$s_{t+1}$$ типа НАЙТИ на одну из трех разных статей расходов: "корневую", "транзитную" и "местную" в зависимости от следующих условий.
Если $$i_t(x) \ne i_t(y)$$ и $$y$$ в данный момент не является корнем, то расходы относим на статью $$T$$ транзитных расходов. Если $$i_t(x) = i_t(y) = k$$ и $$y$$ не является корнем, то на статью $$M_k$$ местных расходов в $$k$$ -м диапазоне, если же $$y$$ — корень, то на статью $$K$$ корневых расходов.
Сумму местных расходов во всех диапазонах обозначим через$$\eq*{ M=\suml_{k=0}^{\log^\ast\!u} M_{k}. }$$
Имеем $$K = O(f)$$, так как при каждом выполнении операции НАЙТИ проходится одно корневое и, возможно, одно прикорневое ребро.
Для транзитных переходов имеем $$T = O(f\cdot \log^\ast\!u)$$, так как при каждом выполнении операции НАЙТИ происходит не более $$\log^\ast\!u$$ переходов из одного диапазона в другой.
Для оценки величины $$M$$ введем потенциал $$c_t(x) = r_t(p_t(x))$$ узла $$x$$ после выполнения операции $$s_t$$. Если к узлу $$x$$ еще не применялась операция СОЗДАТЬ, то $$c_t(x) = 0$$.
Потенциалом группы $$G_k(t)$$ при текущем состоянии коллекции назовем величину$$\eq*{ C_{k}(t)=\suml_{x\in G_{k} (t)} c_{t}(x). }$$
Очевидно, что в любой момент времени справедливо неравенство$$\eq{ C_k(t) \le |G_k(t)| b(k + 1). }$$
Покажем, что для любого узла $$x$$ при любом $$t = 1, 2, 3\dts m$$ выполняется неравенство $$c_t(x) \ge c_{t-1}(x)$$. Действительно, если $$s_t$$ — операция СОЗДАТЬ ( $$x$$ ), то$$\eq*{ c_{t-1}(x) = c_t(x) = 0, }$$ то есть потенциал узла $$x$$, так же, как, очевидно, и всех остальных, не изменяется. Пусть теперь $$s_t$$ — операция ОБЪЕДИНИТЬ $$(x, y)$$.
В случае $$r_{t-1}(x) < r_{t-1}(y)$$ имеем$$\eqa*{ c_t(x) = r_t(p(x)) = r_t(y) = r_{t-1}(y) > r_{t-1}(x) = r_{t-1}(p(x)) = c_{t-1}(x)\ \ \t{и }\\ c_t(y) = c_{t-1}(y). }$$ Случай $$r_{t-1}(x) > r_{t-1}(y)$$ аналогичен.
В случае $$r_{t-1}(x) = r_{t-1}(y)$$ имеем$$\eq*{ \begin{aligned} c_t(y) = r_t(p(y)) = r_t(y) = r_{t-1}(y) + 1 > r_{t-1}(y) = r_{t-1}(p(y)) = c_{t-1}(y),\\ c_t(x) = r_t(p(x)) = r_t(y) = r_{t-1}(y)+1 > r_{t-1}(y) =\\ \qq\qq\qq\;\qq\qq\qq\qq = r_{t-1}(x) = r_{t-1}(p(x)) = c_{t-1}(x). \end{aligned} }$$
Пусть теперь $$s_t$$ является операцией НАЙТИ, проходящей через узел $$x$$, и при этом $$p_{t-1}(x)$$ — не корень ( $$x$$ получает нового родителя $$p_t(x))$$. Тогда имеем$$\eq*{ c_t(x) = r_t(p_t(x)) = r_{t-1}(p_t(x)) > r_{t-1}(p_{t-1}(x)) = c_{t-1}(x). }$$
В этом случае совершен переход по
Итак, для любого узла $$x$$ величина $$c(x)$$ при выполнении операции вида СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ не может уменьшиться и, следовательно,$$\eq*{ C_k(t) \ge C_k(t- 1). }$$
При этом, если $$s_t$$ — операция НАЙТИ, то у $$M_k(t)$$ вершин при ее выполнении потенциал увеличится, по крайней мере, на 1, следовательно, число $$M_k(t)$$ местных переходов в группе $$G_k(t)$$ при ее выполнении удовлетворяет неравенству$$\eq*{ M_k(t) \le C_k(m) - C_k(m - 1). }$$
Суммируя это неравенство по всем $$t$$ и учитывая неравенство (1), получаем, что число $$M_k$$ местных переходов при всех операциях \mbox{НАЙТИ} удовлетворяет неравенству$$\eq*{ M_k \le C_k(m) - C_k(0) \le C_k(m) \le |G_k| b(k + 1). }$$
Заметим далее, что утверждение леммы 2, которая гарантирует, что количество узлов ранга $$r$$ не более $$n/2^r$$, остается верным и при использовании сжатия путей, так как при выполнении операции НАЙТИ ранги элементов не меняются. Следовательно, справедливы соотношения
$$\eq*{ |G_{k} | =\suml_{r=b(k)}^{b(k+1)-1} \frac{n}{2^{r}} < \frac{n}{2^{b(k)}} \left(1+\frac{1}{2} +\frac{1}{4} +\frac{1}{8} +\ldots \right)= \frac{2n}{2^{b(k)}} =\frac{2n}{b(k+1)}. }$$Отсюда
$$\eqa*{ M_{k} \le \frac{2n}{b(k+1)} b(k+1)=2n,\\ M = \suml_{k=0}^{\log^\ast\!u} M_{k} =O(n\cdot \log^\ast\!u). }$$Итак, суммарная трудоемкость выполнения $$f$$ операций НАЙТИ равна$$\eq*{ K + T + M = O(f + f\cdot \log^\ast\!u + n \log^\ast\!u) = O((f + n) \log^\ast\!u). }$$ Учитывая теперь оценки трудоемкости операций СОЗДАТЬ и ОБЪЕДИНИТЬ, получаем утверждение теоремы.
Замечание. Используя функцию Аккермана, задаваемую равенствами
$$\begin{alignat*}{2} A(1,j) = 2^j \q \t{при } j \ge 1,\\ A(i,1) = A(i - 1, 2)\q \t{при } i \ge 2,\\ A(i,j) = A(i - 1, A(i,j - 1))\q \t{при } i, j \ge 2. \end{alignat*}$$и обратную к ней функцию
$$\eq*{ \al(f, n) = \min\{i \ge 1: A(i, \lfloor f/n\rfloor) > \log n\}, }$$Р.Е.Тарьян доказал, что время выполнения последовательности, состоящей из $$u$$ операций ОБЪЕДИНИТЬ с перемешанными с ними $$f$$ операциями НАЙТИ, где $$u \le n - 1$$, $$u + f = m$$, является величиной $$O(m\cdot \al (m, n))$$. Также он показал, что эта оценка не может быть улучшена, то есть алгоритм может потребовать для своего выполнения $$\Om (m \cdot \al (m,n))$$ времени.
Реализация с помощью массива
| СОЗДАТЬ $$(x)$$ | $$O(1)$$ |
| ОБЪЕДИНИТЬ $$(x, y)$$ | $$O(n)$$ |
| НАЙТИ $$(x, y)$$ | $$O(1)$$ |
| $$m$$ операций | $$O(mn)$$ |
Реализация с помощью древовидной cтруктуры
| СОЗДАТЬ $$(x)$$ | $$O(1)$$ |
| ОБЪЕДИНИТЬ $$(x,y)$$ | $$O(1)$$ |
| НАЙТИ $$(x, y)$$ | $$O(n)$$ |
| $$m$$ операций | $$O(mn)$$ |
Реализация с использованием
| СОЗДАТЬ $$(x)$$ | $$O(1)$$ |
| ОБЪЕДИНИТЬ $$(x,y)$$ | $$O(1)$$ |
| НАЙТИ $$(x, y)$$ | $$O(\log n)$$ |
| $$m$$ операций | $$O(m \log n)$$ |
Реализация с использованием рангов и сжатия путей
| СОЗДАТЬ $$(x)$$ | $$O(1)$$ |
| ОБЪЕДИНИТЬ $$(x,y)$$ | $$O(1)$$ |
| НАЙТИ $$(x, y)$$ | $$O(\log n)$$ |
| $$m$$ операций | $$O(n \log^\ast (u + 1))$$ |
| $$O(m \al (m,n))$$ |
Этот тип данных применяется в таких задачах, как поиск минимального остовного дерева для заданного взвешенного неориентированного графа, построение компонент связности графа, минимизация конечного автомата, и многих других, требующих динамического поддержания некоторого отношения эквивалентности. Примеры таких задач будут рассмотрены ниже.
Как правило, в таких задачах вычисления начинаются с пустой коллекции подмножеств ( $$k = 0$$ ). Затем по мере вычислений формируются новые подмножества, включаемые в коллекцию. Формирование новых подмножеств происходит либо путем создания одноэлементного подмножества, либо путем объединения уже существующих в коллекции подмножеств. Для осуществления таких действий используются имена включенных в коллекцию подмножеств. В качестве имени подмножества будем использовать один из его элементов (главный элемент), выбираемый по определенному правилу. Поскольку в коллекции всегда будут находиться попарно непересекающиеся подмножества множества $$U$$, такое имя будет однозначно определять требуемое подмножество.
СОЗДАТЬ ( $$x$$ ). Эта операция предназначена для введения в коллекцию нового подмножества, состоящего из одного элемента $$x$$, при этом предполагается, что $$x$$ не входит ни в одно из подмножеств коллекции, созданной к моменту выполнения этой операции. Элемент $$x$$ указывается в качестве параметра. Именем созданного подмножества будет считаться сам элемент $$x$$.
ОБЪЕДИНИТЬ ( $$x,y$$ ). С помощью этой операции можно объединить два подмножества коллекции, имеющие, соответственно, имена $$x$$ и $$y$$, в одно новое подмножество, при этом оба объединяемые подмножества удаляются из коллекции, а вновь построенное подмножество получает некоторое имя. Во всех рассматриваемых нами случаях именем нового полученного в результате этой операции подмножества будет одно из имен $$x$$ или $$y$$. Имена объединяемых подмножеств указываются в качестве параметров.
НАЙТИ ( $$x, y$$ ). Эта операция позволяет определить имя $$y$$ того подмножества коллекции, которому принадлежит элемент $$x$$. Если элемент $$x$$ до выполнения операции не входил ни в одно из подмножеств коллекции, то в качестве $$y$$ берется 0.
Последовательность $$\sigma$$, составленную из операций типа
СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ, назовем
Мы рассмотрим несколько способов представления коллекции разделенных множеств в памяти компьютера и алгоритмической реализации перечисленных операций. А именно, будут описаны представления
Последний из перечисленных способов является наиболее эффективным по времени выполнения произвольных корректных последовательностей операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ. Строго говоря, во всех перечисленных случаях будут использоваться массивы, но интерпретации их содержимого будут различными. Каждый раз при описании очередной реализации мы будем обсуждать оценки трудоемкости рассматриваемых операций.
Пример 1. Рассмотрим задачу выделения компонент связности неориентированного графа. Напомним, что компонентой связности называется максимальное по включению подмножество вершин графа такое, что любые две его вершины связаны цепью. Полагаем, что вершины графа пронумерованы числами $$1, 2 \dts n$$ и каждое ребро представлено парой ( $$i, j$$ ) номеров вершин. Предполагаем также, что множество ребер не пусто.
Алгоритм выделения компонент связности неориентированного графа
$$\formula{ 1. \ \t{Создать коллекцию из } n\ \t{синглетонов множества}\ \{1, 2\dts n\};\\ 2. \ \t{Прочитать очередное ребро } (i, j);\\ 3. \ \t{Найти имя } a\ \t{подмножества коллекции, содержащего элемент } i;\\ 4. \ \t{Найти имя } b\ \t{подмножества коллекции, содержащего элемент}\ j;\\ 5. \ \t{Если}\ a \ne b,\ \t{то объединить подмножества с именами } a\ \t{и } b; \\ 6. \ \t{Если есть еще непрочитанные ребра, перейти к п.}\,2,\\ \mbox{}\q\, \t{в противном случае закончить вычисления.} }$$Очевидно, построенные подмножества коллекции будут представлять искомые
компоненты связности. Используя названия основных операций над коллекцией
Пример 2. Рассмотрим неориентированный связный граф без петель, ребрам которого приписаны в качестве весов положительные вещественные числа. Требуется построить остовное дерево, накрывающее все вершины графа и имеющее минимальный суммарный вес входящих в него ребер. Итак, пусть заданный граф $$G$$ имеет множество $$V$$ вершин, пронумерованных числами $$1, 2\dts n$$, и множество $$E$$ ребер. Каждому ребру $$e$$ из множества $$E$$ поставлена в соответствие пара $$(N(e), K(e))$$ его концевых вершин и число $$C(e)$$ — его вес. Для решения этой задачи были предложены различные алгоритмы. Мы рассмотрим алгоритм, который разработал Крускал.
Алгоритм Крускала
$$\formula{ 1. \ \t{Создать коллекцию из}\ n\ \t{одноэлементных подмножеств}\\ \mbox{}\q\, \t{множества}\ \{1, 2\dts n\};\\ 2. \ \t{Создать пустое множество}\ T;\\ 3. \ \t{В множестве}\ E\ \t{найти ребро}\ e\ \t{с минимальным весом и удалить его}\\ \mbox{}\q\, \t{из множества}\ E;\\ 4. \ \t{Найти имя}\ a\ \t{подмножества коллекции, содержащего элемент}\ N(e);\\ 5. \ \t{Найти имя}\ b\ \t{подмножества коллекции, содержащего элемент}\ K(e);\\ 6. \ \t{Если}\ a \ne b, \t{то объединить подмножества с именами}\ a\ \t{и}\ b,\ \t{а ребро}\ e\\ \mbox{}\q\, \t{добавить к множеству}\ T;\\ 7. \ \t{Если множество}\ E\ \t{не пусто и}\ |T| < n - 1,\ \t{перейти к п.}\,3,\\ \mbox{}\q\, \t{в противном случае закончить вычисления.} }$$
Заметим, что в процессе работы алгоритма в множестве $$T$$ будут находиться ребра, составляющие ациклический подграф исходного графа, являющийся лесом, состоящим из некоторого числа деревьев. Отсутствие циклов гарантируется проверкой "Если $$a \ne b$$ " в пункте 6 описанного алгоритма. Фактически при $$a \ne b$$ происходит объединение двух поддеревьев в одно дерево с помощью ребра $$e$$, найденного на шаге 3.
Если исходный граф связен, как сказано в постановке задачи, то построенное с помощью такого алгоритма множество $$T$$ будет, очевидно, представлять дерево, накрывающее все вершины исходного графа. Доказательство того, что суммарный вес входящих в него ребер будет минимальным, можно найти в разделе "Графы".
В алгоритме естественным образом используется структура разделенных множеств. Обратим внимание на операцию поиска в множестве $$E$$ ребра $$e$$ с минимальным весом. Эффективность этой операции во многом зависит от выбора структуры данных для хранения множества $$E$$. Приемы эффективного выполнения этой операции рассмотрены в разделе "Приоритетные очереди".
Пусть $$U = \{1, 2\dts n\}$$ — множество, из элементов которого будет строиться коллекция разделенных подмножеств. Одним из очевидных способов представления коллекции является представление ее с помощью массива. При таком способе для каждого элемента $$i$$ в соответствующей ( $$i$$ -й) ячейке массива помещаем имя (канонический элемент) того подмножества, которому принадлежит элемент $$i$$. Если элемент $$i$$ не принадлежит ни одному из подмножеств коллекции, то в $$i$$ -ю ячейку записываем 0.
Обозначим через $$f$$ массив длины $$n$$, с помощью которого будем представлять коллекцию. Пустая коллекция представляется массивом, заполненным нулями.
Операция СОЗДАТЬ ( $$x$$ ) осуществляется записью элемента $$x$$ в ячейку с номером $$x$$. Время выполнения операции — $$O(1)$$.
Операция ОБЪЕДИНИТЬ ( $$x,y$$ ) осуществляется следующим образом. Просматриваются элементы массива $$f$$, и в те ячейки, в которых было записано имя $$x$$, заносится новое имя — $$y$$. Следовательно, именем вновь образованного подмножества будет $$y$$, а $$x$$ перестанет быть именем какого-либо подмножества. Очевидно, время выполнения этой операции — $$O(n)$$.
Операция НАЙТИ ( $$x, y$$ ) выдает в качестве $$y$$ содержимое элемента с номером $$x$$ в массиве $$f$$. Время выполнения операции — $$O(1)$$.
При такой реализации
Пусть, по-прежнему, $$U = \{1, 2\dts n\}$$ — множество, из
элементов которого будет строиться коллекция. Каждое подмножество
коллекции представляется
Фактически в памяти компьютера это дерево будем представлять массивом $$p[1\ldots n]$$ так, что $$p(x)$$ будет предком узла $$x$$, если $$x$$ не является корнем, и $$p(x) = x$$, если $$x$$ — корень. Если же $$x$$ не входит ни в одно из подмножеств коллекции, то $$p(x) = 0$$.
Рассмотрим пример. Пусть $$U = \{1, 2\dts 7\}$$ и коллекция состоит из двух подмножеств $$\{1, 2, 3, 7\}$$ и $$\{4, 6\}$$. Деревья, представляющие эти подмножества, могут быть такими, как на рис.3.1. Кружочки обозначают узлы дерева; указатели на родителей представлены при помощи стрелок. Именем одного из этих подмножеств является 3, другого — 6:
(рис 3.1) Операция СОЗДАТЬ ( $$x$$ ) назначает в качестве родителя узла $$x$$ сам узел $$x$$ с помощью присваивания $$p[x] := x$$. Таким образом, время выполнения операции есть $$O(1)$$. В результате выполнения операции СОЗДАТЬ( $$x$$ ) образуется новое одновершинное дерево с петлей в корне, изображенное на рис. 3.2.
(рис 3.2) Если к коллекции подмножеств, изображенных на рис. 3.1, применить операцию СОЗДАТЬ (5), то получим коллекцию, изображенную на рис. 3.3.
(рис 3.3) Операция ОБЪЕДИНИТЬ ( $$x, y$$ ) назначает узел $$y$$ родителем узла $$x$$ с помощью присваивания $$p[x]:= y$$. Заметим, что $$x$$ и $$y$$ должны быть до выполнения рассматриваемой операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет $$y$$, а $$x$$ перестанет быть именем какого-либо множества. Время выполнения этой операции есть $$O(1)$$.
(рис 3.4) Если применить операцию ОБЪЕДИНИТЬ $$(3, 6)$$ к коллекции, представленной на рис. 3.3, то получим коллекцию, состоящую из двух подмножеств $$\{1, 2, 3, 4, 6, 7\}$$ и $$\{5\}$$, — изображенную на рис. 3.4. Именем первого из этих подмножеств будет 6, второго — 5.
Операция НАЙТИ ( $$x,y$$ ) осуществляется продвижением по указателям на родителей от узла $$x$$ до корня дерева. В качестве $$y$$ берется этот корень. Описанные действия можно реализовать с помощью операторов
$$\formula{ \t \while\ p[x] \ne x\ \t \do\ x := p[x];\ y := x; }$$
Очевидно, что время выполнения данной операции есть $$O(h)$$, где $$h$$ — длина пути из узла $$x$$ в корень соответствующего дерева. Но заметим, что при выполнении операций СОЗДАТЬ и ОБЪЕДИНИТЬ возможно образование дерева в виде линейной цепочки из $$n$$ узлов, изображенной на рис. 3.5.
(рис 3.5) К такой цепочке может привести, например, следующая последовательность операций
СОЗДАТЬ ( $$\bs 1$$ );
СОЗДАТЬ ( $$\bs 2$$ );
$$\dots$$ $$\dots$$ $$\dots$$
СОЗДАТЬ ( $$\bs n$$ );
ОБЪЕДИНИТЬ ( $$\bs 1, \bs 2$$ );
ОБЪЕДИНИТЬ ( $$\bs 2, \bs 3$$ );
$$\dots$$ $$\dots$$ $$\dots$$
ОБЪЕДИНИТЬ ( $$\bs n-{\bs 1},{\bs n}$$ );
Как видим, $$h$$ может достигать величины $$n$$, поэтому трудоемкость операции НАЙТИ является величиной $$O(n)$$.
Худший случай применения операции НАЙТИ в данной ситуации — это НАЙТИ ( $$1,y$$ ). В этом случае необходимо сделать $$n - 1$$ переход по ссылкам на родителей, чтобы дойти от узла $$1$$ к корню дерева $$n$$, и один переход, чтобы узнать, что родитель узла $$n$$ есть сам узел $$n$$.
Если операция СОЗДАТЬ выполняется $$n$$ раз, то время выполнения
последовательности, составленной из $$m$$ операций ОБЪЕДИНИТЬ
и/или НАЙТИ, при рассматриваемой реализации
Предыдущую реализацию
Для такой реализации
Операция СОЗДАТЬ ( $$x$$ ) назначает в качестве родителя узла $$x$$ тот же самый $$x$$, а высотой узла $$x$$ считает 0. Таким образом, время выполнения данной операции есть $$O(1)$$. В результате выполнения операции СОЗДАТЬ ( $$x$$ ) образуется новое дерево, изображенное на рис. 3.6. Число, расположенное рядом с узлом, обозначает его высоту. Описанные действия реализуются с помощью операторов
$$\formula{ p[x]:= x;\ h[x]:= 0; }$$
(рис 3.6) Операция ОБЪЕДИНИТЬ ( $$x, y$$ ) назначает корень большего по высоте дерева родителем корня другого дерева. Если деревья имеют одинаковую высоту, то узел $$y$$ назначается родителем узла $$x$$, после чего значение высоты узла $$y$$ увеличивается на единицу. Заметим, что $$x$$ и $$y$$ должны быть до выполнения операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет имя того из объединяемых подмножеств, у которого корень имел большую высоту, а имя другого из объединяемых подмножеств перестанет быть именем какого-либо из подмножеств. Очевидно, время выполнения этой операции есть константа. Выполнить описанные действия можно с помощью следующей процедуры:
$$\formula{ \t{Procedure ОБЪЕДИНИТЬ (x, y)};\\ \t begin\\ \mbox{}\q if (h[x] < h[y])\ \t then\ p[x] := y\ \t else if\ (h[x] > h[y])\ \t then\ p[y] := x\ \t else\\ \mbox{}\qq \{p[x] := y;\ h[y] := h[y] + 1\}\\ \t end; }$$На рис. 3.7 и рис. 3.8 показано применение операции ОБЪЕДИНИТЬ $$(3,6)$$ к коллекции, изображенной на рис. 3.3, с учетом высот объединяемых поддеревьев. Рядом с кружочками, изображающими узлы, показаны их высоты. Так как $$h(3) = 2 > h(6) = 1$$, то родителем узла 6 становится узел 3.
Операция НАЙТИ ( $$x,y$$ ) осуществляется, как и в предыдущей реализации, продвижением по указателям на родителей от узла $$x$$ до корня дерева. В качестве $$y$$ берется найденный корень.
(рис 3.8) (рис 3.7) Очевидно, что время выполнения данной операции, как и ранее,
пропорционально длине пути из узла $$x$$ в корень соответствующего
дерева. Однако длина такого пути в данном случае может быть оценена иначе.
Для
Лемма 1. В результате выполнения любой последовательности операций из набора $$\{$$ СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ $$\}$$ над пустой коллекцией разделенных множеств для любого узла $$x$$ выполняется неравенство $$n[x]\ge 2^{h(x)}$$, где $$n[x]$$ — количество узлов в поддереве с корнем $$x, h[x]$$ — высота узла $$x$$.
Доказательство Очевидно, перед первым применением операции ОБЪЕДИНИТЬ для любого узла $$x$$ имели $$n[x] = 1$$, $$h[x] = 0$$ и, следовательно, $$n[x] \ge 2^{h(x)}$$. Операции СОЗДАТЬ и НАЙТИ не могут нарушить доказываемого неравенства, поэтому доказательство можно провести индукцией по количеству применений операции ОБЪЕДИНИТЬ.
Предположим, что перед очередным применением операции ОБЪЕДИНИТЬ ( $$x,y$$ ) доказываемое неравенство все еще остается верным, тогда если высота узла $$x$$ меньше высоты узла $$y$$, то дерево, полученное с помощью ОБЪЕДИНИТЬ ( $$x, y$$ ), имеет корень $$y$$, а высоты узлов $$x$$ и $$y$$ не изменились. Количество узлов в дереве с корнем $$x$$ не изменилось, а количество узлов в дереве с корнем $$y$$ увеличилось. Таким образом, как для узлов $$x$$, $$y$$, так и для всех остальных неравенство сохраняется. Случай, когда высота узла $$x$$ больше высоты узла $$y$$, аналогичен рассмотренному.
Если же высоты деревьев с корнями $$x$$ и $$y$$ до выполнения операции были одинаковы ( $$h[x] = h[y] = h)$$, то узел $$y$$ становится родителем узла $$x$$, высота узла $$y$$ увеличивается на 1, а высота узла $$x$$ не изменяется. Пусть после выполнения операции величины $$h[x]$$, $$h[y]$$, $$n[x]$$, $$n[y]$$ становятся равными соответственно $$h'[x]$$, $$h'[y]$$, $$n'[x]$$, $$n'[y]$$, тогда имеем $$h'[y] = h [y] + 1$$, $$h'[x] = h[x]$$, $$n'[x] = n[x]$$, $$n'[y] = n[y] + n[x]$$. По предположению индукции, имеем $$n[y] \ge 2^{h[y]}$$ и $$n[x] \ge 2^{h[x]}$$. Следовательно, после выполнения рассматриваемой операции для узлов $$x$$ и $$y$$ имеем соотношения$$\eqa*{ n'[x] = n[x] \ge 2^{h[x]} = 2^{h' [x]}\q \t{и }\\ n'[y] = n[y] + n[x] \ge 2^{h [y]} + 2^{h [x]} = 2^{h + 1} = 2^{h' [y]}. }$$ Таким образом, утверждение леммы остается верным и в этом случае.
Лемма 2. Если за время работы, начавшейся с пустой коллекции, операция СОЗДАТЬ применялась $$n$$ раз, то для любого $$h \ge 0$$ число $$k$$ узлов высоты $$h$$ удовлетворяет неравенству $$k \le n/2^h$$.
Доказательство Пусть $$x_1,x_2\dts x_k$$ — все узлы высоты $$h$$, тогда по лемме 1 при $$i \!=\! 1, 2\dts k$$ справедливы неравенства $${n[x_i] \!\ge\! 2^h}$$. Таким образом,$$\eq*{ n \ge n[x_1] + n[x_2] + ... + n[x_k] \ge k2^h, }$$ откуда и следует требуемое неравенство $$k \le n/2^h$$.
Следствие 3.
В результате выполнения любой последовательности
операций из набора $$\{$$ СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ $$\}$$ над
пустой коллекцией
Доказательство Дерево максимальной высоты образуется, очевидно, лишь тогда, когда все $$n$$ элементов объединяются в одно множество. Для такого дерева количество $$k$$ узлов максимальной высоты $$h$$ равно 1, по лемме 2 имеем $$1 = k \le n/2^h$$, откуда $$2^h \le n$$ и, следовательно, $$h \le \log n$$.
Следствие 4. Время выполнения операции НАЙТИ есть $$O(\log n)$$.
Следствие 5.
При реализации
Замечание
При реализации операции объединения подмножеств в
качестве
Предыдущий способ реализации
$$\formula{ \t begin p[x]:= x;\ r[x] := 0\ \t end; }$$
В качестве родителя узла $$x$$ берется тот же самый $$x$$, а его рангом считаем $$0$$. Таким образом, время выполнения операции есть константа.
Для анализа трудоемкости выполнения операций нам потребуются две функции. Одна из них, $$b(n)$$, является суперэкспонентой и определяется следующим образом:
$$\eq*{ b(0) = 0,\q b(n) = 2^{b(n-1)}\q \t{при } n > 0. }$$Вторая — суперлогарифм $$\log^\ast n$$, по основанию 2, определяемая соотношением
$$\eq*{ \log^\ast n = \max\{k: b(k) \le n\}. }$$Суперлогарифм является в некотором смысле обратной функцией к суперэкспоненте, $$\log^\ast (b(n)) = n$$. Значения функций $$\log^\ast n$$ и $$b(n)$$ при нескольких значениях аргументов приведены в следующих таблицах:
| $$n$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ |
| $$b(n)$$ | $$0$$ | $$1$$ | $$2$$ | $$4$$ | $$16$$ | $$65536$$ | $$2^{65536}$$ |
| $$n$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$\dots$$ | $$15$$ | $$16$$ | $$\dots$$ | $$65535$$ | $$65536$$ | $$\dots$$ | $$2^{65536}-1$$ |
| $$\log^\ast n$$ | $$0$$ | $$1$$ | $$2$$ | $$2$$ | $$3$$ | $$3$$ | $$\dots$$ | $$3$$ | $$4$$ | $$\dots$$ | $$4$$ | $$5$$ | $$\dots$$ | $$5$$ |
Ребро $$(x, p(x))$$ при текущем состоянии коллекции назовем корневым, если $$p(x)$$ — корень и $$p(x) = x$$ (петля); назовем его прикорневым, если $$p(x)$$ — корень и $$p(x) \ne x$$, в противном случае — внутренним.
Отметим следующие свойства коллекции на множестве из $$n$$ элементов. Прикорневое ребро может превратиться во внутреннее, а корневое — в прикорневое только при выполнении операции ОБЪЕДИНИТЬ.
Если при выполнении очередной операции ОБЪЕДИНИТЬ $$(x,y)$$ узел $$y$$ становится родителем узла $$x$$, то после ее выполнения справедливо неравенство $$r(y) > r(x)$$.
При выполнении операции НАЙТИ
Если перед выполнением операции НАЙТИ узел $$x$$ был родителем узла $$y$$, а после выполнения этой операции родителем узла $$y$$ стал узел $$x' \ne x$$, то выполняется неравенство $$r(x) < r(x')$$. Следовательно, даже после изменения леса в результате выполнения операции НАЙТИ ранги вдоль любого пути от листа к корню будут строго возрастать.
При выполнении операции ОБЪЕДИНИТЬ ранг любого некорневого элемента не изменяется, а ранг корня либо сохраняется, либо увеличивается на 1.
Теорема 1. Время выполнения последовательности операций, состоящей из $$n$$ операций СОЗДАТЬ, $$u \le n - 1$$ операций ОБЪЕДИНИТЬ и $$f$$ операций НАЙТИ, при использовании рангов и сжатия путей является величиной $$O((f + n)\log^\ast\!u)$$.
Доказательство Пусть $$s_1, s_2\dts s_m$$ — все операции вида СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ, объявленные в формулировке теоремы и выписанные в порядке их следования, $$m = n + u + f$$. Очевидно, суммарная трудоемкость всех операций СОЗДАТЬ есть $$O(n)$$, суммарная трудоемкость всех операций ОБЪЕДИНИТЬ есть $$O(u)$$. Остается оценить суммарную трудоемкость операций НАЙТИ.
Через $$r_t(x)$$ обозначим
Поскольку
Оценим теперь суммарное время, требуемое для выполнения $$f$$ операций НАЙТИ; очевидно, оно пропорционально числу ребер, ведущих от сыновей к отцам и встречающихся при выполнении всех таких операций. Для оценки времени, затрачиваемого на реализацию этих операций, применим бухгалтерский прием. Отнесем расход времени на прохождение очередного ребра $$(x, y)$$ от узла $$x$$ к его родителю $$y$$ при выполнении операции $$s_{t+1}$$ типа НАЙТИ на одну из трех разных статей расходов: "корневую", "транзитную" и "местную" в зависимости от следующих условий.
Если $$i_t(x) \ne i_t(y)$$ и $$y$$ в данный момент не является корнем, то расходы относим на статью $$T$$ транзитных расходов. Если $$i_t(x) = i_t(y) = k$$ и $$y$$ не является корнем, то на статью $$M_k$$ местных расходов в $$k$$ -м диапазоне, если же $$y$$ — корень, то на статью $$K$$ корневых расходов.
Сумму местных расходов во всех диапазонах обозначим через$$\eq*{ M=\suml_{k=0}^{\log^\ast\!u} M_{k}. }$$
Имеем $$K = O(f)$$, так как при каждом выполнении операции НАЙТИ проходится одно корневое и, возможно, одно прикорневое ребро.
Для транзитных переходов имеем $$T = O(f\cdot \log^\ast\!u)$$, так как при каждом выполнении операции НАЙТИ происходит не более $$\log^\ast\!u$$ переходов из одного диапазона в другой.
Для оценки величины $$M$$ введем потенциал $$c_t(x) = r_t(p_t(x))$$ узла $$x$$ после выполнения операции $$s_t$$. Если к узлу $$x$$ еще не применялась операция СОЗДАТЬ, то $$c_t(x) = 0$$.
Потенциалом группы $$G_k(t)$$ при текущем состоянии коллекции назовем величину$$\eq*{ C_{k}(t)=\suml_{x\in G_{k} (t)} c_{t}(x). }$$
Очевидно, что в любой момент времени справедливо неравенство$$\eq{ C_k(t) \le |G_k(t)| b(k + 1). }$$
Покажем, что для любого узла $$x$$ при любом $$t = 1, 2, 3\dts m$$ выполняется неравенство $$c_t(x) \ge c_{t-1}(x)$$. Действительно, если $$s_t$$ — операция СОЗДАТЬ ( $$x$$ ), то$$\eq*{ c_{t-1}(x) = c_t(x) = 0, }$$ то есть потенциал узла $$x$$, так же, как, очевидно, и всех остальных, не изменяется. Пусть теперь $$s_t$$ — операция ОБЪЕДИНИТЬ $$(x, y)$$.
В случае $$r_{t-1}(x) < r_{t-1}(y)$$ имеем$$\eqa*{ c_t(x) = r_t(p(x)) = r_t(y) = r_{t-1}(y) > r_{t-1}(x) = r_{t-1}(p(x)) = c_{t-1}(x)\ \ \t{и }\\ c_t(y) = c_{t-1}(y). }$$ Случай $$r_{t-1}(x) > r_{t-1}(y)$$ аналогичен.
В случае $$r_{t-1}(x) = r_{t-1}(y)$$ имеем$$\eq*{ \begin{aligned} c_t(y) = r_t(p(y)) = r_t(y) = r_{t-1}(y) + 1 > r_{t-1}(y) = r_{t-1}(p(y)) = c_{t-1}(y),\\ c_t(x) = r_t(p(x)) = r_t(y) = r_{t-1}(y)+1 > r_{t-1}(y) =\\ \qq\qq\qq\;\qq\qq\qq\qq = r_{t-1}(x) = r_{t-1}(p(x)) = c_{t-1}(x). \end{aligned} }$$
Пусть теперь $$s_t$$ является операцией НАЙТИ, проходящей через узел $$x$$, и при этом $$p_{t-1}(x)$$ — не корень ( $$x$$ получает нового родителя $$p_t(x))$$. Тогда имеем$$\eq*{ c_t(x) = r_t(p_t(x)) = r_{t-1}(p_t(x)) > r_{t-1}(p_{t-1}(x)) = c_{t-1}(x). }$$
В этом случае совершен переход по
Итак, для любого узла $$x$$ величина $$c(x)$$ при выполнении операции вида СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ не может уменьшиться и, следовательно,$$\eq*{ C_k(t) \ge C_k(t- 1). }$$
При этом, если $$s_t$$ — операция НАЙТИ, то у $$M_k(t)$$ вершин при ее выполнении потенциал увеличится, по крайней мере, на 1, следовательно, число $$M_k(t)$$ местных переходов в группе $$G_k(t)$$ при ее выполнении удовлетворяет неравенству$$\eq*{ M_k(t) \le C_k(m) - C_k(m - 1). }$$
Суммируя это неравенство по всем $$t$$ и учитывая неравенство (1), получаем, что число $$M_k$$ местных переходов при всех операциях \mbox{НАЙТИ} удовлетворяет неравенству$$\eq*{ M_k \le C_k(m) - C_k(0) \le C_k(m) \le |G_k| b(k + 1). }$$
Заметим далее, что утверждение леммы 2, которая гарантирует, что количество узлов ранга $$r$$ не более $$n/2^r$$, остается верным и при использовании сжатия путей, так как при выполнении операции НАЙТИ ранги элементов не меняются. Следовательно, справедливы соотношения
$$\eq*{ |G_{k} | =\suml_{r=b(k)}^{b(k+1)-1} \frac{n}{2^{r}} < \frac{n}{2^{b(k)}} \left(1+\frac{1}{2} +\frac{1}{4} +\frac{1}{8} +\ldots \right)= \frac{2n}{2^{b(k)}} =\frac{2n}{b(k+1)}. }$$Отсюда
$$\eqa*{ M_{k} \le \frac{2n}{b(k+1)} b(k+1)=2n,\\ M = \suml_{k=0}^{\log^\ast\!u} M_{k} =O(n\cdot \log^\ast\!u). }$$Итак, суммарная трудоемкость выполнения $$f$$ операций НАЙТИ равна$$\eq*{ K + T + M = O(f + f\cdot \log^\ast\!u + n \log^\ast\!u) = O((f + n) \log^\ast\!u). }$$ Учитывая теперь оценки трудоемкости операций СОЗДАТЬ и ОБЪЕДИНИТЬ, получаем утверждение теоремы.
Замечание. Используя функцию Аккермана, задаваемую равенствами
$$\begin{alignat*}{2} A(1,j) = 2^j \q \t{при } j \ge 1,\\ A(i,1) = A(i - 1, 2)\q \t{при } i \ge 2,\\ A(i,j) = A(i - 1, A(i,j - 1))\q \t{при } i, j \ge 2. \end{alignat*}$$и обратную к ней функцию
$$\eq*{ \al(f, n) = \min\{i \ge 1: A(i, \lfloor f/n\rfloor) > \log n\}, }$$Р.Е.Тарьян доказал, что время выполнения последовательности, состоящей из $$u$$ операций ОБЪЕДИНИТЬ с перемешанными с ними $$f$$ операциями НАЙТИ, где $$u \le n - 1$$, $$u + f = m$$, является величиной $$O(m\cdot \al (m, n))$$. Также он показал, что эта оценка не может быть улучшена, то есть алгоритм может потребовать для своего выполнения $$\Om (m \cdot \al (m,n))$$ времени.
Реализация с помощью массива
| СОЗДАТЬ $$(x)$$ | $$O(1)$$ |
| ОБЪЕДИНИТЬ $$(x, y)$$ | $$O(n)$$ |
| НАЙТИ $$(x, y)$$ | $$O(1)$$ |
| $$m$$ операций | $$O(mn)$$ |
Реализация с помощью древовидной cтруктуры
| СОЗДАТЬ $$(x)$$ | $$O(1)$$ |
| ОБЪЕДИНИТЬ $$(x,y)$$ | $$O(1)$$ |
| НАЙТИ $$(x, y)$$ | $$O(n)$$ |
| $$m$$ операций | $$O(mn)$$ |
Реализация с использованием
| СОЗДАТЬ $$(x)$$ | $$O(1)$$ |
| ОБЪЕДИНИТЬ $$(x,y)$$ | $$O(1)$$ |
| НАЙТИ $$(x, y)$$ | $$O(\log n)$$ |
| $$m$$ операций | $$O(m \log n)$$ |
Реализация с использованием рангов и сжатия путей
| СОЗДАТЬ $$(x)$$ | $$O(1)$$ |
| ОБЪЕДИНИТЬ $$(x,y)$$ | $$O(1)$$ |
| НАЙТИ $$(x, y)$$ | $$O(\log n)$$ |
| $$m$$ операций | $$O(n \log^\ast (u + 1))$$ |
| $$O(m \al (m,n))$$ |
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.