13
правок
Изменения
Нет описания правки
Пусть <tex> union(v_1,v_2) </tex> — процедура объединения двух множеств , содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,
а <tex> get(v) </tex> — поиск представителя множества, содержащего <tex> v </tex>.
Рассмотрим <tex> n </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (<tex> m > n </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>.Записав неравенство из первого пункта вдоль пути из второго пункта , получаем требуемое.
}}
Для 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>.
{{Теорема
#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
#Все остальные.
Обозначим эти классы <tex> T_1, T_2, T_3 </tex>.
<center>
+
{\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>
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>.
<
{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n
</tex> . </center>
Из первого утверждения и в силу использования сжатия путей следует,
что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из <tex>Т_3T_3 </tex>.
Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex>Т_3T_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}\log_2(n)} \limits {nx^{Rank} \over 2^{Rank} n}</tex>.</center>
При <tex> x < 2~</tex>:
{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n
\le
\sum_{Rank=0}^{log_{2}\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>.
