c++ - 这个递归函数的运行时间是多少？

Question

我很难计算出这个简单的递归函数的运行时间。

void myRecur(int n)
{
   if (n < 1) return;
   cout << n << " ";
   myRecur(n/2);
   cout << n << " ";
   myRecur(n/2);
}

我认为它会打印:4 2 1 1 2 1 1 4 2 1 1 2 1 1 for myRecur(4)。

还有，这个函数在时间复杂度上是不是和树遍历函数类似？

非常感谢任何有关理解递归的建议以及对这个特定问题的运行时间的详细解释。

Answer 1

这是使用递归关系的好地方!让 T(n) 为算法在大小为 n 的输入上运行所需的时间。然后

• T(0) = 1，因为基本情况执行恒定量的工作，并且
• T(n) = 2T(⌊n/2⌋) + 1，因为每种情况都会对规模为 n/2 的问题进行两次递归调用，并执行额外的常量工作。

现在的目标是找到某种非递归地描述 T(n) 的表达式。有很多方法可以做到这一点。查找迭代方法和递归树方法以获得一些示例。最快的方法是使用名称美妙的主定理，它可以让您直接从递归关系确定时间复杂度。在这种情况下，主定理表明这可以求解 T(n) = θ(n)。