Изменения

Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, изменять можно только ее последнюю версию. Примем функцию потенциала <tex>\phi</tex> равной числу полных узлов в последней версии. <tex>\phi = O(n)</tex>. Если была только одна версия структуры данных и полные узлы в ней отсутствовали, то при добавлении нового узла между двумя уже существующими нужно добавить в эти узлы вторую версию (первый рисунок этого раздела). Функция потенциала увеличится на <tex>2</tex>. Тогда амортизационная стоимость операции добавления будет <tex>a = t + \Delta\phi = 3 + 2 = O(1). </tex> Если при преобразовании структуры данных было склонировано <tex>k</tex> узлов, то количество полных узлов в последней версии (на рисунке выше узлы последней версии выделены красным цветом) уменьшится на <tex>k</tex>, и еще два узла нужно будет добавить (по одному слева и справа). Тогда амортизационная стоимость операции добавления будет <tex>a = t + \Delta\phi = k + (-k + 2) = O(1)</tex>. Таким образом, [[Амортизационный анализ|по теореме о методе потенциалов]], амортизационное время работы по добавлению элемента будет <tex>O(1)</tex>.