recursion - 这个递归代码的运行时间是多少？

Question

我想知道以下递归函数的运行时是什么：

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

如果您将其视为调用树，则每个节点将有 2 个分支。该调用树中的节点数为 2⁰ + 2¹ + 2² + 2³ + ... + 2^n 相当于 2^(n+1) - 1。所以这个函数的时间复杂度应该是 O( 2^(n+1)-1) 假设每个呼叫的时间恒定为 O(1) - 我正确吗？根据我有这个例子的书，时间复杂度是 O(2^n)。我很困惑 - 我错过了什么？

标签： recursionbig-o

Answer 1

Big-O 表示法忽略常数因子和低阶项。所以 O(2^(n+1)-1) 等价于 O(2^n)。

O(2^(n+1)-1) = O(2^n * 2^1 - 1)

我们去掉 2^1 的常数因子，然后我们去掉 -1 的低阶项，因为 2^n 渐近增长得更快。