142
правки
Изменения
Нет описания правки
==Общий метод построения частично персистентных структур данных==
[[Файл:Частичная персистентность.png|мини|слевасправа|500x300px| Пунктирные линии — обратные ссылки,<br> <tex>X</tex> — исходный узел, актуальный до версии <tex>10</tex>,<br>
<tex>X'</tex> — склонированный узел, актуальный с версии <tex>11</tex>, с пустым списком изменений]]
Применим методы, описанные выше, в общем случае для абстрактной структуры данных.
Оценим время работы этого алгоритма. Введем функцию потенциала, которая будет равна суммарному размеру всех списков изменений в последней версии. Посмотрим, как меняется суммарный размер списков изменений, когда мы совершаем одно изменение. Если ''change log'' был не полный, то мы просто добавляем туда один элемент, потенциал увеличится на единицу.
Если ''change log'' был полный, то потенциал уменьшается на его размер, так как мы склонировали узел с пустым списком изменений. После этого мы пошли по обратным ссылкам (их было <tex>P</tex> штук) и добавили в <tex>P</tex> узлов по одному значению. Таким образом амортизированное время работы будет <tex>O(1)</tex>.
==Получение полностью персистентных структур данных==
