algorithm - 这个递归算法的时间复杂度是多少？

Question

int func3(int n){
  if (n <= 1) return n;
  return func3(n - 1) + func3(n - 1);}

我的想法是:在每个递归中我们都有一个加法运算。而我们每次把递归一分为二的时候都做这个操作。所以我不确定我应该称它为 O(N2^N) 还是 O(2^N)。我认为 O(N2^N) 更有意义，因为我们将问题分成 2^N 部分并分别添加它们。尽管我不确定。那么有人可以通过展示他们的步骤来指导我吗？

Answer 1

您可以将对函数的调用绘制为二叉树:

    func3
     /\
 func3 func3
.............

您的二叉树中将有 n 级节点，每个 next_level_node_count = perv_level_node_count * 2。

这是一个几何级数。