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