求高效计算第n个斐波那契数的Python函数，已尝试低效方法

当然存在高效计算斐波那契数的方法，以下是两种实用且性能优异的实现：

1. 迭代法（O(n)时间，O(1)空间） #

这是最直观的高效实现，彻底避免了普通递归版本的重复计算问题，适合绝大多数场景，能轻松处理n=1000这样的大数值：

def fib(n):
    if n == 0:
        return 0
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

这个函数完全能通过你给出的所有测试用例，Python原生支持大整数运算，不用担心计算大斐波那契数时出现溢出问题。

2. 矩阵快速幂法（O(logn)时间，O(1)空间） #

如果需要处理极大的n（比如n=10^6甚至更大），矩阵快速幂法的效率会更高，它通过将斐波那契数转化为矩阵幂运算，把时间复杂度降到对数级别：

def multiply(a, b):
    # 计算两个2x2矩阵的乘积
    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, power):
    # 快速幂计算矩阵的power次幂
    result = [[1, 0], [0, 1]]  # 单位矩阵
    while power > 0:
        if power % 2 == 1:
            result = multiply(result, mat)
        mat = multiply(mat, mat)
        power = power // 2
    return result

def fib(n):
    if n == 0:
        return 0
    base_mat = [[1, 1], [1, 0]]
    powered_mat = matrix_power(base_mat, n - 1)
    return powered_mat[0][0]

核心原理是利用斐波那契数的矩阵性质：[[1,1],[1,0]]^(n-1) 的左上角元素就是第n个斐波那契数。

注意事项 #

• 不推荐使用**比内公式（通项公式）**计算大n的斐波那契数，因为它依赖浮点数运算，当n较大时会出现精度丢失，无法得到精确值。
• 普通递归（包括带记忆化的递归）要么效率极低（无记忆化），要么空间复杂度较高（有记忆化），整体实用性不如上述两种方法。

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