斐波那契数列的快速计算方法

问题描述

斐波那契数列定义为：

• F(0) = 0, F(1) = 1
• F(n) = F(n-1) + F(n-2)（n ≥ 2）
  例如：0, 1, 1, 2, 3, 5, 8, 13, ...
  直接递归计算F(n)的时间复杂度为O(2^n)，效率极低。如何高效计算F(n)？

方法1：递归的缺点与改进思路

直接递归代码（Python示例）：

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

问题分析：

• 计算F(4)需递归调用F(3)和F(2)，而F(3)又调用F(2)和F(1)，存在大量重复计算（如F(2)被计算两次）。
• 递归树规模指数增长，时间复杂度O(2^n)，空间复杂度O(n)（栈深度）。

改进方向：避免重复计算，保存中间结果。

方法2：记忆化搜索（自顶向下）

思路：用哈希表缓存已计算的F(k)，遇到重复子问题直接返回结果。
代码实现：

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

复杂度分析：

• 每个F(k)仅计算一次，共O(n)个子问题。
• 时间复杂度O(n)，空间复杂度O(n)（递归栈+哈希表）。

方法3：动态规划（自底向上）

思路：从F(0)和F(1)开始迭代计算，避免递归开销。
代码实现：

def fib_dp(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

复杂度分析：

• 时间复杂度O(n)，空间复杂度O(1)（仅保存前两个值）。
• 优点：无递归栈溢出风险，适合大n。

方法4：矩阵快速幂（对数时间复杂度）

数学原理：
将递推关系转化为矩阵形式：

[ F(n)   ]   = [ 1  1 ] [ F(n-1) ]
[ F(n-1) ]     [ 1  0 ] [ F(n-2) ]

递推得到：

[ F(n)   ]   = [ 1  1 ]^(n-1) [ F(1) ]
[ F(n-1) ]     [ 1  0 ]        [ F(0) ]

关键步骤：

1. 定义矩阵乘法函数。
2. 利用快速幂思想计算矩阵的n次幂（分治策略）：
   • 若n为偶数：A^n = (A^(n/2))^2
   • 若n为奇数：A^n = A * (A^(n-1))
     代码实现：

def mat_mult(A, B):
    return [
        [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
        [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
    ]

def mat_power(M, n):
    if n == 1:
        return M
    if n % 2 == 0:
        half_power = mat_power(M, n//2)
        return mat_mult(half_power, half_power)
    else:
        return mat_mult(M, mat_power(M, n-1))

def fib_matrix(n):
    if n <= 1:
        return n
    M = [[1, 1], [1, 0]]
    result = mat_power(M, n-1)
    return result[0][0]  # F(n) = result[0][0]*F(1) + result[0][1]*F(0)

复杂度分析：

• 矩阵乘法O(1)，快速幂递归深度O(log n)，时间复杂度O(log n)。
• 适合极大n（如n=10^6）。

方法5：通项公式（数值精度限制）

比奈公式：
F(n) = (φ^n - ψ^n) / √5，其中φ=(1+√5)/2≈1.618，ψ=(1-√5)/2≈-0.618。
局限性：浮点数精度误差，n较大时结果不精确，实际应用少。

总结对比

实际选择：

• 一般情况用动态规划（代码简单高效）。
• 若n极大（如>10^5）且需频繁计算，用矩阵快速幂。
• 记忆化搜索适合递归逻辑清晰的场景。