Изменения
Нет описания правки
Из второго утверждения следует:
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> .
Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex>
Из выше сказанного и первого следствия второго утверждения получаем что:<center> <tex> {\sum_{v:v \in get,v \in T2} \limits} \le \log^*_x(\log_2(n)) = O(\log^*(n)) </tex></center> Для того, чтобы <tex> \log^*_x </tex> существовал необходимо, чтобы <tex> x > e ^{ 1 /e } \approx 1,44 </tex>
Как максимум через <tex> x^{R(k)} </tex> переходов ребро перестанет появляться в классе Т3.
<center><tex> {\sum_{get} \limits}~ {\sum_{v:v \in get,v \in T3} \limits} 1/n = {\sum_v \limits ~\sum_{get: in ~ this ~ get ~ v \in T3} \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 T3} \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>.
В силу того что интервал <tex> (1,45...2) </tex> не пустой теорема доказана.
}}
