给定代码段的空间复杂度是什么？

Question

时间复杂度为O（2 ^ N）。如何得出此代码的空间复杂度？

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

Answer 1

算法的空间复杂度是算法相对于输入大小所占用的总空间。空间复杂度包括辅助空间和输入所使用的空间。

quick reference

[基本代码段是递归代码输入n递归调用n-1

值3的调用示例：

f（3）f（2）+ f（2）f（1）+ f（1）[对于一个f（2），像另外两个一样明智]

执行顺序类似于DFS遍历。

由于递归，程序将重用之前使用的相同程序空间。

树的最大深度将导致空间复杂性

O（N）-其中N是输入数字

用于工作程序的递归使用Stack Memory