递归函数的空间复杂性

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

解决这些类型问题的有效方法是考虑递归树.要识别的递归函数的两个特征是:

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(recursion depth).正如我们的树深度所示,我们将有n个总返回语句,因此内存复杂度为O(n).

Answer 2

这是我的想法：

• 诱惑是说空间复杂度也是O(2^N)，因为毕竟每个O(2^N)递归调用都要分配内存，对吧？（不对）
• 实际上，这些值在每次调用时都被加在一起/折叠起来，因此所需的空间只是从基本情况开始的每次调用的结果，形成数组 [f(1), f(2), f(3 ) ... f(n)]，换句话说就是 O(n) 内存