这段代码的空间复杂性是多少？

Question

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

我知道时间的复杂性是O(2^n),我理解为什么.

但我不明白为什么空间复杂性O(n).我被告知这是因为在任何给定时间只有n节点,但它对我没有意义.

Answer 1

因为第二个f(n-1)不能运行直到第一个完成(反之亦然 - 它们都是相同的).第一个调用将递归n次数,然后所有这些将返回,这样将推送总共n堆栈帧.然后第二个电话会做同样的事情.

因此n,在递归中它永远不会超过级别,这是空间复杂性的唯一贡献者.

Answer 2

空间复杂度为O(n),因为递归的一侧到达叶子,然后返回,直到根,类似于递归的另一侧发生,并且在每个中间步骤中,递归中使用的空间不能大于O递归树的深度.

Answer 3

绘制指数时间复杂度树,并且从树的根开始的任何叶子的路径长度将是线性的.该线性路径是算法的空间复杂度.该算法将遍历每个路径以解决问题,但在任何时候,存储在堆栈中的最大递归调用数将是线性的.例如:forf(3)

         3 
       /   \ 
     2      2 
    / \    / \ 
   1   1  1   1

从根到叶的最大长度是O(n).因此,空间复杂性也是如此O(n).