gpt4 book ai didi

algorithm - 斐波那契数列递归空间复杂度

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:38:21 25 4
gpt4 key购买 nike

<分区>

public int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}

我很困惑为什么上面代码的空间复杂度是O(n)。现在,我知道递归的深度是n,也就是树的高度。

没有创建临时变量或最终结果变量。这里的空间复杂度是从函数调用栈计算出来的吗?

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com