下面這段代碼定義了一個遞歸函數 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