147
правок
Изменения
→Время работы
[[Link-Cut Tree|Linking-Cutting Tree]] выполняет все вышеописанные запросы за <tex>O(\log(N))</tex>, оценим время работы алгоритма.
Очевидно, что просмотров ребер суммарно <tex>O(\log(E))</tex>, как и в алгоритме Диница. Переход к следующему ребру происходит в следующих случаях:
# просматриваемое ребро насыщено
# дерево разрезается по нулевому ребру
Следующий шаг в алгоритме Диница - сумма длин путей. Раньше считалось за <tex>O(V^2)</tex>. Потому, что на каждый путь DFS тратил время, пропорциональное длине этого пути. Сейчас тратится только <tex>O(\log(V))</tex> на каждый путь. Если путь найден, значит до него дошли, значит это соответствует одному запросу. Поэтому тратим на каждый путь тоже логарифм <tex>O(\log(V))</tex>.
Тогда имеем ассимптотику <tex>O(E\log(V) + V \log(V)) = O((V + E) \log(V))</tex>. И, суммарно, если подставить в Алгоритм Диница будем иметь ассимптотику <tex>O(VE \log(VEV))</tex>
== Источники ==
