斐波那契序列递归空间复杂度[重复]

是的,本例中的空间复杂度取决于调用堆栈中使用的空间,这取决于活动函数调用的数量(已调用但未完成执行的函数)。

如果你注意到最后一句话

return fib(n-1) + fib(n-2)

什么时候? fib(n-1) 是经过计算的 O(n) 使用空间。一次 FIB(N-1) 完成执行堆栈空间可由 fib(n-2) .

因此,在这种情况下,调用 fib(n) 是 o(n) ,因此空间复杂性为 o(n) .

然而,值得注意的是,时间复杂度是指数级的。