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

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

Реализация

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

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

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

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

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

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

Сжатие пути

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

Псевдокод

Для реализации СНМ будем поддерживать следующие массивы:

[math]p[x][/math] — массив "родителей".

[math]r[x][/math] — массив рангов.

get

get(x)
   if p[x] != x
      p[x] = get(p[x])
   return p[x]

union

union(x, y)
   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

Асимптотика

см. также Анализ реализации с ранговой эвристикой
Операция Истинное время Амортизированное время
get [math]O(\log n)[/math] [math]O(\alpha(m, n))[/math]
union [math]O(1)[/math] [math]O(1)[/math]
  • m — общее количество операций
  • n — полное количество элементов
  • [math]\alpha(m, n)[/math] — функция, обратная к функции Аккермана (если [math]m[/math] операций get и [math]n[/math] элементов).

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

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

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

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

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

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

[math]m \backslash n[/math] 0 1 2 3 4 5
1 1 2 4 8 16 32
2 2 4 16 65536 [math]2^{2^{16}}[/math] [math]2^{2^{2^{16}}}[/math]
3 2 16 [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]
4 2 [math]\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}[/math] [math]\cdots[/math] [math]\cdots[/math] [math]\cdots[/math] [math]\cdots[/math]

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

Ссылки

Литература

  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1. (стр 589)