1632
правки
Изменения
м
itog root = x '''while''' p[itogroot] != itogroot itog root = p[itogroot]
i j = p[i] p[i] = itogroot i = j '''return''' itog root
:'''Пример''': <tex>\mathrm{\log^*_2 16} = 3</tex>
rollbackEdits.php mass rollback
Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции (<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).
===Объединение по рангу===
p[y] = x
Также возможна реализация функции <tex>\mathrm{get}</tex> без использования <tex>\mathrm{O(\log n)}</tex> дополнительнй дополнительной памяти.
===='''get'''====
'''function''' '''get'''(x: '''int'''): '''int'''
i = x
'''while''' p[i] != i
==Асимптотика==
:''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с ранговой эвристикой]]''
|definition='''Итерированный логарифм''' (англ. ''Iterated logarithm'') <tex>\mathrm{\log^*n}</tex> — минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</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>, так как при каждом вызове операции <tex>\mathrm{union}</tex> дважды вызывается операция <tex>\mathrm{get}</tex>.
|proof=
Рассмотрим все вызовы функции <tex>\mathrm{get(u)}</tex>. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина <tex>u</tex> не корень и не сын корня, то во время рекурсивных вызовов функции <tex>\mathrm{get(u)}</tex> текущее значение <tex>\mathrm{R(PL(u))}</tex> возрастает.
Пусть <tex>m</tex> — количество вызовов операции <tex>\mathrm{get(u)}</tex>, <tex>n</tex> — количество вызовов операции <tex>\mathrm{union(v, u)}</tex>, и <tex>m\geqslant n</tex>.
Разделим все вершины на <tex>4</tex> типа:
Для первых двух типов вершин одна операция <tex>\mathrm{get(u)}</tex> работает за истинное время <tex>\mathrm{O(1)}</tex>, поэтому их суммарное время работы не превышает <tex>2\cdot m</tex>.
При каждом вложенном вызове функции <tex>\mathrm{get(u)}</tex> для вершин третьего типа ранг вершины по условию возрастает на до <tex>i^{\mathrm{R(u)}}</tex>. Ранг вершины может меняться в пределах от <tex>0</tex> до <tex>\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{O(m\cdot \log^* n)}</tex>.
