3622
правки
Изменения
→Преобразование списка в персистентный за O(1): чуть переписана потенциальная оценка
Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, изменять можно только ее последнюю версию. Примем функцию потенциала <tex>\Phi</tex> равной числу полных узлов в последней версии.
# Амортизационная стоимость операции добавления:
#* Если была только одна версия структуры данных и полные узлы в ней отсутствовали<tex>a_{empty} = t + \Delta\Phi = O(1) + 2 = O(1), </tex> так как если добавление узла не задевает полных узлов, то при добавлении нового узла между двумя уже существующими нужно добавить в эти узлы вторую версию (первый рисунок этого раздела). Функция потенциала увеличится узел добавляется за константное время, а количество полных узлов увеличивается на <tex>2</tex>.Тогда #* <tex>a a_{fat} = t + \Delta\phi Phi = 3 O(1) + k - k + 2 = O(1). , </tex>#* Если при преобразовании структуры данных было склонировано так как если узел влечёт изменения полных узлов, то сначала потратится <tex>k</tex> времени на копирование этих полных узлов, и в то количество полных узлов в последней версии (на рисунке выше узлы последней версии выделены красным цветом) же время потенциал уменьшится на <tex>k</tex>, и еще два узла нужно будет добавить (по одному слева и справа). Тогда а потом увеличится максимум на <tex>a = t + \Delta\phi = k + (-k + 2) = O(1)</tex>.#Для любого <tex>i: \Phi Phi_i = O(n),</tex> так как количество толстых полных узлов не может превосходить общее количество больше общего количества узловв списке.
Таким образом, [[Амортизационный анализ#Метод потенциалов|по теореме о методе потенциалов]], амортизационное время работы по добавлению элемента будет <tex>O(1)</tex>.
