big-o - 递归函数的空间复杂度

Question

给定以下函数:

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

我知道 Big O 时间复杂度是 O(2^N)，因为每次调用都会调用该函数两次。

我不明白的是为什么空间/内存复杂度是O(N)？

Answer 1

解决此类问题的一个有用方法是考虑 recursion tree 。递归函数要识别的两个特征是:

1. 树深度(在基本情况之前将执行多少返回语句)
2. 树的宽度(将进行多少递归函数调用总数)

本例的递推关系为 T(n) = 2T(n-1)。正如您正确指出的，时间复杂度为 O(2^n)，但让我们看看它与递归树的关系。

      C
     / \         
    /   \      
T(n-1)  T(n-1)

            C
       ____/ \____
      /           \
    C              C   
   /  \           /  \
  /    \         /    \
T(n-2) T(n-2) T(n-2)  T(n-2)

这种模式将持续到我们的基本情况如下图所示:

对于每个连续的树级别，我们的 n 都会减少 1。因此，我们的树在到达基本情况之前将具有深度 n。由于每个节点有 2 个分支，并且总共有 n 个级别，因此节点总数为 2^n，从而使时间复杂度为 O(2^n)。

我们的内存复杂度由返回语句的数量决定，因为每个函数调用都将存储在程序堆栈上。概括而言，递归函数的内存复杂度为O(递归深度)。正如我们的树深度所示，我们总共将有 n 个返回语句，因此内存复杂度为 O(n)。