大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树的有序遍历,但你击中了每个元素,所以它是O(n)(big-theta更合适).