Изменения

Пусть <tex> union(v1v_1,v2v_2) </tex> — процедура объединения двух множеств содержащих <tex> v1 v_1 </tex> и <tex> v2 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>). Для удобства, не Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов корни поддеревьев и <tex> m > n </tex>представителей, то есть <tex> union(v1v_1,v2v_2) </tex> заменяем на <tex> union(get(v1v_1),get(v2v_2)) </tex>.

Тогда нам надо оценить Оценим стоимость операции <tex> get(v) </tex>. Обозначим <tex>R(v)</tex> - — ранг вершины,<tex>P(v)</tex> - — отец вершины,<tex>L(v) </tex> - — самый первый отец вершины, <tex> K(v) </tex> - — количество вершин в поддерева корнем которого является <tex> v </tex>

<tex> R(P(v))>R(v) </tex>

Из того как работает принципа работы функции <tex> get </tex> следует:1.#<tex> R(L(v))>R(v) </tex> 2. #Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида : <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow ... \dots \rightarrow P(v) </tex>Записав неравенство из первого пункта вдоль пути из второго пункта следует что <tex> R(P(v))>R(v) </tex> получаем требуемое.

<tex> R(v)=i \Rightarrow K(v) \ge 2^i </tex>

 Для 0 равенство очевидноеочевидно.Ранг вершины стает равным <tex> i </tex> при сливании объединении поддеревьев ранга <tex>i-1</tex>, отсюда следует:<tex>K(v) \ge K(v1v_1)+K(v2v_2) \ge 2^{i-1}+2^{i-1} \ge 2^i </tex>.

1. #<tex> R(v) \le \log_2(n) </tex> 2. #Количество вершин ранга <tex> i \le {n \over 2^i} </tex> 

Рассмотрим некоторое число <tex> x </tex> .

1.#Ведут в корень или в сына корня.

2.#<tex> R(P(v)) \ge x^{R(v)}</tex>

3. #Все остальные.

Обозначим эти классы <tex> T1T_1,T2T_2,T3 T_3 </tex>.

<center><tex>S= {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T1T_1} \limits 1} + {\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T3T_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> получаем:

В силу того что <texcenter>{\sum_{v:v \in get,v \in T1} \limits 1} = O(1) </tex> получаем: <center><tex> S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T2T_2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3T_3} \limits} 1/m </tex></center>

Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v1v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>

Из выше сказанного и первого следствия второго утверждения получаем что:<center> <tex> {\sum_{v:v \in get,v \in T2T_2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n)) </tex></center>

Рассмотрим сумму<center> <tex>{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3T_3} \limits} 1~/m < {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3T_3} \limits} 1/n </tex> </center> Из первого утверждения и того что происходит сжатие всилу использования сжатия путей следует , что <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из Т3Т_3.

Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе Т3Т_3.

<center><tex> {\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3T_3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T3T_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 T3T_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>.