693
правки
Изменения
→union
Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции (<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> дополнительной памяти.
==Асимптотика==
!Операция !! Истинное время !! Амортизированное время
|- style = "text-align = center"
| ''<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>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>m</tex> и <tex>n</tex>:
<tex>\mathrm{A(m, n) } = \begin{cases}
2^n, & m = 1 \\
2, & m > 1, n = 0 \\
\mathrm{A(m - 1, A(m, n - 1))}, & m > 1, n > 0
\end{cases} </tex>
{| class="wikitable" border = 1
|-
!<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>\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> n </tex> операций <tex> \mathrm{union } </tex> и <tex> m </tex> операций <tex> \mathrm{get } </tex> (. Можем считать, что число операций <tex> \mathrm{union} </tex> равно числу элементов множества, так как количество операций <tex>\mathrm{union}</tex> не превосходит количество элементов множества <tex>n</tex>. Заметим, что <tex> m \geqslant n</tex> n , так как при каждом вызове операции <tex>\mathrm{union}</tex> дважды вызывается операция <tex>\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>.
{{Утверждение
|statement=
<tex> \mathrm{R(P(v)) > } \geqslant \mathrm{R(v) } </tex>
|proof=
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}
{{Утверждение
|statement=
<tex> \mathrm{R(v) } = i \Rightarrow {\mathrm{K(v) }} \ge geqslant {2^i }</tex>
|proof=
Докажем по индукции:
Для <tex>0 </tex> равенство очевидно.
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</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{get } = \mathrm{O(\log^{*}(n)) } </tex>
|proof=
Поскольку количество вершин с рангом <tex>k</tex> не превышает число <tex>\dfrac{n}{2^k}</tex>, то суммарное время работы медленно растущих вызовов равно
<center>
<texdpi="150">S = O\sum_u \limits i^{\mathrm{R(1u) + {}}=\sum_{getk=0}^{\log n} \limits} ~ {\sum_{v:v \in get,v \in T_2mathrm{{R(u)}=k}} \limitsi^k \leqslant \sum_{k=0} 1/m+ ^{\sum_{getlog n} \limitsi^k \cdot \frac{n} ~ {2^k} \leqslant n \cdot \sum_{v:v k=0}^{\log n} \in get,v limits \in T_3dfrac{i^k}{2^k} = \limitsmathrm{O(n)} 1 / m</tex>.
</center>
В итоге получаем, что суммарное время работы операции <tex>\mathrm{get(u)}</tex> равняется <tex>T = \mathrm{O(m)} + \mathrm{O(m\cdot \log^* n)} +\mathrm{O(n)} = \mathrm{O(m\cdot \log^*n + n)}</tex>.
С учетом того факта что <tex>m\geqslant n</tex>, амортизированное время работы равно <tex>\mathrm{O(\log^* n)}</tex>.
}}
==СсылкиИсточники информации==
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств {{---}} описание этой реализации на habrahabr.ru]
* [http://ru.wikipedia.org/wiki/Функция_Аккермана Функция Аккермана {{---}} Википедия]
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - стр 589. — ISBN 978-5-8459-0857-4