斐波那契递归函数的真实时间复杂度：是2^n还是黄金比例的n次方？

首先明确：两种说法都有道理，但O(φⁿ)是更精确的渐近时间复杂度，而O(2ⁿ)是一个宽松的上界——这就是你看到不同表述的原因。

先看递归式和精确复杂度推导 #

递归斐波那契的核心逻辑是：

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

对应的时间复杂度递归方程是：

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

解这个递归方程需要用到特征方程法：

1. 写出特征方程：x² = x + 1
2. 解得两个根：φ=(1+√5)/2≈1.618（黄金比例），ψ=(1-√5)/2≈-0.618
3. 最终T(n)的表达式是T(n) = a*φⁿ + b*ψⁿ + O(1)，其中a、b是常数

因为|ψ|<1，当n增大时，ψⁿ会趋近于0，所以可以忽略，最终精确的渐近复杂度是O(φⁿ)。

为什么很多网站说O(2ⁿ)？ #

这是因为用递归树分析时，每一层的节点数最多是2的k次方（k为层数），总节点数的上限是2⁰+2¹+…+2ⁿ≈2ⁿ⁺¹，所以O(2ⁿ)是一个正确但宽松的上界。

对于入门学习来说，这个推导更直观易懂，不需要涉及特征方程的数学知识，所以很多普及类资料会优先用这个表述。

总结 #

• O(2ⁿ)：正确，但不是最紧的上界
• O(φⁿ)：更精确的渐近复杂度，反映了递归斐波那契的实际增长速率

内容的提问来源于stack exchange，提问作者Ahmed Alnyle