Big O и обход дерева

Question

Если бы у меня была такая функция:

void myfunction(node* root)
{
   for(int i = 0; i<root->children.size();i++)
   {
      myfunction(root->children[i]);
   }
}

Это будет Большой О из n ^ 2 или Большой О из n? Если у вас есть цикл for, а внутри цикла for вызов функции для себя, является ли Big O числом итераций, умноженным на функцию?

Answer 1

Это обход по порядку n-дерева, но вы ударяете по каждому элементу, так что это O (n) (биг-тета больше подходит).

Answer 2

Вы можете решить это, учитывая, что происходит с деревом с N узлами.

Функция будет вызываться один раз для каждого узла дерева, как и O (N) и Big-Theta (N).

Подумайте, как не важно, насколько широкое дерево, сколько высоту дерева для большого значения O, у него все равно такое же количество посещений.

При этом глубина в зависимости от ширины влияет на пробел соображений функции.

Если дерево очень широкое (скажем, ширина такова, что глубина всегда постоянна для любого N), то пространство стека, необходимое для обхода, является постоянным.
Однако если ширина была фиксированным постоянным значением> 1, то требуемое место в стеке равно O (log (N)).
Если у вас был вырожденный случай, когда ширина была 1, тогда дерево становится связанным списком, а требования к пространству составляют O (N).
Некоторые языки / компиляторы могут оптимизировать рекурсию так, чтобы требования к пространству были фактически постоянными (но это зависит от того, что вы делаете / возвращаете во время обхода).

Answer 3

Это рекурсивный вызов функции. Вам нужно немного изучить рекуррентные отношения , чтобы вычислить сложность времени в обозначениях Big O. Ваши аргументы верны в общем случае. В данном конкретном случае ответы уже были размещены.

РЕДАКТИРОВАТЬ: Ссылка для обсуждения Big-Oh для рекурсивных функций.

Answer 4

В математике, информатике и связанные поля, большие обозначения O описывает ограничивающее поведение функция, когда аргумент стремится к определенной стоимости или бесконечность, как правило, с точки зрения более простого функции. Обозначение Big O позволяет его пользователи упростить функции в порядке сосредоточиться на своих темпах роста: разные функции с одинаковыми Скорость роста может быть представлена ​​с помощью то же самое обозначение O.

Остальное здесь .
И что касается вашего примера, у вас определенно есть O (n).

Answer 5

Это O (n), где n - общее количество узлов в дереве