234
правки
Изменения
→Оценка времени работы
По лемме, количество легких dashed-ребер, преобразованных в solid, будет не больше, чем <tex>\log n</tex>.
Обозначим за <tex>F</tex> лес деревьев, в которых каждое ребро либо solid, либо dashed, a <tex>F'</tex> - лес, получившийся из <tex>F</tex> после одного вызова <tex>expose</tex>. Определим потенциал <tex>\Phi _{a}(F) = n - 1 - |\{heavy H \cap solid-edges\}|</tex>. , <tex>\Delta \Phi _{a}</tex> - увеличение <tex>\Phi _{a}</tex> после одной операции <tex>expose</tex>.
<tex>V = M + \Delta \Phi _{a}\\
= M + |H \cap S \rightarrow D| - |H \cap D \rightarrow S| \\
\leqslant M + |L \cap D \rightarrow S| - |H \cap D \rightarrow S| \\
= 2 * \times |L \cap D \rightarrow S| \\=2 * \times \log n
</tex>
}}
Докажем, что амортизационная стоимость операции <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'(v_{i} t) - r(v_{i}v)) (лемма)</tex>. Это приводит к тому, что амортизационная стоимость <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>
