Пусть <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> 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> следует: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> , получаем требуемое.
}}
{{Утверждение
|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(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>.
{{Теорема
|statement=
Амортизационная стоимость <tex> get = O(\log^{*}(n)) </tex>
|proof=
Рассмотрим некоторое число <tex> x </tex> .
Разобьем наши ребра на три класса:
1.#Ведут в корень или в сына корня.#<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>.
2Рассмотрим сумму<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(vx))</tex>=x^{R(v)}cтрого увеличивается при переходе по ребру из <tex> T_3 </tex>.
3. Все остальныеКак максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_3 </tex>.
Обозначим эти классы <texcenter> T1,T2,T3 </tex>Амортизированная стоимость<tex> S= {\sum_{get} \limits} (~ {\sum_{u v:v \in get,u v \in T1T_3} \limits } 1} + /n = {\sum_v \limits ~\sum_{u \get: in ~ this ~ get,u ~ v \in T2T_3} \limits } 1} + {/n \sum_{u le \in get,u \in T3} sum_v \limits 1} x^{R(v) / m </tex> , где <tex> {u \in get } </tex> означает что ребро <tex> u n</tex> было пройдено во время выполнения текущего <tex> get .</texcenter> .
В силу того что Из второго следствия второго утверждения следует:<tex>{\sum_{u \in get,u \in T1} \limits 1} = O(1) </texcenter> получаем <tex> S = O(1) + {\sum_{get} \limits}( ~ {\sum_{u v:v \in get,u v \in T2T_3} \limits} 1)/m+ {n \le \sum_{getRank=0}^{\log_2(n)} \limits{nx^{Rank} ( {\sum_over 2^{u \in get,u \in T3Rank} \limitsn} 1)/m </tex> .</center>
После K ребер из второго класса При <tex> x < 2~</tex> R:<center><tex>{\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n\le\sum_{Rank=0}^{\log_2(v1n) } \ge x^limits {x^{.Rank} \over 2^{.^Rank}}\le\sum_{.Rank=0}^\infty \limits {x^{R(v)}}Rank}\over 2^{Rank}}\le{ 2 \over 2-x } = O(1)</tex>.</center>
Из выше сказанного и первого следствия второй леммы получаем что <tex> {\sum_{u \in get,u \in T2} \limits} = log^*_x(log_2(n)) = O(log^*(n)) </tex> . Для того чтоб <tex> log^*_x </tex> существовал необходимо чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>
Рассмотрим сумму Итак <tex>{\sum_{get} \limits} S = O( {\sum_{u \in get,u \in T3} \limits} 1)/m < {+ O(\sum_{get} \limits} log^*(x)) + O( {\sum_{u \in get,u \in T3} \limits} 1)/n </tex> Из первого утверждения следует <tex> R= O(P\log^*(x)) </tex> только увеличивается при переходе по ребру из Т3.Как максимум через В силу того, что интервал <tex> x^R(k1,45...2) </tex> переходов ребро перестанет появлятся в классе Т3не пустой, теорема доказана.
}}
== Ссылки ==
* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]
