Изменения

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

Level Ancestor problem

11 байт добавлено, 00:16, 7 мая 2019
Нет описания правки
== Наивная реализация и двоичные подъемы ==
[[Файл:LevelAncestor.png|200px|thumb|right]]
Используя обход в глубину посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>, что так же в худшем случае работает за <tex>O(n)</tex>. Получили алгоритм за < <tex><O(n),O(n)></tex> >, где время ответа на запрос можно улучшить до <tex>O(\log n)</tex> c помощью [[Метод двоичного подъёма | предподсчета двоичных подъемов]] , но тогда и время предподсчета в наивной реализации (посчитать подъемы для всех вершин) ухудшится до < <tex><O(n \log n),O(\log n)></tex> >. Альтернативой данным двум алгоритмам является полный предподсчет всех возможных запросов, что соответственно дает нам ассимптотику < <tex><O(n^2),O(1)></tex> >.
В данном примере поступает запрос <tex>LA(v, 2)</tex>, на который алгоритм должен дать ответ h.
== Использование Heavy-light декомпозиции ==
Этот алгоритм базируется на различных способах [[Heavy-light декомпозиция | декомпозиции дерева]] (выберем heavy-light декомпозицию), из свойств этого разбиения следует, что подняться на любую высоту из вершины <tex>v</tex> мы можем за <tex>O(\log n)</tex>. Данное разбиение можно строить за <tex>O(n)</tex>, что дает нам алгоритм за < <tex><O(n), O(\log n)></tex> >.
== Алгоритм лестниц ==
36
правок

Навигация