Оценка сложности алгоритма
Предположим, у меня есть дерево. Передо мной стоит задача: найти самый глубокий лист, учитывая его корень. Вот псевдокод:
heightFunc(elem)
height = 1;
for all children c in elem:
height = max(height, 1 + heightFunc(c));
return height;
Понятно, что он сначала складывает в стек инфу,а потом достает. Но какая сложность у этого алгоритма? O(n)? O(log n)? И как вооще можно это оценивать?
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Алгоритм работает за линейное время O(n).
Каждый узел посещается один раз, т.к. дерево - у узла единственный родитель, два раза в один узел не заходим
Деревья бывают чёрно-красными, но само по себе это не поможет. А вот если в узлах хранить дополнительную информацию о высоте поддерева (т.н. augmented деревья (дополненные)), то за O(1) можно узнавать высоту дерева, если обновлять высоты в процессе изменения структуры (за O(logn) в случае сбалансированных деревьев)