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 + 2log(n)</tex>
Докажем, что амортизированная стоимость операции изменения класса ребер в link-cut-дереве равна <tex>O(1)</tex>
Пусть </tex>s(v)</tex> - количество вершин в поддеревьях <tex>v</tex>(здесь имеется в виду splay-дерево пути). <tex>\Phi = \sum_{v} log(s(v))</tex>. Нам известно, что стоимость i-той операции splay не превосходит 1 + 3*(r'(v_{i} - r(v_{i})). Тогда стоимость всех <tex>splay</tex> за один <tex>expose</tex> ограниченна суммой. После каждого <tex>splay(v _{i})</tex> vi -ребенок вершины v(i+1) link-cut-дереве, поэтому s'(vi)< s(v(i+1)). Значение суммы ограничено
