该算法的 space 复杂度是多少（n 或 log(n)）？

Question

我有一个关于这段特定伪代码的 space（内存）复杂度的问题：

int b(int n, int x) {
   int sol = x;
   if (n>1) {
      for (int i = 1; i <= n; i++) {
         sol = sol+i;
      }
      for (int k=0; k<3; k++) {
         sol = sol + b(n/3,sol/9);
      }
   }
   return sol;
}

代码被调用：b(n,0)

我的观点是，space 复杂度呈线性增长，即 n，因为随着输入 n 的增长，变量声明的数量也会增加（sol).

而我的一个朋友坚持认为它必须是 log(n)。我不太明白他的解释。但是他说了第二个 for 循环，三个递归调用是按顺序发生的。

那么，n 或 log(n) 正确吗？

Answer 1

我认为复杂度是

O(log 3 base (n) )

Answer 2

调用函数 b 的总次数为 O(n)，但 space 复杂度为 O(log(n))。

程序中的递归调用导致执行堆栈增长。每次发生递归调用时，所有局部变量都会被压入堆栈（堆栈大小增加）。当函数从递归返回时，局部变量从堆栈中弹出（堆栈大小减小）。

所以这里要计算的是执行栈的最大大小，也就是递归的最大深度，显然是O(log(n)).