Изменения

Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, мы изменяем изменять можно только ее последнюю версию. Примем функцию потенциала равной числу полных узлов в последней версии. Если была только одна версия структуры данных и полные узлы в ней отсутствовали, то при добавлении нового узла между двумя уже существующими нужно добавить в эти узлы вторую версию (первый рисунок этого раздела). Функция потенциала увеличится на <tex>2</tex>. Если мы склонировали при преобразовании структуры данных было склонировано <tex>k</tex> узлов, то количество полных узлов в последней версии (на рисунке выше узлы последней версии выделены красным цветом) уменьшится на <tex>k</tex>, и еще два узла мы добавим нужно будет добавить (по одному слева и справа). Таким образом, амортизационное время работы по добавлению элемента будет <tex>O(1)</tex>.