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-дерево 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>splay3 * log(n) - 3*log(s(v _{i})) + M</tex> vi -ребенок вершины v Здесь <tex>M = O(log(i+1n)) link-cut-дереве</tex>, поэтому s'(vi)амортизационная стоимость <tex>expose</tex> равна < stex>O(vlog(i+1n)). Значение суммы ограничено</tex>
