我有一个关于这段特定伪代码的空间(内存)复杂性的问题:
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
的增长,变量声明的数量也随之增加(溶胶
)。
而我的一个 friend 坚持认为它必须是log(n)
。我不太明白他的解释。但他谈到了第二个 for
循环以及三个递归调用按顺序发生的情况。
那么,n
或 log(n)
正确吗?
最佳答案
调用函数b
的总次数为O(n)
,但空间复杂度为O(log(n))
。
程序中的递归调用会导致执行堆栈增长。每次发生递归调用时,所有局部变量都会被插入堆栈(堆栈大小增加)。当函数从递归返回时,局部变量将从堆栈中弹出(堆栈大小减小)。
所以这里要计算的是执行堆栈的最大大小,也就是递归的最大深度,显然是O(log(n))
。
关于algorithm - 该算法的空间复杂度是多少(n 或 log(n))?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40207735/