递归斐波那契时间复杂度的澄清

Question

我正在关注 O(2^n) 时间复杂度的 YouTube 视频，这是给出的代码：

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

fib(4);

视频中据说该代码执行的操作是 8 次，即 2^3。

这是因为递归斐波那契实际上是 2^(n-1),
由于我们用 BigO 排除常量，我们认为它是 O(2^n)。

但是我真的不明白为什么操作次数是8。

我写下了这个函数的递归树（通过平衡它）。

我看到 fib() 被调用了 14 次，那么操作数不是 14 次吗？
为什么我们只计算最后一层？

Answer 1

您观看的 YouTube 视频中的所有内容似乎都是错误的。

你的

fib(n)

的递推关系是：

T(n) = T(n-1) + T(n-2) + O(1)

这肯定是指数级的，但肯定不是 O(2ⁿ)。由于 O(1) 对整体复杂度并不重要，因此我们实际上有 T(n) = O(fib(n))，即 O(φⁿ)，其中 φ 是黄金比例，约为 1.618。

在表述指数复杂性时，您必须确保底数完全正确。