这个算法的空间复杂度是多少(n还是log(n))

Question

我有一个关于这段伪代码的空间(内存)复杂度的问题:

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)

我的观点是，空间复杂度线性增长，即n，因为随着输入n的增长，变量声明的数量也在增加(sol)。

然而我的一个朋友坚持它必须是log(n)。我不太明白他的解释。但是他提到了第二个for循环，并且三个递归调用是依次发生的。

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

Answer 1

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

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

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

Answer 2

我认为复杂性是

0 (log 3以n为底)