下面这段代码定义了一个递归函数 fibonacci，用于计算第 n 个斐波那契数。
def fibonacci(n):if n <= 1:return nelse:return fibonacci(n - 1) + fibonacci(n - 2)
虽然代码逻辑正确，但其性能较差，尤其是对于较大的 n 值，其复杂度较高：
- 时间复杂度：当前代码的时间复杂度为 O(2^n)，因为每次调用
fibonacci(n)会递归调用fibonacci(n-1)和fibonacci(n-2)，导致重复计算。 - 空间复杂度：空间复杂度为 O(n)，因为递归调用栈的深度为
n。
优化 1：使用动态规划（自顶向下，带备忘录）
通过缓存已经计算过的斐波那契数，避免重复计算，可以将时间复杂度优化到 O(n)。
def fibonacci(n, memo={}):if n <= 1:return nif n not in memo:memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)return memo[n]
优化 2：使用动态规划（自底向上，迭代法）
通过迭代的方式计算斐波那契数，避免递归调用栈的开销，同时将空间复杂度优化到 O(1)。
def fibonacci(n):if n <= 1:return na, b = 0, 1for _ in range(2, n + 1):a, b = b, a + breturn b
优化 3：使用 Python 内置的 lru_cache 装饰器
Python 的 functools 模块提供了 lru_cache 装饰器，可以自动缓存函数的结果，避免重复计算。
from functools import lru_cache@lru_cache(maxsize=None)
def fibonacci(n):if n <= 1:return nreturn fibonacci(n - 1) + fibonacci(n - 2)
优化4：使用矩阵快速幂算法（高级优化）
对于非常大的 n 值，可以使用矩阵快速幂算法将时间复杂度优化到 O(log n)。这种方法适合对性能要求极高的场景。
def matrix_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 matrix_pow(matrix, power):result = [[1, 0], [0, 1]] # Identity matrixwhile power > 0:if power % 2 == 1:result = matrix_mult(result, matrix)matrix = matrix_mult(matrix, matrix)power //= 2return resultdef fibonacci(n):if n <= 1:return nmatrix = [[1, 1], [1, 0]]result = matrix_pow(matrix, n - 1)return result[0][0]
推荐使用 优化建议 2（迭代法），因为它在时间复杂度和空间复杂度上都有较好的平衡，且代码简洁易读。优化后的代码如下：
def fibonacci(n):if n <= 1:return na, b = 0, 1for _ in range(2, n + 1):a, b = b, a + breturn b
