693
правки
Изменения
→union
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''<tex>\mathrm{union}</tex>''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''<tex>\mathrm{get}</tex>'').
Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где <tex>\mathrm{get}</tex> будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацимиреализациями]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).
===Объединение по рангу===
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.
Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен <tex>10</tex>. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на <tex>1</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] < r[y] p[x] = y '''else''' p[y] = x Также возможна реализация функции <tex>\mathrm{get}</tex> без использования <tex>\mathrm{O(\log n)}</tex> дополнительной памяти. ===='''get'''==== '''function''' '''get'''(x: '''int'''): '''int''' root = x '''while''' p[root] != root root = p[root] i = x '''while''' p[i] != i j = p[i] p[i] = root i = j '''return''' root
==Асимптотика==
| ''<tex>\mathrm{union}</tex>'' || <tex>\mathrm{O(\log n)}</tex> || <tex>\mathrm{O(\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> является логарифмическим.
{| 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>\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 [\dfrac{m}{n} \right ] \right )} \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} ( b </tex>. Можем считать, что число операций <tex> \mathrm{union} </tex> равно числу элементов множества, так как количество операций <tex>\mathrm{union}</tex> не превосходит количество элементов множества <tex>n</tex>. Заметим, что <tex>m\geqslant n</tex>, так как при каждом вызове операции <tex>\mathrm{union}</tex> дважды вызывается операция <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{K(v)} </tex> — количество вершин в поддереве, корнем которого является <tex>\mathrm{v}</tex>.
{{Утверждение
|statement=
<tex> \mathrm{R(P(v))} > \geqslant \mathrm{R(v)} </tex>
|proof=
#<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>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}
{{Утверждение
|statement=
<tex> \mathrm{R(v)} = i \Rightarrow {\mathrm{K(v)}} \geqslant {2^i }</tex>
|proof=
Докажем по индукции:
Из последнего утверждения следует:
{{Теорема
|proof=
<center>
<texdpi="150">\sum_u \limits i^{\sum_mathrm{R(u)}}=\mathrmsum_{k=0}^{\log n} \limits {\dfrac sum_{n \mathrm{B{R(u)}=k}} \limits i^k)\leqslant \sum_{k=0}^{\log n}\limits i^k \cdot \frac{n} {2^{k} \leqslant n \cdot \mathrmsum_{k=0}^{\log n}\limits \dfrac{i^k}{2^k}= \mathrm{O(n)}</tex>
</center>
}}
* [http://ru.wikipedia.org/wiki/Функция_Аккермана Функция Аккермана {{---}} Википедия]
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - стр 589. — ISBN 978-5-8459-0857-4
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]