234
правки
Изменения
→Оценка времени работы
Теперь проанализируем <tex>M</tex>. Используя тот факт, что начальное значение <tex>\Phi _{a}</tex> не превосходит <tex>n - 1</tex>, приходим к тому, что для деревьев с <tex>n</tex> вершинами, по крайней мере за <tex>n - 1</tex> операцию <tex>expose</tex>, среднее <tex>M</tex> на одну операцию будет не больше, чем <tex>1 + 2\log n</tex>
Докажем, что амортизационная стоимость операции изменения класса ребер в link-cut-дереве <tex>expose</tex> равна <tex>O(1log(n))</tex>
Пусть </tex>s(v)</tex> - количество вершин в поддеревьях <tex>v</tex>(здесь имеется в виду splay-дерево T пути, котоый строится в ходе выполнения <tex>expose</tex>). <tex>\Phi = \sum_{v} \log (s(v))</tex>. Нам известно, что стоимость i-той операции splay не превосходит 1 + 3*(r'(v_{i} - r(v_{i})). После каждого <tex>splay(v)</tex> v соединена с w = pathparent(v), поэтому s(w) > s(vлемма). Это приводит к тому, что амортизационная стоимость <tex>expose</tex> ограничена следующим значением
<tex>3 * \log n - 3*\log (s(v)) + M</tex>
Здесь <tex>M = O(\log n)</tex>, поэтому амортизационная стоимость <tex>expose</tex> равна <tex>O(\log n)</tex>
