234
правки
Изменения
→Оценка времени работы
Докажем, что амортизационная стоимость операции <tex>expose</tex> равна <tex>O(log(n))</tex>
Пусть <tex>s(v)</tex> {{- --}} количество вершин в поддеревьях <tex>v</tex> (здесь имеется в виду splay-дерево пути, котоый строится в ходе выполнения <tex>expose</tex>), <tex>r(v) = log(s(v))</tex>. По [[Splay-дерево#Lemma1|лемме]] стоимость ''i''-той операции <tex>splay</tex> не превосходит <tex>1 + 3 \times (r(t) - r(v))</tex>. Это приводит к тому, что амортизационная стоимость <tex>expose</tex> ограничена следующим значением:
<tex>3 \times \log n - 3 \times \log (s(v)) + M</tex>
Здесь <tex>M = O(\log n)</tex>, поэтому амортизационная стоимость <tex>expose</tex> равна <tex>O(\log n)</tex>
