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 循环内部有一个函数调用自身，那么大 O 是迭代次数乘以函数吗？

Answer 1

这是一个 n 树的中序遍历，但是你遍历了每个元素，所以它是 O(n)(big-theta 更合适)。