234
правки
Изменения
Нет описания правки
{{Определение
|definition=Персистентными структурами данных мы будем называть называются такие структуры, что при всяком их изменении остается доступ ко всем предыдущим версиям этой структуры.
}}
== Наивная реализация ==
Самое простое и очевидное решение этой задачи — симуляция описанного процесса, т.е. честное копирование стека при каждой операции. <br>
Очевидно, что это не самое эффективное решение. Сложность одной операции составляет <tex>O(n)</tex> и количество требуемой памяти — <tex>O(n * n)</tex>.
== Нормальная Эффективная реализация ==
Попробуем решить задачу эффективнее. Вместо n копий стека будем хранить n первых элементов. Тогда операции push и pop будут иметь следующий вид:<br>
