693
правки
Изменения
→Оценка времени работы
Пункт <tex>2</tex> выполняется за <tex>O(\log n)</tex> за счёт добавления новых рёбер в <tex>G_{i+1}</tex> и вызывается до <tex>\log n</tex> раз.
Пусть до момента, когда мы нашли нужное ребро, мы сделали <tex>S</tex> неудачных сканирований. Получаем сложность удаления одного ребра <tex>O(\log^2{n}+S\cdot\log n)</tex>. <!--- Возможно, мы удалим мост, но это уже другая история, да и она всяко лучше логарифмов в квадрате... --->
Выразим сложность одной операции <tex>\mathrm{remove}</tex> другим способом. Для <tex>m</tex> вызовов процедуры сложность равна <tex>O(\log^2{n}\cdot m+\mathrm{\log}n\cdot\sum{S})</tex>, что не превосходит <tex>O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m)</tex>, так как уровень ребра <tex>m</tex> раз рос максимум до <tex>\log n</tex>. Отсюда суммарная сложность всех запросов равна <tex>O(\log^2{n}\cdot m)</tex>, а для одного запроса мы решаем задачу за <tex>O(\log^2{n})</tex>.
