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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Анализ реализации с ранговой эвристикой)
Строка 1: Строка 1:
Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции (get и union) выполняются в среднем за практически константное время.
+
Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции (<tex>\mathrm{get}</tex> и <tex>\mathrm{union}</tex>) выполняются в среднем за практически константное время.
 
==Реализация==
 
==Реализация==
 
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".  
 
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".  
  
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''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).
  
 
===Объединение по рангу===
 
===Объединение по рангу===
Строка 13: Строка 13:
  
 
===Сжатие пути===
 
===Сжатие пути===
Эта эвристика несколько модифицирует операцию ''get''. Операция get вызывается для элемента ''x'', проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция ''get'' становится двухпроходной.
+
Эта эвристика несколько модифицирует операцию ''<tex>\mathrm{get}</tex>''. Операция <tex>\mathrm{get}</tex> вызывается для элемента ''x'', проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и ''x''. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция ''<tex>\mathrm{get}</tex>'' становится двухпроходной.
  
 
===Псевдокод===
 
===Псевдокод===
Строка 47: Строка 47:
 
!Операция !! Истинное время !! Амортизированное время
 
!Операция !! Истинное время !! Амортизированное время
 
|- style = "text-align = center"
 
|- style = "text-align = center"
| ''get''                  || <tex>O(\log n)</tex>        ||  <tex>O(\alpha(m, n))</tex>  
+
| ''<tex>\mathrm{get}</tex>''                  || <tex>\mathrm{O(\log n)}</tex>        ||  <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex>  
 
|-
 
|-
| ''union''                || <tex>O(1)</tex>            ||  <tex>O(1)</tex>
+
| ''<tex>\mathrm{union}</tex>''                || <tex>\mathrm{O(1)}</tex>            ||  <tex>\mathrm{O(1)}</tex>
 
|}
 
|}
 
* m {{---}} общее количество операций
 
* m {{---}} общее количество операций
Строка 55: Строка 55:
 
* n {{---}} полное количество элементов
 
* n {{---}} полное количество элементов
  
* <tex>\alpha(m, n)</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций get и <tex>n</tex> элементов).
+
* <tex>\mathrm{\alpha(m, n)}</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций get и <tex>n</tex> элементов).
  
Докажем, что если глубина множества (т.е. его ранг) равна k, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с n элементами есть <tex>O(\log n)</tex>, а значит и время работы операции get является логарифмическим.
+
Докажем, что если глубина множества (т.е. его ранг) равна k, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с n элементами есть <tex>\mathrm{O(\log n)}</tex>, а значит и время работы операции <tex>\mathrm{get}</tex> является логарифмическим.
  
 
Будем доказывать данное свойство по индукции. Для k = 0, очевидно, в множестве содержится 1 вершина. Пусть для множеств ранга k - 1 свойство выполняется. Как следует из ранговой эвристики, множество ранга k может получиться только при подвешивании множества ранга k - 1 к множеству ранга k - 1. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.
 
Будем доказывать данное свойство по индукции. Для k = 0, очевидно, в множестве содержится 1 вершина. Пусть для множеств ранга k - 1 свойство выполняется. Как следует из ранговой эвристики, множество ранга k может получиться только при подвешивании множества ранга k - 1 к множеству ранга k - 1. Но тогда из предположения индукции в новом множестве действительно будет <tex>2^k</tex> вершин, что и требовалось доказать.
Строка 65: Строка 65:
 
Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел <tex>m</tex> и <tex>n</tex>:
 
Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел <tex>m</tex> и <tex>n</tex>:
  
<tex>A(m, n) = \begin{cases}
+
<tex>\mathrm{A(m, n)} = \begin{cases}
 
  2^n, & m = 1 \\
 
  2^n, & m = 1 \\
 
  2, & m > 1, n = 0 \\
 
  2, & m > 1, n = 0 \\
  A(m - 1, A(m, n - 1)), & m > 1, n > 0
+
  \mathrm{A(m - 1, A(m, n - 1))}, & m > 1, n > 0
 
\end{cases} </tex>
 
\end{cases} </tex>
  
Строка 86: Строка 86:
 
|}
 
|}
  
Функция, обратная функции Аккермана <tex>\alpha(m, n)</tex> равна минимальному <tex>i</tex> такому, что <tex>A \left (i, \left [\frac{m}{n} \right ] \right ) \geq \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция get выполняется за константное время.
+
Функция, обратная функции Аккермана <tex>\mathrm{\alpha(m, n)}</tex> равна минимальному <tex>i</tex> такому, что <tex>\mathrm{A \left (i, \left [\frac{m}{n} \right ] \right )} \geq \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция get выполняется за константное время.
  
  
Строка 92: Строка 92:
  
 
Проведем анализ реализации с ранговой эвристикой, будем доказывать более слабую оценку (итерированный логарифм).
 
Проведем анализ реализации с ранговой эвристикой, будем доказывать более слабую оценку (итерированный логарифм).
Рассмотрим <tex> a </tex> операций <tex> union  </tex> и  <tex> b </tex> операций  <tex> get </tex> (<tex> b > a </tex>).
+
Рассмотрим <tex> a </tex> операций <tex> \mathrm{union} </tex> и  <tex> b </tex> операций  <tex> \mathrm{get} </tex> (<tex> b > a </tex>).
 
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
 
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на  <tex> union(get(v_1),get(v_2)) </tex>.
+
то есть <tex> \mathrm{union(v_1,v_2)} </tex> заменяем на  <tex> \mathrm{union(get(v_1),get(v_2))} </tex>.
  
Оценим стоимость операции <tex> get(v) </tex>.   
+
Оценим стоимость операции <tex> \mathrm{get(v)} </tex>.   
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
+
Обозначим <tex> \mathrm{R(v)} </tex> — ранг вершины, <tex>\mathrm{P(v)}</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
+
<tex> \mathrm{L(v)} </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.
+
<tex> \mathrm{K(v)} </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.
  
 
{{Утверждение  
 
{{Утверждение  
 
|statement=
 
|statement=
<tex> R(P(v)) > R(v) </tex>
+
<tex> \mathrm{R(P(v))} > \mathrm{R(v)} </tex>
 
|proof=
 
|proof=
Из принципа работы функции <tex> get </tex> следует:
+
Из принципа работы функции <tex> \mathrm{get} </tex> следует:
#<tex> R(L(v))>R(v) </tex>.
+
#<tex> \mathrm{R(L(v))}>\mathrm{R(v)} </tex>.
#Между  <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>.
+
#Между  <tex> v </tex> и <tex> \mathrm{P(v)} </tex> существует путь вида: <tex> v \rightarrow \mathrm{L(v)} \rightarrow \mathrm{L(L(v))} \rightarrow \dots \rightarrow \mathrm{P(v)} </tex>.
 
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
 
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
 
}}
 
}}
Строка 113: Строка 113:
 
{{Утверждение  
 
{{Утверждение  
 
|statement=
 
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
+
<tex> \mathrm{R(v)} = i \Rightarrow \mathrm{K(v)} \geqslant 2^i </tex>
 
|proof=
 
|proof=
 
Докажем по индукции:  
 
Докажем по индукции:  
Строка 119: Строка 119:
 
Для 0 равенство очевидно.
 
Для 0 равенство очевидно.
 
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
 
Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, следовательно:
<tex>K(v) \ge K(v_1) + K(v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </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>.
 
}}
 
}}
  
 
Из последнего утверждения следует:
 
Из последнего утверждения следует:
  
#<tex> R(v) \le \log_2a </tex>.
+
#<tex> \mathrm{R(v)} \le \log_2a </tex>.
 
#Количество вершин ранга <tex> i \le {a \over 2^i} </tex>.
 
#Количество вершин ранга <tex> i \le {a \over 2^i} </tex>.
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}a)  </tex>
+
Амортизационная стоимость <tex> \mathrm{get} = \mathrm{O(\log^{*}a)} </tex>
 
|proof=
 
|proof=
 
Рассмотрим некоторое число <tex> x </tex>.
 
Рассмотрим некоторое число <tex> x </tex>.
Строка 135: Строка 135:
  
 
#Ведут в корень или в сына корня.
 
#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
+
#<tex> \mathrm{R(P(v))} \geqslant x^{\mathrm{R(v)}}</tex>.
 
#Все остальные.
 
#Все остальные.
  
Строка 144: Строка 144:
 
<center>
 
<center>
 
<tex>
 
<tex>
S =  {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
S =  {\sum_{\mathrm{get}} \limits} ({\sum_{v:v \in \mathrm{get},v \in T_1} \limits 1}
 
+
 
+
{\sum_{v:v \in get,v \in T_2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1}  ) /  b  
+
{\sum_{v:v \in \mathrm{get},v \in T_2} \limits 1} + {\sum_{v: \in \mathrm{get},v \in T_3} \limits 1}  ) /  b  
 
</tex>,
 
</tex>,
 
</center>
 
</center>
где <tex>  {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.  
+
где <tex>  {v \in \mathrm{get} } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> \mathrm{get} </tex>.  
 
Ребро <tex> v </tex>  эквивалентно вершине, в которой оно начинается.
 
Ребро <tex> v </tex>  эквивалентно вершине, в которой оно начинается.
  
В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:
+
В силу того, что <tex>{\sum_{v:v \in \mathrm{get},v \in T_1} \limits 1} = \mathrm{O(1)} </tex> получаем:
  
 
<center>
 
<center>
 
<tex>
 
<tex>
S = O(1) +  {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/b+ {\sum_{get} \limits} ~  {\sum_{v:v \in get,v \in T_3} \limits} 1 / b
+
S = \mathrm{O(1)} +  {\sum_{\mathrm{get}} \limits} ~ {\sum_{v:v \in \mathrm{get},v \in T_2} \limits} 1/b+ {\sum_{\mathrm{get}} \limits} ~  {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1 / b
 
</tex>.
 
</tex>.
 
</center>
 
</center>
  
Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>.
+
Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> \mathrm{R(v_1)} \geqslant x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>.
  
 
Из выше сказанного и первого следствия второго утверждения получаем, что:
 
Из выше сказанного и первого следствия второго утверждения получаем, что:
 
<center>
 
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits}  \le \log^*_x(\log_2a) = O(\log^*a)
+
<tex> {\sum_{v:v \in \mathrm{get},v \in T_2} \limits}  \le \mathrm{\log^*_x(\log_2a)} = \mathrm{O(\log^*a)}
 
</tex>.
 
</tex>.
 
</center>
 
</center>
  
Для того, чтобы <tex> \log^*_x(\log_2a) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.
+
Для того, чтобы <tex> \mathrm{\log^*_x(\log_2a)} </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.
  
  
 
Рассмотрим сумму
 
Рассмотрим сумму
 
<center> <tex>
 
<center> <tex>
{\sum_{get} \limits} ~  {\sum_{v:v \in get,v \in T_3} \limits} 1/b
+
{\sum_{\mathrm{get}} \limits} ~  {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/b
 
  <  
 
  <  
  {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/a  
+
  {\sum_{\mathrm{get}} \limits} ~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a  
 
</tex>. </center>  
 
</tex>. </center>  
 
Из первого утверждения и в силу использования сжатия путей следует,
 
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.
+
что <tex> \mathrm{R(P(x))}</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.
  
Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.
+
Как максимум через <tex> x^{\mathrm{R(k)}} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.
  
 
<center><tex>
 
<center><tex>
{\sum_{get} \limits}~  {\sum_{v:v \in get,v \in T_3} \limits} 1/a = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits  }  
+
{\sum_{\mathrm{get}} \limits}~  {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a = {\sum_v \limits ~\sum_{\mathrm{get}: in ~ this ~ \mathrm{get} ~ v \in T_3} \limits  }  
   1/a \le \sum_v \limits x^{R(v)} /a
+
   1/a \le \sum_v \limits x^{\mathrm{R(v)}} /a
 
</tex>.</center>
 
</tex>.</center>
  
 
Из второго следствия второго утверждения следует:
 
Из второго следствия второго утверждения следует:
 
<center> <tex>  
 
<center> <tex>  
{\sum_{get} \limits}~  {\sum_{v:v \in get,v \in T_3} \limits} 1/a \le  \sum_{Rank=0}^{\log_2a} \limits {ax^{Rank} \over 2^{Rank} a}
+
{\sum_{\mathrm{get}} \limits}~  {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a \le  \sum_{Rank=0}^{\log_2a} \limits {ax^{Rank} \over 2^{Rank} a}
 
</tex>.</center>
 
</tex>.</center>
  
 
При  <tex> x < 2~</tex>:
 
При  <tex> x < 2~</tex>:
 
<center><tex>
 
<center><tex>
{\sum_{get} \limits}~  {\sum_{v:v \in get,v \in T_3} \limits} 1/a
+
{\sum_{\mathrm{get}} \limits}~  {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a
 
\le
 
\le
 
\sum_{Rank=0}^{\log_2a} \limits {x^{Rank} \over 2^{Rank}}
 
\sum_{Rank=0}^{\log_2a} \limits {x^{Rank} \over 2^{Rank}}
Строка 200: Строка 200:
 
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
 
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
 
\le
 
\le
{ 2 \over 2-x } = O(1)
+
{ 2 \over 2-x } = \mathrm{O(1)}
 
</tex>.</center>  
 
</tex>.</center>  
  
  
Итак <tex> S = O(1) + O(\log^*x) + O(1) = O(\log^*x) </tex>.
+
Итак <tex> S = \mathrm{O(1)} + \mathrm{O(\log^*x)} + \mathrm{O(1)} = \mathrm{O(\log^*x)} </tex>.
 
В силу того, что интервал (1.45; 2) не пустой, теорема доказана.  
 
В силу того, что интервал (1.45; 2) не пустой, теорема доказана.  
 
}}
 
}}

Версия 15:15, 16 апреля 2015

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

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

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

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

Сжатие пути

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

Псевдокод

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

[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

Асимптотика

см. также Анализ реализации с ранговой эвристикой
Операция Истинное время Амортизированное время
[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(1)}[/math] [math]\mathrm{O(1)}[/math]
  • m — общее количество операций
  • n — полное количество элементов
  • [math]\mathrm{\alpha(m, n)}[/math] — функция, обратная к функции Аккермана (если [math]m[/math] операций get и [math]n[/math] элементов).

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

Будем доказывать данное свойство по индукции. Для k = 0, очевидно, в множестве содержится 1 вершина. Пусть для множеств ранга k - 1 свойство выполняется. Как следует из ранговой эвристики, множество ранга k может получиться только при подвешивании множества ранга k - 1 к множеству ранга k - 1. Но тогда из предположения индукции в новом множестве действительно будет [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]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]\mathrm{\alpha(m, n)}[/math] равна минимальному [math]i[/math] такому, что [math]\mathrm{A \left (i, \left [\frac{m}{n} \right ] \right )} \geq \log n[/math]. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция get выполняется за константное время.


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

Проведем анализ реализации с ранговой эвристикой, будем доказывать более слабую оценку (итерированный логарифм). Рассмотрим [math] a [/math] операций [math] \mathrm{union} [/math] и [math] b [/math] операций [math] \mathrm{get} [/math] ([math] b \gt a [/math]). Не теряя общности, будем считать, что [math] 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] v [/math], [math] \mathrm{L(v)} [/math] — отец вершины, [math] \mathrm{K(v)} [/math] — количество вершин в поддереве, корнем которого является [math] v [/math].

Утверждение:
[math] \mathrm{R(P(v))} \gt \mathrm{R(v)} [/math]
[math]\triangleright[/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]

Докажем по индукции:

Для 0 равенство очевидно. Ранг вершины станет равным [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]

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

  1. [math] \mathrm{R(v)} \le \log_2a [/math].
  2. Количество вершин ранга [math] i \le {a \over 2^i} [/math].
Теорема:
Амортизационная стоимость [math] \mathrm{get} = \mathrm{O(\log^{*}a)} [/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим некоторое число [math] x [/math]. Разобьем наши ребра на три класса:

  1. Ведут в корень или в сына корня.
  2. [math] \mathrm{R(P(v))} \geqslant x^{\mathrm{R(v)}}[/math].
  3. Все остальные.

Обозначим эти классы [math] T_1, T_2, T_3 [/math].

Амортизационная стоимость

[math] S = {\sum_{\mathrm{get}} \limits} ({\sum_{v:v \in \mathrm{get},v \in T_1} \limits 1} + {\sum_{v:v \in \mathrm{get},v \in T_2} \limits 1} + {\sum_{v: \in \mathrm{get},v \in T_3} \limits 1} ) / b [/math],

где [math] {v \in \mathrm{get} } [/math] означает, что ребро, начало которого находится в [math] v [/math], было пройдено во время выполнения текущего [math] \mathrm{get} [/math]. Ребро [math] v [/math] эквивалентно вершине, в которой оно начинается.

В силу того, что [math]{\sum_{v:v \in \mathrm{get},v \in T_1} \limits 1} = \mathrm{O(1)} [/math] получаем:

[math] S = \mathrm{O(1)} + {\sum_{\mathrm{get}} \limits} ~ {\sum_{v:v \in \mathrm{get},v \in T_2} \limits} 1/b+ {\sum_{\mathrm{get}} \limits} ~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1 / b [/math].

Во время [math] get [/math] после прохождения K ребер из второго класса [math] \mathrm{R(v_1)} \geqslant x^{x^{.^{.^{.^{x^{R(v)}}}}}} [/math].

Из выше сказанного и первого следствия второго утверждения получаем, что:

[math] {\sum_{v:v \in \mathrm{get},v \in T_2} \limits} \le \mathrm{\log^*_x(\log_2a)} = \mathrm{O(\log^*a)} [/math].

Для того, чтобы [math] \mathrm{\log^*_x(\log_2a)} [/math] существовал необходимо, чтобы [math] x \gt e ^{ 1 /e } \approx 1,44 [/math].


Рассмотрим сумму

[math] {\sum_{\mathrm{get}} \limits} ~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/b \lt {\sum_{\mathrm{get}} \limits} ~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a [/math].

Из первого утверждения и в силу использования сжатия путей следует, что [math] \mathrm{R(P(x))}[/math] cтрого увеличивается при переходе по ребру из [math] T_3 [/math].

Как максимум через [math] x^{\mathrm{R(k)}} [/math] переходов ребро перестанет появляться в классе [math] T_3 [/math].

[math] {\sum_{\mathrm{get}} \limits}~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a = {\sum_v \limits ~\sum_{\mathrm{get}: in ~ this ~ \mathrm{get} ~ v \in T_3} \limits } 1/a \le \sum_v \limits x^{\mathrm{R(v)}} /a [/math].

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

[math] {\sum_{\mathrm{get}} \limits}~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a \le \sum_{Rank=0}^{\log_2a} \limits {ax^{Rank} \over 2^{Rank} a} [/math].

При [math] x \lt 2~[/math]:

[math] {\sum_{\mathrm{get}} \limits}~ {\sum_{v:v \in \mathrm{get},v \in T_3} \limits} 1/a \le \sum_{Rank=0}^{\log_2a} \limits {x^{Rank} \over 2^{Rank}} \le \sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}} \le { 2 \over 2-x } = \mathrm{O(1)} [/math].


Итак [math] S = \mathrm{O(1)} + \mathrm{O(\log^*x)} + \mathrm{O(1)} = \mathrm{O(\log^*x)} [/math].

В силу того, что интервал (1.45; 2) не пустой, теорема доказана.
[math]\triangleleft[/math]

Ссылки

Литература

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