142
правки
Изменения
→Преобразование списка в персистентный за O(1)
#* Если была только одна версия структуры данных и полные узлы в ней отсутствовали, то при добавлении нового узла между двумя уже существующими нужно добавить в эти узлы вторую версию (первый рисунок этого раздела). Функция потенциала увеличится на <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>\Phi = O(n)</tex> так как количество толстых узлов не может превосходить общее количество узлов.
Таким образом, [[Амортизационный анализ#Метод потенциалов|по теореме о методе потенциалов]], амортизационное время работы по добавлению элемента будет <tex>O(1)</tex>.
