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 a </tex> операций <tex> union </tex> и <tex> m b </tex> операций <tex> get </tex> (<tex> m b > n a </tex>).
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
то есть <tex> union(v_1,v_2) </tex> заменяем на <tex> union(get(v_1),get(v_2)) </tex>.
Из последнего утверждения следует:
#<tex> R(v) \le \log_2(n) log_2a </tex>.#Количество вершин ранга <tex> i \le {n a \over 2^i} </tex>.
{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)a) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex>.
S = {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T_1} \limits 1}
+
{\sum_{v:v \in get,v \in T2T_2} \limits 1} + {\sum_{v: \in get,v \in T_3} \limits 1} ) / m b
</tex>,
</center>
<center>
<tex>
S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_2} \limits} 1/mb+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1 / mb
</tex>.
</center>
Из выше сказанного и первого следствия второго утверждения получаем, что:
<center>
<tex> {\sum_{v:v \in get,v \in T_2} \limits} \le \log^*_x(\log_2(n)log_2a) = O(\log^*(n)a)
</tex>.
</center>
Для того, чтобы <tex> \log^*_x(\log_2(n)log_2a) </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~/mb
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n a
</tex>. </center>
Из первого утверждения и в силу использования сжатия путей следует,
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n a = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T_3} \limits } 1/n a \le \sum_v \limits x^{R(v)} /na
</tex>.</center>
Из второго следствия второго утверждения следует:
<center> <tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n a \le \sum_{Rank=0}^{\log_2(n)log_2a} \limits {nxax^{Rank} \over 2^{Rank} na}
</tex>.</center>
При <tex> x < 2~</tex>:
<center><tex>
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3T_3} \limits} 1/na
\le
\sum_{Rank=0}^{\log_2(n)log_2a} \limits {x^{Rank} \over 2^{Rank}}
\le
\sum_{Rank=0}^\infty \limits {x^{Rank} \over 2^{Rank}}
Итак <tex> S = O(1) + O(\log^*(x)) + O(1) = O(\log^*(x)) </tex>.
В силу того, что интервал <tex> (1,45...2) </tex> не пустой, теорема доказана.
}}
