斐波那契数列：从递归到矩阵快速幂

算法之美：从递归到矩阵快速幂

斐波那契数列是算法设计中一个绝佳的试金石：问题足够简单，解法却足够多样，从指数级复杂度一路优化到对数级，完整展现了算法思维的力量。

朴素递归：简洁的陷阱

最直观的思路来自数学定义本身：

F(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F(n-1) + F(n-2) & n \geq 2 \end{cases}

直接翻译成 Python 再自然不过：

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

然而这段代码美则美矣，效率却是一场灾难。每次调用 fib(n) 都会分裂出两个子问题，整个递归树膨胀为一棵巨大的二叉树，时间复杂度高达 $O(2^n)$ 。在我的机器上，fib(40) 需要数秒，fib(50) 则几乎不可能跑完——只因它在重复计算成千上万次相同的子问题。

记忆化搜索：用空间换时间

问题的根源在于重复计算。既然 fib(5) 的值不会变，算过一次就记住它：

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]

这是自顶向下的动态规划（记忆化搜索），每个子问题只计算一次，时间复杂度骤降至 $O(n)$ ，空间复杂度 $O(n)$ 。fib(1000) 瞬间出结果。

同样的思路反过来，自底向上递推，只用两个变量滚动：

def fib_iter(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)$ ，简洁高效，是工程中最常用的实现。

矩阵快速幂：通往对数级

但 $O(n)$ 就是终点吗？斐波那契的递推关系可以写成矩阵形式：

\begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F(n-1) \\ F(n-2) \end{bmatrix}

反复迭代即得：

\begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} F(1) \\ F(0) \end{bmatrix}

问题转化为求矩阵的 $n-1$ 次幂。而幂运算可以用快速幂（二分幂）优化到 $O(\log n)$ ：

def mat_mul(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_pow(M, n):
    result = [[1, 0], [0, 1]]  # 单位矩阵
    while n:
        if n & 1:
            result = mat_mul(result, M)
        M = mat_mul(M, M)
        n >>= 1
    return result

def fib_fast(n):
    if n <= 1:
        return n
    M = [[1, 1], [1, 0]]
    return mat_pow(M, n - 1)[0][0]

至此，求解 $F(n)$ 的时间复杂度降至 $O(\log n)$ ，即便 $n=10^{18}$ 也能在毫秒级完成。

视野延伸：斐波那契无处不在

斐波那契数列远不止是一道算法题。向日葵的螺旋排布、松果的鳞片、鹦鹉螺的壳纹，都遵循斐波那契数列的规律——这是自然界高效生长的最优解。在金融领域，斐波那契回撤是技术分析的经典工具；在计算机科学中，斐波那契堆是优化最短路径算法的关键数据结构，而斐波那契编码更是一种紧凑的整数编码方案。

从 $O(2^n)$ 到 $O(\log n)$ ，这段旅程告诉我们：同一个问题，换一个视角，可能是完全不同的世界。