大O和树遍历

发布于 2024-07-25 16:10:14 字数 281 浏览 3 评论 0原文

如果我有一个这样的函数：

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

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

原文

If I had a function like this:

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

Would that be Big O of n^2 or Big O of n? If you have a for loop and inside that for loop a function call to itself, is the Big O the number of iterations times the function?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

俏︾媚 2024-08-01 16:10:14

这是一个 n 树的中序遍历，但是你遍历了每个元素，所以它的时间复杂度为 O(n)（大 θ 更合适）。

回复收藏 0 原文

書生途 2024-08-01 16:10:14

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

编辑：请参阅此链接，了解 Big-Oh 的讨论递归函数。

回复收藏 0 原文

蓝礼 2024-08-01 16:10:14

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

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

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

也就是说，深度与宽度确实会影响函数的空间考虑因素。

如果树非常宽（假设宽度使得深度对于任何 N 始终恒定），则遍历所需的堆栈空间是恒定的。
然而，如果宽度是固定常数值> 1 则所需的堆栈空间为 O(log(N))。
如果你有宽度为 1 的退化情况，那么树就变成了一个链表，空间需求是 O(N)。
某些语言/编译器将能够优化递归，以便空间需求实际上是恒定的（但这取决于您在遍历期间正在执行/返回的内容）。