Изменения

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

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

1 байт убрано, 23:21, 4 апреля 2015
Нет описания правки
Оценим амортизационное время работы этого алгоритма. Введем потенциал, равный суммарному размеру нижних половин списков изменений во всех версиях. Когда мы раздваиваем узел, мы уменьшаем потенциал на половину размера списка изменений (в нашем примере это <tex>2P</tex>), затем мы переставляем <tex>P</tex> ссылок, потенциал увеличивается на <tex>P</tex>, значит амортизационное время работы — <tex>O(1)</tex>.
==Использование персистентных структур данных для решения геометрических задач===
Персистентные структуры данных используются при решении геометрических задач. Примером может служить Point loctaion problem — задача о местоположении точки. Задачи такого рода решаются в ''offline'' и ''online''. В ''offline''-задачах все запросы даны заранее и можно обрабатывать их одновременно. В ''online''-задачах следующий запрос можно узнать только после того, как найден ответ на предыдущий.
Анонимный участник

Навигация