1632
правки
Изменения
м
rollbackEdits.php mass rollback
|proof=
Из принципа работы функции <tex> get </tex> следует:
#<tex> R(L(v))>R(v) </tex>.#Между <tex> v </tex> и <tex> P(v) </tex> существует путь вида: <tex> v \rightarrow L(v) \rightarrow L(L(v)) \rightarrow \dots \rightarrow P(v) </tex>.
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
}}
Из последнего утверждения следует:
#<tex> R(v) \le \log_2(n) </tex>.#Количество вершин ранга <tex> i \le {n \over 2^i} </tex>.
{{Теорема
#Ведут в корень или в сына корня.
#<tex> R(P(v)) \ge x^{R(v)}</tex>.
#Все остальные.
</center>
Во время <tex> get </tex> после прохождения K ребер из второго класса <tex> R(v_1) \ge x^{x^{.^{.^{.^{x^{R(v)}}}}}} </tex> .
Из выше сказанного и первого следствия второго утверждения получаем, что:
</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}
