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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 69 промежуточных версий 19 участников)
Строка 1: Строка 1:
{{В разработке}}
+
Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции (<tex>\mathrm{get}</tex> и <tex>\mathrm{union}</tex>) выполняются в среднем за практически константное время.
Система непересекающихся множеств. Реализация с помощью леса корневых деревьев. (disjoint set union (DSU) или Union-Find)
 
 
 
 
==Реализация==
 
==Реализация==
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель - один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме элемента множества, хранится ссылка на "родителя".  
+
Каждое множество хранится в виде дерева. Элементы множества хранятся в вершинах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".  
  
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''union''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''get'').
+
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''<tex>\mathrm{union}</tex>''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''<tex>\mathrm{get}</tex>'').
  
Сама по себе такая реализация еще не дает выигрыша в скорости, в сравнении с [[СНМ(наивные_реализации)|наивными реализациями]], так как при неудачном стечении обстоятельств дерево может выродиться в линейный список и get будет работать за линейное время. Сильный выигрыш в скорости даст использование двух эвристик: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).
+
Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где <tex>\mathrm{get}</tex> будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализациями]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).
  
 
===Объединение по рангу===
 
===Объединение по рангу===
 
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.  
 
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.  
  
Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней границей высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен 1. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое, к какому подвешивать, но ранг объединенного дерева будет больше на 1.
+
Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен <tex>0</tex>. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на <tex>1</tex>.
  
 
===Сжатие пути===
 
===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''get'' и делает ее двухпроходной. Операция get вызывается для элемента ''x'' (''get(x)''), проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому подвесим их напрямую (изменим ссылки) к корню дерева и, таким образом уменьшим его высоту.
+
Эта эвристика несколько модифицирует операцию ''<tex>\mathrm{get}</tex>''. Операция <tex>\mathrm{get}</tex> вызывается для элемента <tex>x</tex>, проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и <tex>x</tex>. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция ''<tex>\mathrm{get}</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
  
 
==Асимптотика==
 
==Асимптотика==
Реализация системы непересекающихся множеств с помощью леса корневых деревьев дает следующие асимптотически оценки для операций:
+
:''см. также [[Анализ_реализации_с_ранговой_эвристикой|Анализ реализации с ранговой эвристикой]]''
{| class="wikitable" border = 1, style="text-align: right; margin-left: auto; margin-right: auto;"
+
 
|- bgcolor=#FFFFFF
+
{| class="wikitable" border = 1
! get              ||  a(m,n)
+
|-
 +
!Операция !! Истинное время !! Амортизированное время
 +
|- style = "text-align = center"
 +
| ''<tex>\mathrm{get}</tex>''                  || <tex>\mathrm{O(\log n)}</tex>        ||  <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex>
 +
|-
 +
| ''<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> является логарифмическим.
 +
 
 +
Будем доказывать данное свойство по индукции. Для <tex>k = 0</tex>, очевидно, в множестве содержится <tex>1</tex> вершина. Пусть для множеств ранга <tex>k - 1</tex> свойство выполняется. Как следует из ранговой эвристики, множество ранга <tex>k</tex> может получиться только при подвешивании множества ранга <tex>k - 1</tex> к множеству ранга <tex>k - 1</tex>. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.
 +
 
 +
===Функция Аккермана===
 +
 
 +
Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел <tex>m</tex> и <tex>n</tex>:
 +
 
 +
<tex>\mathrm{A(m, n)} = \begin{cases}
 +
2^n, & m = 1 \\
 +
2, & m > 1, n = 0 \\
 +
\mathrm{A(m - 1, A(m, n - 1))}, & m > 1, n > 0
 +
\end{cases} </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>
 
|-
 
|-
! union            || 1
+
! <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>
 
|-
 
|-
! m*get + n*union  || m*a(m,n) + n
+
! <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>
 
|}
 
|}
где m - общее количество операций, n - полное количество элементов, a(m, n) - функция, обратная к функции Аккермана - очень медленно растущая функция и практически для всех разумных значений не превышает 4, поэтому ее можно считать константой. Таким образом, при этой реализации время работы линейно зависит от количества операций.
 
  
==Ссылки==
+
Функция, обратная функции Аккермана <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> выполняется за константное время.
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств - описание этой реализации на habrahabr.ru]
+
 
* [http://ru.wikipedia.org/wiki/Функция_Аккермана  Функция Аккермана - Википедия]
+
===Анализ реализации с ранговой эвристикой===
 +
 
 +
Проведем анализ реализации с ранговой эвристикой. Будем доказывать, что амортизационная стоимость <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> 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>.
 +
Не теряя общности, будем считать, что <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{R(v)} </tex> — ранг вершины, <tex>\mathrm{P(v)}</tex> — представитель множества, содержащего <tex>\mathrm{v}</tex>,
 +
<tex> \mathrm{L(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{v}</tex> — представитель множества, то <tex>\mathrm{P(v)}=\mathrm{v}</tex> и <tex> \mathrm{R(P(v))} = \mathrm{R(v)} </tex>.
 +
 
 +
Иначе, из принципа работы функции <tex> \mathrm{union} </tex> следует:
 +
#<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=
 +
Докажем по индукции:
 +
 
 +
Для <tex>0</tex> равенство очевидно.
 +
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
 +
<tex>\mathrm{K(v)} \geqslant \mathrm{K(v_1)} + \mathrm{K(v_2)} \geqslant 2^{i-1}+2^{i-1} \geqslant 2^i </tex>.
 +
}}
 +
 
 +
Из последнего утверждения следует:
 +
 
 +
{{Утверждение
 +
|statement=
 +
<tex> \mathrm{R(v)} \leqslant \log_2n </tex>
 +
}}
 +
{{Утверждение
 +
|statement=
 +
Количество вершин ранга <tex> i \leqslant \dfrac{n}  {2^i} </tex>.
 +
|proof=
 +
Если бы это было не так, то просуммировав количество вершин всех рангов, мы получили бы число большее <tex>n</tex>. Это противоречит условию, по которому <tex>n</tex> — число всех вершин. Значит утверждение верно.
 +
}}
 +
 
 +
{{Теорема
 +
|statement=
 +
Амортизационная стоимость <tex> \mathrm{get} = \mathrm{O(\log^{*}n)}  </tex>
 +
|proof=
 +
 
 +
Рассмотрим все вызовы функции <tex>\mathrm{get(u)}</tex>. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина <tex>u</tex> не корень и не сын корня, то во время рекурсивных вызовов функции <tex>\mathrm{get(u)}</tex> текущее значение <tex>\mathrm{R(L(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> типа:
 +
 
 +
:1. <tex>u</tex> — корень. Таких вызовов <tex>\mathrm{get(u)}</tex> будет ровно <tex>m</tex>.
 +
:2. <tex>u</tex> — сын корня. Таких вызовов <tex>\mathrm{get(u)}</tex> будет не больше чем <tex>m</tex>.
 +
Оставшиеся вершины разделим на:
 +
:3. Быстро растущие вызовы — такие что <tex>\mathrm{R(P(u))} \geqslant i^{\mathrm{R(u)}}</tex>, где <tex>i</tex> — число из диапазона <tex dpi="150">e ^{\frac{1}{e}} < i < 2</tex> <tex dpi="150">(e ^{\frac{1}{e}}\approx </tex> <tex>1.44</tex><tex dpi="150">)</tex>.
 +
:4. Медленно растущие вызовы — <tex>\mathrm{R(P(u))} < i^{\mathrm{R(u)}}</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>.
 +
 
 +
Поскольку количество вершин с рангом <tex>k</tex> не превышает число <tex>\dfrac{n}{2^k}</tex>, то суммарное время работы медленно растущих вызовов равно
 +
<center>
 +
<tex dpi="150">\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)}</tex>
 +
</center>
 +
В итоге получаем, что суммарное время работы операции <tex>\mathrm{get(u)}</tex> равняется <tex>T = \mathrm{O(m)} + \mathrm{O(m\cdot \log^* n)} +\mathrm{O(n)} = \mathrm{O(m\cdot \log^*n + n)}</tex>.
 +
С учетом того факта что <tex>m\geqslant n</tex>, амортизированное время работы равно <tex>\mathrm{O(\log^* n)}</tex>.
 +
}}
 +
 
 +
== См. также ==
 +
* [[СНМ (списки с весовой эвристикой)]]
 +
* [[СНМ (наивные реализации)]]
 +
 
 +
==Источники информации==
 +
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств {{---}} описание этой реализации на habrahabr.ru]
 +
* [http://ru.wikipedia.org/wiki/Функция_Аккермана  Функция Аккермана {{---}} Википедия]
 +
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ —  Вильямс, 2010. - стр 589. — ISBN 978-5-8459-0857-4
  
== Литература ==
+
[[Категория: Дискретная математика и алгоритмы]]
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''' —  Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1.  (стр 589)
+
[[Категория: Структуры данных]]

Текущая версия на 19:12, 4 сентября 2022

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

  1. [math] \mathrm{R(L(v))}\gt \mathrm{R(v)} [/math].
  2. Между [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]

См. также

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