下面这段代码定义了一个递归函数 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