Изменения

Перейти к: навигация, поиск

Персистентные структуры данных

33 байта добавлено, 21:39, 20 апреля 2015
Преобразование списка в персистентный за O(1)
[[Файл:Аморанализ.png|700px]]
Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, изменять можно только ее последнюю версию. Примем функцию потенциала <tex>\phiPhi</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>\Phi = O(n)</tex> так как количество толстых узлов не может превосходить количество узлов. Таким образом, [[Амортизационный анализ#Метод потенциалов|по теореме о методе потенциалов]], амортизационное время работы по добавлению элемента будет <tex>O(1)</tex>.
==Общий метод построения частично персистентных структур данных==
142
правки

Навигация