Изменения
Нет описания правки
Амортизированная стоимость
<wikitexcenter><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> 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>
Из выше сказанного и первого следствия второго утверждения получаем что :<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>
Рассмотрим сумму <center> <tex>{\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3} \limits} 1~/m < {\sum_{get} \limits} ~ {\sum_{v:v \in get,v \in T3} \limits} 1/n </tex> </center>
Из первого утверждения и того что происходит сжатие путей следует <tex> R(P(x))</tex> cтрого увеличивается при переходе по ребру из Т3.
