Изменения

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

Level Ancestor problem

14 байт убрано, 17:46, 15 мая 2019
Сравнение с наивными реализациями
В итоге полученный алгоритм действительно работает за < <tex>O(n), O(1)</tex> > времени и за <tex>O(n)</tex> памяти.
== Сравнение с наивными реализациями ==
Используя обход в глубину <tex>dfs</tex> посчитаем глубину каждой вершины дерева (это можно сделать за <tex>O(n)</tex>), после чего можем из вершины <tex>v</tex> подняться до необходимой глубины вершины <tex>k</tex>,
что так же в худшем случае работает за <tex>O(n)</tex>.
Получили алгоритм за < <tex>O(n), O(n)</tex> > времени и <tex>O(n)</tex> памяти, где время ответа на
Анонимный участник

Навигация