693
правки
Изменения
Нет описания правки
Запоминание изменений и откаты не влияют на время работы, если оно истинное, а не амортизированное. Действительно: пусть в СНМ произошло <tex>r</tex> изменений. Каждое из них будет один раз занесено в массив и один раз отменено. Значит, запись в массив и откаты работают за <tex>\Theta(r)</tex>. Но и сами изменения заняли <tex>\Theta(r)</tex> времени, значит, откаты не увеличили асимптотическое время работы.
Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность. <!-- Я не уверен, бывает ли персистентный СНМ, работающий за log. -->
=== Частные случаи ===
# Деревья. Для таких графов задачу можно решать при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Операции добавления и удаления рёбер и проверка на существование пути между вершинами работают за <tex>O(\log n)</tex>.
