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

Материал из Викиконспекты
Перейти к: навигация, поиск

Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции ([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]1[/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] [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(\log^*n)[/math]).

Определение:
[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]m\geqslant n[/math], так как количество операций [math]\mathrm{union}[/math] не превосходит количество элементов множества [math]n[/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{get} [/math] следует:

  1. [math] \mathrm{R(L(v))}\gt \mathrm{R(v)} [/math].
  2. Между [math] v [/math] и [math] \mathrm{P(v)} [/math] существует путь вида: [math] 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(P(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]1[/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]\log^*_{i} \left (\log_2 n \right )[/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]

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=СНМ_(реализация_с_помощью_леса_корневых_деревьев)&oldid=50269»