Изменения

Пусть <tex>Runion(v_1,v_2) </tex> — процедура объединения двух множеств, содержащих <tex> v_1 </tex> и <tex> v_2 </tex>,а <tex> get(v)</tex> - ранг вершины— поиск представителя множества,содержащего <tex> v </tex>.Рассмотрим <tex>Pn </tex> операций <tex> union </tex> и <tex> m </tex> операций <tex> get </tex> (v<tex> m > n </tex>).Не теряя общности, будем считать, что <tex> union </tex> - отец вершиныпринимает в качестве аргументов представителей,то есть <tex>Lunion(vv_1,v_2) </tex> - первой заменяем на <tex> union(get(v_1),get(v_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>. {{Утверждение

Предположим на секундуДокажем по индукции:  Для 0 равенство очевидно.Ранг вершины станет равным <tex> i </tex> при объединении поддеревьев ранга <tex>i-1</tex>, что следовательно:<tex>K(v) \sum a_nge 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>a_ni \le {n \over 2^- i} </tex>. {{Теорема|statement=Амортизационная стоимость <tex> get = a_nO(\log^{*}(n)) </tex>|proof=Рассмотрим некоторое число <tex> x </tex>.Разобьем наши ребра на три класса: #Ведут в корень или в сына корня.#<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} + - a_n{\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(\sum a_nlog_2(n)) </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~/m < {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T_3} \limits} 1/n </tex>. Тогда</center> Из первого утверждения и в силу использования сжатия путей следует, что <tex> R(P(x))</tex> cтрого увеличивается при переходе по линености рядовребру из <tex> T_3 </tex>. Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе <tex> T_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(n)} \limits {nx^{Rank} \over 2^{Rank} n}</tex>|a_n| .</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= a_n0}^\infty \limits {x^{Rank} \over 2^{Rank}}\le{ 2 \over 2-x } = O(1)</tex>.</center>   Итак <tex> S = O(1) + O(\log^*(x)) + a_nO(1) = O(\log^-*(x)) </tex>.В силу того, начнёт сходиться и ряд что интервал <tex>\sum |a_n|(1,45...2) </tex>. Противоречиене пустой, теорема доказана.