Какова временная сложность обхода дерева?

Какова временная сложность обхода дерева, я уверен, что это должно быть очевидно, но мой плохой мозг не может справиться с этим прямо сейчас.Какова временная сложность обхода дерева?

источник

2011-02-10 new299

Это линейное искусство программирования Vol 1 страница 326 – new299

Это искусство программирования Кнута? Я пытаюсь найти это, чтобы дать другу хороший пример того, что для n-арного дерева он линейный. – Nicholas

yes Knuth's «Искусство компьютерного программирования» – new299

Это зависит от того, какой обход вы выполняете, и алгоритм, но обычно это будет O (n), где n - общее количество узлов в дереве. Каноническая рекурсивная реализация первого обхода глубины будет потреблять память (в стеке) в порядке самого глубокого уровня, который на сбалансированном дереве будет log (n).

источник

2011-02-10 11:20:33 Uri

Это правда о n-арном дереве? У меня есть структура данных, которая является деревом max-depth 4 и пересекает его, мой друг использует 3 для циклов, и говорит, что его алгоритм работает в 'O (n^3)' время, но я считаю, что он работает в ' n' time, 'n' - общее число узлов в дереве – Nicholas

@Nocholas, вы правы и ваш друг ошибается. Оно включено). – Uri

Не так ли будет n для дерева с n узлов?

Вы посещаете каждый древо один раз, не так ли? Поэтому я бы сказал, что он линейный.

источник

2011-02-10 11:18:28 Nanne

Я предполагаю, что это должно быть дерево с «n узлами», а не «n листьев». – aamadmi

Вы правы, неверно terminoligy :) – Nanne

@Nanne С правильным алгоритмом это действительно линейная сложность во времени (посещение каждого узла один раз), но это может все еще не иметь линейной сложности в пространстве. Подобно использованию стека. – Tim

Какова временная сложность обхода дерева?

ответ

Смежные вопросы