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>).
Для 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> T_1, T_2, T_3 </tex>.
<center>
</tex>
</center>
где <tex> {v \in get } </tex> означает , что ребро , начало которого находится в <tex> v </tex> , было пройдено во время выполнения текущего <tex> get </tex>.
Ребро <tex> v </tex> эквивалентно вершине, в которой оно начинается.
Во время <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))
