斐波那契递归函数的实时复杂度是多少

Question

我很困惑斐波那契函数的复杂度是2^n还是黄金比例的n次方。

“我注意到很多网站都说这个递归的复杂度是 2 的 n 次方。”

Answer 1

我们用这个伪代码来计算𝐹_𝑛

function F(n):
    if n < 2:
        return n  ' F(0) = 0, F(1) = 1
    return F(n-1) + F(n-2)

我们将计算 𝐹_𝑛 所需的初等运算（复杂度为 O(1)）的数量称为 𝑇_𝑛。

然后我们有常数 𝐴 和 𝐵 使得：

• 𝑇₀=𝐴
• 𝑇₁ = 𝐴
• 𝑇_𝑛 = 𝑇_𝑛−1 + 𝑇_𝑛−2 + 𝐵

这里我们将加法视为常数时间运算。

我们可以看到这个序列：

• 𝑇₂ = 2𝐴 + 𝐵 = 2(𝐴+𝐵) − 𝐵
• 𝑇₃ = 3𝐴 + 2𝐵 = 3(𝐴+𝐵) − 𝐵
• 𝑇₄ = 5𝐴 + 4𝐵 = 5(𝐴+𝐵) − 𝐵
• ...
• 𝑇_𝑛 = 𝐹_𝑛+1(𝐴+𝐵) − 𝐵 = θ(𝐹_𝑛+1)

由于 𝐹_𝑛 = θ(φ^𝑛)，我们有：

𝑇_𝑛 = θ(Φ^𝑛+1) = θ(Φ^𝑛)

对于 Big O，我们无法通过更改幂运算的 base 来获得等效表达式。 关于大 O 表示法的维基百科警告了这一点：

另一方面，不同底数的指数的阶数不同。例如，2^𝑛 和 3^𝑛 的阶数不同。

所以我们不能说 𝑇_𝑛 = θ(2^𝑛)，因为 φ 不是 2，而是 1.618...