1302
правки
Изменения
Нет описания правки
<center><tex>
S= {\sum_{get} \limits} ({\sum_{v:v \in get,v \in T1} \limits 1} + {\sum_{v:v \in get,v \in T2} \limits 1} + {\sum_{v: \in get,v \in T3} \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 T1} \limits 1} = O(1) </tex> получаем:
<center><tex> S = O(1) + {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T2} \limits} 1/m+ {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3} \limits} 1/m </tex></center> .
Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </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>.
}}
== Ссылки ==
* [http://en.wikipedia.org/wiki/Iterated_logarithm Wikipedia -Iterated logarithm]
