СНМ (реализация с помощью леса корневых деревьев)

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

Реализация

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

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

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

Объединение по рангу

Эта эвристика аналогична весовой эвристике у связных списков. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.

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

Сжатие пути

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

Псевдокод

Для реализации СНМ будем поддерживать следующие массивы: [math]p[x][/math] — массив "родителей", [math]r[x][/math] — массив рангов.

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

Также возможна реализация функции [math]\mathrm{get}[/math] без использования [math]\mathrm{O(\log n)}[/math] дополнительной памяти.

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

Асимптотика

см. также Анализ реализации с ранговой эвристикой

Операция	Истинное время	Амортизированное время
[math]\mathrm{get}[/math]	[math]\mathrm{O(\log n)}[/math]	[math]\mathrm{O(\mathrm{\alpha(m, n)})}[/math]
[math]\mathrm{union}[/math]	[math]\mathrm{O(\log n)}[/math]	[math]\mathrm{O(\mathrm{\alpha(m, n)})}[/math]

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

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

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

Функция Аккермана

Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел [math]m[/math] и [math]n[/math]:

[math]\mathrm{A(m, n)} = \begin{cases} 2^n, & m = 1 \\ 2, & m \gt 1, n = 0 \\ \mathrm{A(m - 1, A(m, n - 1))}, & m \gt 1, n \gt 0 \end{cases} [/math]

Таблица значений функции Аккермана:

[math]\mathbf{m \backslash n}[/math]	[math]\mathbf{0}[/math]	[math]\mathbf{1}[/math]	[math]\mathbf{2}[/math]	[math]\mathbf{3}[/math]	[math]\mathbf{4}[/math]	[math]\mathbf{5}[/math]
[math]\mathbf{1}[/math]	[math]1[/math]	[math]2[/math]	[math]4[/math]	[math]8[/math]	[math]16[/math]	[math]32[/math]
[math]\mathbf{2}[/math]	[math]2[/math]	[math]4[/math]	[math]16[/math]	[math]65536[/math]	[math]2^{2^{16}}[/math]	[math]2^{2^{2^{16}}}[/math]
[math]\mathbf{3}[/math]	[math]2[/math]	[math]16[/math]	[math]\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}[/math]	[math]\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{A(3, 2)}[/math]	[math]\cdots[/math]	[math]\cdots[/math]
[math]\mathbf{4}[/math]	[math]2[/math]	[math]\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}[/math]	[math]\cdots[/math]	[math]\cdots[/math]	[math]\cdots[/math]	[math]\cdots[/math]

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

Анализ реализации с ранговой эвристикой

Проведем анализ реализации с ранговой эвристикой. Будем доказывать, что амортизационная стоимость [math] \mathrm{get} = \mathrm{O(\log^{*}n)} [/math].

Определение:

Итерированный логарифм (англ. Iterated logarithm) [math]\mathrm{\log^*n}[/math] — минимальное число логарифмирований [math]n[/math], необходимое для получения значения, не превосходящего [math]1[/math].

Пример: [math]\mathrm{\log^*_2 16} = 3[/math]

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

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

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

[math] \mathrm{R(P(v))} \geqslant \mathrm{R(v)} [/math]

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

[math] \mathrm{R(v)} = i \Rightarrow {\mathrm{K(v)}} \geqslant {2^i}[/math]

[math]\triangleright[/math]

Докажем по индукции: Для [math]0[/math] равенство очевидно. Ранг вершины станет равным [math] i [/math] при объединении поддеревьев ранга [math]i-1[/math], следовательно: [math]\mathrm{K(v)} \geqslant \mathrm{K(v_1)} + \mathrm{K(v_2)} \geqslant 2^{i-1}+2^{i-1} \geqslant 2^i [/math].

[math]\triangleleft[/math]

Из последнего утверждения следует:

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

[math] \mathrm{R(v)} \leqslant \log_2n [/math]

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

Количество вершин ранга [math] i \leqslant \dfrac{n} {2^i} [/math].

[math]\triangleright[/math]

Если бы это было не так, то просуммировав количество вершин всех рангов, мы получили бы число большее [math]n[/math]. Это противоречит условию, по которому [math]n[/math] — число всех вершин. Значит утверждение верно.

[math]\triangleleft[/math]

Теорема:

Амортизационная стоимость [math] \mathrm{get} = \mathrm{O(\log^{*}n)} [/math]

Доказательство:

[math]\triangleright[/math]

Рассмотрим все вызовы функции [math]\mathrm{get(u)}[/math]. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина [math]u[/math] не корень и не сын корня, то во время рекурсивных вызовов функции [math]\mathrm{get(u)}[/math] текущее значение [math]\mathrm{R(L(u))}[/math] возрастает. Пусть [math]m[/math] — количество вызовов операции [math]\mathrm{get(u)}[/math], [math]n[/math] — количество вызовов операции [math]\mathrm{union(v, u)}[/math], и [math]m\geqslant n[/math]. Разделим все вершины на [math]4[/math] типа: 1. [math]u[/math] — корень. Таких вызовов [math]\mathrm{get(u)}[/math] будет ровно [math]m[/math]. 2. [math]u[/math] — сын корня. Таких вызовов [math]\mathrm{get(u)}[/math] будет не больше чем [math]m[/math]. Оставшиеся вершины разделим на: 3. Быстро растущие вызовы — такие что [math]\mathrm{R(P(u))} \geqslant i^{\mathrm{R(u)}}[/math], где [math]i[/math] — число из диапазона [math]e ^{\frac{1}{e}} \lt i \lt 2[/math] [math](e ^{\frac{1}{e}}\approx [/math] [math]1.44[/math][math])[/math]. 4. Медленно растущие вызовы — [math]\mathrm{R(P(u))} \lt i^{\mathrm{R(u)}}[/math]. Для первых двух типов вершин одна операция [math]\mathrm{get(u)}[/math] работает за истинное время [math]\mathrm{O(1)}[/math], поэтому их суммарное время работы не превышает [math]2\cdot m[/math]. При каждом вложенном вызове функции [math]\mathrm{get(u)}[/math] для вершин третьего типа ранг по условию возрастает до [math]i^{\mathrm{R(u)}}[/math]. Ранг вершины может меняться в пределах от [math]0[/math] до [math]\log_2n[/math]. Значит количество рекурсивных вызовов равняется количеству возведений в степень [math]\mathrm{R(n)}[/math] числа [math]i[/math], необходимых для достижения числа [math]\log_2n[/math]. Или что то же самое, количеству логарифмирований по основанию [math]i[/math] числа [math]\log_2n[/math] для получения [math]1[/math] и еще одному логарифмированию для получения [math]0[/math]. Количество логарифмирований описывается функцией [math]\log^*_{i} \left (\log_2 n \right )[/math]. С учетом последнего логарифмирования формула примет вид [math]\log^*_{i}n[/math]. Тогда время работы [math]m[/math] быстро растущих вызовов равно [math]\mathrm{O(m\cdot \log^* n)}[/math]. Поскольку количество вершин с рангом [math]k[/math] не превышает число [math]\dfrac{n}{2^k}[/math], то суммарное время работы медленно растущих вызовов равно [math]\sum_u \limits i^{\mathrm{R(u)}}=\sum_{k=0}^{\log n} \limits \sum_{\mathrm{{R(u)}=k}} \limits i^k \leqslant \sum_{k=0}^{\log n} \limits i^k \cdot \frac{n}{2^k} \leqslant n \cdot \sum_{k=0}^{\log n} \limits \dfrac{i^k}{2^k} = \mathrm{O(n)}[/math] В итоге получаем, что суммарное время работы операции [math]\mathrm{get(u)}[/math] равняется [math]T = \mathrm{O(m)} + \mathrm{O(m\cdot \log^* n)} +\mathrm{O(n)} = \mathrm{O(m\cdot \log^*n + n)}[/math]. С учетом того факта что [math]m\geqslant n[/math], амортизированное время работы равно [math]\mathrm{O(\log^* n)}[/math].

[math]\triangleleft[/math]

См. также

• СНМ (списки с весовой эвристикой)
• СНМ (наивные реализации)

Источники информации

• Система непересекающихся множеств — описание этой реализации на habrahabr.ru
• Функция Аккермана — Википедия
• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - стр 589. — ISBN 978-5-8459-0857-4