Python 斐波那契数列 5 种实现方法与性能分析

优点

• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 利用缓存避免重复计算
• 代码接近数学定义，可读性强

适用场景

• 学习'记忆化'、'动态规划'的绝佳案例
• 适合中等规模数据（如 n < 10^5）

方法四：生成器版本（内存友好）

def fib_generator(n):
    a, b = 0, 1
    count = 0
    while count < n:
        yield a
        a, b = b, a + b
        count += 1

# 使用方式
for num in fib_generator(10):
    print(num)
# 输出：0 1 1 2 3 5 8 13 21 34

优点

• 不一次性生成所有数，节省内存
• 支持 next() 逐个获取
• 适合处理大数据或无限序列

适用场景

• 处理大量数据（如前 100 万个斐波那契数）
• 流式处理、实时输出

方法五：矩阵快速幂（超快）

适用于求第百万个斐波那契数的极致性能需求。

def matrix_multiply(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 matrix_power(mat, n):
    if n == 1:
        return mat
    if n % 2 == 0:
        half = matrix_power(mat, n // 2)
        return matrix_multiply(half, half)
    else:
        return matrix_multiply(mat, matrix_power(mat, n - 1))

def fib_fast(n):
    if n <= 1:
        return n
    base_matrix = [[1, 1], [1, 0]]
    result_matrix = matrix_power(base_matrix, n)
    return result_matrix[0][1]

优点

• 时间复杂度：O(log n)
• 极速计算，适合超大数

适用场景

• 求第 10^6 个斐波那契数
• 算法竞赛、高性能计算

性能对比总结表

最佳实践建议

• 日常开发 → 用循环迭代法
• 学习算法 → 用记忆化递归
• 处理大数据 → 用生成器
• 追求极致性能 → 用矩阵快速幂

扩展练习题

1. 写一个函数，返回前 n 个斐波那契数的列表（用生成器）
2. 写一个函数，判断某个数是否为斐波那契数
3. 画出斐波那契数列的图形（用 matplotlib）
4. 模拟'兔子繁殖'问题（经典故事背景）

附录：一键运行脚本模板

"""
【推荐】斐波那契函数合集（可直接复制使用）
"""
from functools import lru_cache

# 1. 循环迭代（最优）
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# 2. 记忆化递归（推荐学习）
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# 3. 生成器（内存友好）
def fib_gen(n):
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

# 测试
if __name__ == "__main__":
    print("前 10 个斐波那契数：")
    print(list(fib_gen(10)))