Изменения

Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции (<tex>\mathrm{get }</tex> и <tex>\mathrm{union}</tex>) выполняются в среднем за практически константное время.

Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах вершинах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".

При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''<tex>\mathrm{union}</tex>''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''<tex>\mathrm{get}</tex>'').

Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где <tex>\mathrm{get }</tex> будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацимиреализациями]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).

Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1<tex>0</tex>. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на <tex>1</tex>.

Эта эвристика несколько модифицирует операцию ''<tex>\mathrm{get}</tex>''. Операция <tex>\mathrm{get }</tex> вызывается для элемента ''<tex>x''</tex>, проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''<tex>x''</tex>. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция ''<tex>\mathrm{get}</tex>'' становится двухпроходной.

Для реализации СНМ будем поддерживать следующие массивы:<tex>p[x]</tex> {{---}} массив "родителей", <tex>r[x]</tex> {{---}} массив рангов.===='''get'''==== '''function''' '''get'''(x: '''int'''): '''int''' '''if''' p[x] != x p[x] = get(p[x]) '''return''' p[x]

===='''union'''==== '''function''' '''union'''(x: '''int''', y: '''int'''): x = get(x) y = get(y) '''if''' x == y '''return''' '''if''' r[x] == r[y] r[x]++ '''if''' r[x] <tex>r[y] p[x]= y '''else''' p[y] = x Также возможна реализация функции <tex>\mathrm{get}</tex> без использования <tex>\mathrm{{---O(\log n)}} массив "родителей"</tex> дополнительной памяти.

<tex>r[x]</tex> {{---}} массив рангов.===='''get'''==== '''function''' '''get'''(x: '''int'''): '''int''' if p[x] ! root = x '''while''' p[xroot] != get(p[x])root return root = p[xroot] ====union=== i = union(x, y) x '''while''' p[i] != get(x)i y j = get(y) if x == y return; if r[x] == r[y] rp[xi]++ if r[x] < r[y] p[xi] = yroot elsei = j p[y] = x '''return''' root

| ''<tex>\mathrm{get}</tex>'' || <tex>\mathrm{O(\log n)}</tex> || <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex>

| ''<tex>\mathrm{union}</tex>'' || <tex>\mathrm{O(1\log n)}</tex> || <tex>\mathrm{O(1\mathrm{\alpha(m, n)})}</tex>

* Где <tex>m </tex> {{---}} общее количество операций * , <tex>n </tex> {{---}} полное количество элементов * , <tex>\mathrm{\alpha(m, n)}</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций <tex>\mathrm{get }</tex> и <tex>n</tex> элементов).

Докажем, что если глубина множества (т.е. его ранг) равна <tex>k</tex>, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с <tex>n </tex> элементами есть <tex>\mathrm{O(\log n)}</tex>, а значит и время работы операции <tex>\mathrm{get }</tex> является логарифмическим.

Будем доказывать данное свойство по индукции. Для <tex>k = 0</tex>, очевидно, в множестве содержится <tex>1 </tex> вершина. Пусть для множеств ранга <tex>k - 1 </tex> свойство выполняется. Как следует из ранговой эвристики, множество ранга <tex>k </tex> может получиться только при подвешивании множества ранга <tex>k - 1 </tex> к множеству ранга <tex>k - 1</tex>. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.

<tex>\mathrm{A(m, n) } = \begin{cases}

\mathrm{A(m - 1, A(m, n - 1))}, & m > 1, n > 0

!<tex>\mathbf{m \backslash n}</tex> !! <tex>\mathbf{0 }</tex> !! <tex>\mathbf{1 }</tex> !! <tex>\mathbf{2 }</tex> !! <tex>\mathbf{3 }</tex> !! <tex>\mathbf{4 }</tex> !! <tex>\mathbf{5}</tex>|- style = "text-align = center"| ! <tex>\mathbf{1 }</tex> || <tex>1 </tex> || <tex>2 </tex> || <tex>4 </tex> || <tex>8 </tex> || <tex>16 </tex> || <tex>32</tex>

| ! <tex>\mathbf{2 }</tex> || <tex>2 </tex> || <tex>4 </tex> || <tex>16 </tex> || <tex>65536 </tex> || <tex>2^{2^{16}}</tex> || <tex>2^{2^{2^{16}}}</tex>

| ! <tex>\mathbf{3 }</tex> || <tex>2 </tex> || <tex>16 </tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{A(3, 2)}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>

| ! <tex>\mathbf{4 }</tex> || <tex>2 </tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>

Функция, обратная функции Аккермана <tex>\mathrm{\alpha(m, n)}</tex> , равна минимальному <tex>i</tex> такому, что <tex>\mathrm{A \left (i, \left [\fracdfrac{m}{n} \right ] \right ) } \geq geqslant \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция <tex>\mathrm{get }</tex> выполняется за константное время.

===Анализ Проведем анализ реализации с ранговой эвристикой. Будем доказывать, что амортизационная стоимость <tex> \mathrm{get} =\mathrm{O(\log^{*}n)} </tex>.{{Определение|definition='''Итерированный логарифм''' (англ. ''Iterated logarithm'') <tex>\mathrm{\log^*n}</tex> — минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</tex>.}}'''Пример''': <tex>\mathrm{\log^*_2 16} =3</tex>

Проведем анализ реализации с ранговой эвристикой, будем доказывать более слабую оценку(итерированный логарифм).Рассмотрим <tex> a n </tex> операций <tex> \mathrm{union } </tex> и <tex> b m </tex> операций <tex> \mathrm{get } </tex>. Можем считать, что число операций <tex> \mathrm{union} </tex> равно числу элементов множества, так как количество операций <tex>\mathrm{union}</tex> не превосходит количество элементов множества <tex>n</tex> (. Заметим, что <tex>m\geqslant n</tex>, так как при каждом вызове операции <tex>\mathrm{union}</tex> b дважды вызывается операция <tex> a \mathrm{get}</tex>).Не теряя общности, будем считать, что <tex> \mathrm{union } </tex> принимает в качестве аргументов представителей,то есть <tex> \mathrm{union(v_1,v_2) } </tex> заменяем на <tex> \mathrm{union(get(v_1),get(v_2)) } </tex>.

Оценим стоимость операции <tex> \mathrm{get(v) } </tex>. Обозначим <tex> \mathrm{R(v) } </tex> — ранг вершины, <tex>\mathrm{P(v)}</tex> — представитель множества, содержащего <tex> \mathrm{v }</tex>,<tex> \mathrm{L(v) } </tex> — отец вершины,<tex> \mathrm{K(v) } </tex> — количество вершин в поддереве, корнем которого является <tex> \mathrm{v }</tex>.

{{Утверждение

<tex> \mathrm{R(P(v)) > } \geqslant \mathrm{R(v) } </tex>

Из Если <tex>\mathrm{v}</tex> — представитель множества, то <tex>\mathrm{P(v)}=\mathrm{v}</tex> и <tex> \mathrm{R(P(v))} = \mathrm{R(v)} </tex>. Иначе, из принципа работы функции <tex> get \mathrm{union} </tex> следует:#<tex> \mathrm{R(L(v))}>\mathrm{R(v) } </tex>.#Между <tex> \mathrm{v } </tex> и <tex> \mathrm{P(v) } </tex> существует путь вида: <tex> \mathrm{v } \rightarrow \mathrm{L(v) } \rightarrow \mathrm{L(L(v)) } \rightarrow \dots \rightarrow \mathrm{P(v) } </tex>.

{{Утверждение

<tex> \mathrm{R(v) } = i \Rightarrow {\mathrm{K(v) }} \ge geqslant {2^i }</tex>

Для <tex>0 </tex> равенство очевидно.

<tex>\mathrm{K(v) } \ge geqslant \mathrm{K(v_1) } + \mathrm{K(v_2) } \ge geqslant 2^{i-1}+2^{i-1} \ge geqslant 2^i </tex>.

#{{Утверждение|statement=<tex> \mathrm{R(v) } \le leqslant \log_2a log_2n </tex>.#}}{{Утверждение|statement=Количество вершин ранга <tex> i \le leqslant \dfrac{n} {a \over 2^i} </tex>.|proof=Если бы это было не так, то просуммировав количество вершин всех рангов, мы получили бы число большее <tex>n</tex>. Это противоречит условию, по которому <tex>n</tex> — число всех вершин. Значит утверждение верно.}}

Амортизационная стоимость <tex> \mathrm{get } = \mathrm{O(\log^{*}an) } </tex>

<center>Рассмотрим все вызовы функции <tex>S = {\sum_mathrm{get(u)} \limits} ({\sum_{v:v \in get</tex>. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина <tex>u</tex> не корень и не сын корня,v \in T_1} \limits 1}+{то во время рекурсивных вызовов функции <tex>\sum_mathrm{v:v \in get,v \in T_2(u)} </tex> текущее значение <tex>\limits 1} + mathrm{\sum_{v: \in get,v \in T_3R(L(u))} \limits 1} ) </ b tex> возрастает.Пусть </tex>,m</centertex>где — количество вызовов операции <tex> \mathrm{v \in get (u)} </tex> означает, что ребро, начало которого находится в <tex> n</tex> — количество вызовов операции <tex>\mathrm{union(v , u)}</tex>, было пройдено во время выполнения текущего и <tex> get m\geqslant n</tex>. Ребро Разделим все вершины на <tex> v 4</tex> эквивалентно вершине, в которой оно начинается.типа:

В силу того, что :1. <tex>u</tex> — корень. Таких вызовов <tex>\mathrm{get(u)}</tex> будет ровно <tex>m</tex>.:2. <tex>u</tex> — сын корня. Таких вызовов <tex>\sum_mathrm{vget(u)}</tex> будет не больше чем <tex>m</tex>.Оставшиеся вершины разделим на::v 3. Быстро растущие вызовы — такие что <tex>\mathrm{R(P(u))} \in get,v geqslant i^{\in T_1mathrm{R(u)}} </tex>, где <tex>i</tex> — число из диапазона <tex dpi="150">e ^{\limits frac{1} {e}} < i < 2</tex> <tex dpi= O"150">(e ^{\frac{1}{e}}\approx </tex> <tex>1.44</tex><tex dpi="150">) </tex> получаем.:4. Медленно растущие вызовы — <tex>\mathrm{R(P(u))} < i^{\mathrm{R(u)}}</tex>.

Для первых двух типов вершин одна операция <centertex>\mathrm{get(u)}</tex>работает за истинное время <tex>S = \mathrm{O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1</b+ {\sum_{get} \limits} ~ {\sum_{v:v \in gettex>,v \in T_3} поэтому их суммарное время работы не превышает <tex>2\limits} 1 / bcdot m</tex>.</center>

Во время При каждом вложенном вызове функции <tex> \mathrm{get (u)}</tex> после прохождения K ребер из второго класса для вершин третьего типа ранг по условию возрастает до <tex> i^{\mathrm{R(v_1u) }}</tex>. Ранг вершины может меняться в пределах от <tex>0</tex> до <tex>\ge x^{x^log_2n</tex>. Значит количество рекурсивных вызовов равняется количеству возведений в степень <tex>\mathrm{R(n)}</tex> числа <tex>i</tex>,необходимых для достижения числа <tex>\log_2n</tex>. Или что то же самое, количеству логарифмирований по основанию <tex>i</tex> числа <tex>\log_2n</tex> для получения <tex>1</tex> и еще одному логарифмированию для получения <tex>0</tex>.Количество логарифмирований описывается функцией <tex dpi="130">\log^*_{i} \left (\log_2 n \right )</tex>.С учетом последнего логарифмирования формула примет вид <tex dpi="130">\log^*_{i}n</tex>.^Тогда время работы <tex>m</tex> быстро растущих вызовов равно <tex>\mathrm{xO(m\cdot \log^{R(v* n)}}}}}} </tex>.

Из выше сказанного и первого следствия второго утверждения получаемПоскольку количество вершин с рангом <tex>k</tex> не превышает число <tex>\dfrac{n}{2^k}</tex>, что:то суммарное время работы медленно растущих вызовов равно

<texdpi="150"> \sum_u \limits i^{\mathrm{R(u)}}=\sum_{v:v k=0}^{\log n} \in get,v limits \in T_2sum_{\mathrm{{R(u)}=k}} \limitsi^k \leqslant \sum_{k=0} ^{\le log n} \limits i^k \cdot \logfrac{n}{2^*_x(k} \leqslant n \cdot \log_2a) sum_{k= O(0}^{\logn} \limits \dfrac{i^k}{2^*ak} = \mathrm{O(n)}</tex>.

Для того, чтобы <tex> \log^*_x(\log_2a) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.  Рассмотрим сумму<center> <tex>{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/b < {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a </tex>. </center> Из первого утверждения и в силу использования сжатия путей следует,что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>. Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>. <center><tex>{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits } 1/a \le \sum_v \limits x^{R(v)} /a</tex>.</center> Из второго следствия второго утверждения следует:<center> <tex> {\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a \le \sum_{Rank=0}^{\log_2a} \limits {ax^{Rank} \over 2^{Rank} a}</tex>См.</center> При <tex> x < 2~</tex>:<center><tex>{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a\le\sum_{Rankтакже =0}^{\log_2a} \limits {x^{Rank} \over 2^{Rank}}\le\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}\le{ 2 \over 2-x } = O* [[СНМ (1списки с весовой эвристикой)]]</tex>.</center>   Итак <tex> S = O(1) + O(\log^*x) + O[[СНМ (1наивные реализации) = O(\log^*x) </tex>.В силу того, что интервал (1.45; 2) не пустой, теорема доказана. }}]]

==СсылкиИсточники информации==