Изменения

Перейти к: навигация, поиск

Задача о динамической связности

27 байт добавлено, 00:24, 15 января 2018
Оценка времени работы
'''Замечание.''' Увеличив уровень ребра на единицу, нужно не забыть обновить <tex>G_{i+1}</tex> и <tex>F_{i+1}</tex>.
====Оценка времени работы====
Пункт <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>\log n</tex> раз.
Пусть до момента, когда мы нашли нужное ребро, мы сделали <tex>S</tex> неудачных сканирований. Получаем сложность удаления одного ребра <tex>O(\log^2{n}+S\cdot\log n)</tex>. Для <tex>m</tex> вызовов процедуры <tex>\mathrm{remove(u, v)}</tex> сложность равна <tex>O(\log^2{n}\cdot m+\mathrm{\log}n\cdot\sum{S})</tex>, что не превосходит O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m). Отсюда суммарная сложность всех запросов равна O(\log^2{n}\cdot m)</tex>, а для одного запроса мы решаем задачу за <tex>O(\log^2{n})</tex>
====Псевдокод====
693
правки

Навигация