693
правки
Изменения
→Оценка времени работы
Пункт <tex>1</tex> работает за <tex>O(\log^2 n)</tex>, так как мы добавляем ребро за <tex>O(\log n)</tex> на каждом уровне, а количество уровней не больше <tex>\log n</tex>.
Пункт <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>.
