c++ - 大 O 和树遍历

Question

如果我有这样的功能：

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

那是 n^2 的大 O 还是 n 的大 O？如果您有一个 for 循环，并且在该 for 循环内部有一个对自身的函数调用，那么 Big O 是迭代次数乘以该函数吗？

Answer 1

这是一个 n-tree 的有序遍历，但是你会碰到每个元素，所以它是 O(n) （big-theta 更合适）。

Answer 2

这是一个递归函数调用。您需要研究一下递归关系来计算大 O 表示法的时间复杂度。在一般情况下，您的推理是正确的。在这种特定情况下，答案已经发布。

编辑：请参阅此链接以讨论 Big-Oh for Recursive Functions。

Answer 3

您可以通过考虑具有 N 个节点的树会发生什么来解决这个问题。

该函数将为树中的每个节点调用一次，O(N) 和 Big-Theta(N) 也是如此。

考虑一下，对于大 O 值来说，树的宽度与树的高度并不重要，它仍然有相同的访问次数。

也就是说，深度与宽度确实会影响功能的空间考虑。

如果树非常宽（比如宽度使得任何 N 的深度总是恒定的），那么遍历所需的堆栈空间是恒定的。
然而，如果宽度是一个固定的常数值 > 1，那么所需的堆栈空间是 O(log(N))。
如果您遇到宽度为 1 的退化情况，则树将变为链表，并且空间要求为 O(N)。
一些语言/编译器将能够优化递归，以便空间需求实际上是恒定的（但这取决于您在遍历期间正在做什么/返回）。

Answer 4

在数学、计算机科学和相关领域，大 O 表示法描述了当参数趋于特定值或无穷大时函数的限制行为，通常以更简单的函数表示。Big O 表示法允许其用户简化函数以便专注于它们的增长率：具有相同增长率的不同函数可以使用相同的 O 表示法来表示。

其余的在这里。
关于你的例子，你肯定有 O(n)。

Answer 5

这是 O(n)，其中 n 是树中的节点总数