693
правки
Изменения
→Оценка времени работы
Выразим сложность одной операции <tex>\mathrm{remove}</tex> другим способом. Для <tex>n</tex> вершин и <tex>m</tex> вызовов процедуры сложность равна <tex>O(\log^2{n}\cdot m+\log n\cdot\displaystyle \sum_{i=1}^m S_i)</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>.
'''function''' remove ('''Node''' u, '''Node''' v):
'''Edge''' e = <tex>\langle </tex>u, v<tex>\rangle</tex>
i = e.level
'''while''' i >= 0
'''Edge''' e e2 '''for''' e2 = <tex>\langle </tex>x, y<tex>\rangle</tex> '''for''' e : e.level == i'''and''' x <tex>\in T_u</tex>
'''if''' y <tex>\in T_v</tex>
'''for''' j = i '''downto''' 0
insert(<tex>F_j</tex>, ee2) i = 0
'''break'''
'''else''' ee2.level++ i---->
== См. также ==
