13
правок
Изменения
Нет описания правки
Функция, обратная функции Аккермана <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> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.
Оценим стоимость операции <tex> get(v) </tex>.
Обозначим <tex> R(v) </tex> — ранг вершины, <tex>P(v)</tex> — представитель множества, содержащего <tex> v </tex>,
<tex> L(v) </tex> — отец вершины,
<tex> K(v) </tex> — количество вершин в поддереве, корнем которого является <tex> v </tex>.
{{Утверждение
|statement=
<tex> R(P(v)) > R(v) </tex>
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>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>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}
{{Утверждение
|statement=
<tex> R(v) = i \Rightarrow K(v) \ge 2^i </tex>
|proof=
Докажем по индукции:
Для 0 равенство очевидно.
Ранг вершины станет равным <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> R(v) \le \log_2(n) </tex>.
#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>.
{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
Разобьем наши ребра на три класса:
#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
#Все остальные.
Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.
Амортизационная стоимость
<center>
<tex>
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m
</tex>,
</center>
где <tex> {v \in get } </tex> означает, что ребро, начало которого находится в <tex> v </tex>, было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.
В силу того, что <tex>{\sum_{v:v \in get,v \in T_1} \limits 1} = O(1) </tex> получаем:
<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / m
</tex>.
</center>
Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>.
Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n))
</tex>.
</center>
Для того, чтобы <tex> \log^*_x(\log_2(n)) </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>.
Рассмотрим сумму
<center> <tex>
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1~/m
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex>. </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.
Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits }
1/n \le \sum_v \limits x^{R(v)} /n
</tex>.</center>
Из второго следствия второго утверждения следует:
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n \le \sum_{Rank=0}^{\log_2(n)} \limits {nx^{Rank} \over 2^{Rank} n}
</tex>.</center>
При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{\log_2(n)} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
\le
{ 2 \over 2-x } = O(1)
</tex>.</center>
Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}
==Ссылки==
