yupanzi
Algorithm Python

斐波那契数列的时间复杂度分析

· 3 分钟阅读

计算斐波那契数列的第 n 个数有多种方法，不同方法的时间复杂度差异很大。我们来看看常见的几种实现方式。

什么是斐波那契数列

除了第一个和第二个数外，任意一个数都等于前两个数之和：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

四种实现方法对比

方法时间复杂度空间复杂度特点
递归O(2^n)O(n)简单但效率低
动态规划O(n)O(n)避免重复计算
矩阵快速幂O(log n)O(1)最快的精确方法
Binet 公式O(1)O(1)有精度限制

递归方法

最直观的实现，但效率很低：

def fibonacci_recursive(n):
    if n <= 1:
        return n
    # 每次都会重复计算大量子问题
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

问题：计算 f(5) 时，f(3) 会被计算 2 次，f(2) 会被计算 3 次。

动态规划

用数组存储已计算的值，避免重复计算：

def fibonacci_dp(n):
    if n <= 1:
        return n
    # 存储所有中间结果
    fib = [0] * (n+1)
    fib[1] = 1
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

优化：只需要保存前两个数，空间复杂度可以降到 O(1)。

矩阵快速幂

利用矩阵乘法性质，通过快速幂算法加速：

def matrix_multiply(a, b):
    return [[sum(x * y for x, y in zip(row, col)) for col in zip(*b)] for row in a]

def matrix_power(matrix, n):
    result = [[1, 0], [0, 1]]  # 单位矩阵
    while n > 0:
        if n % 2 == 1:
            result = matrix_multiply(result, matrix)
        matrix = matrix_multiply(matrix, matrix)
        n //= 2
    return result

def fibonacci_matrix(n):
    if n <= 1:
        return n
    matrix = [[1, 1], [1, 0]]
    powered_matrix = matrix_power(matrix, n-1)
    return powered_matrix[0][0]

原理：利用 [[1,1],[1,0]]^n 的性质快速计算。

Binet 公式

使用黄金分割比直接计算：

import math

def fibonacci_binet(n):
    sqrt_5 = math.sqrt(5)
    phi = (1 + sqrt_5) / 2  # 黄金分割比
    return round((phi**n - (-1/phi)**n) / sqrt_5)

注意事项

  • 递归方法仅适合小数值，n > 40 时会非常慢
  • 动态规划是实际工作中最常用的方法，平衡了效率和易读性
  • 矩阵快速幂适合需要计算超大数值的场景
  • Binet 公式在 n 很大时会因浮点数精度问题产生误差

相关文章