本文旨在通过数学方法证明使用备忘录（Memoization）优化的递归斐波那契程序的线性时间复杂度 O(n)。我们将首先回顾朴素递归斐波那契算法的指数时间复杂度，然后通过分析备忘录方法减少的递归调用次数，推导出优化的斐波那契算法的时间复杂度证明。
朴素递归斐波那契算法的时间复杂度分析
经典的递归斐波那契算法，由于存在大量的重复计算，导致其时间复杂度为 O(2^n)。 我们可以通过递归树来理解这一点。计算 fib(n) 需要计算 fib(n-1) 和 fib(n-2)，而计算 fib(n-1) 又需要计算 fib(n-2) 和 fib(n-3)，以此类推。可以看到，很多子问题被重复计算了很多次。
以下是朴素递归斐波那契算法的示例代码：
private static long fibNaive(int n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}其时间复杂度推导过程如下：
- T(n) = T(n - 1) + T(n - 2) + c
- 由于 T(n-1) > T(n-2), 所以 T(n) < 2T(n-1) + c
- T(n) = 2T(n-1) + c = 4T(n-2) + 3c = 8T(n-3) + 7c = 2^k T(n-k) + (2^k - 1)c
- 当 n - k = 0 时，k = n
- T(n) = 2^n T(0) + (2^n - 1)c
- T(n) = (1 + c) * 2^n - c
- 因此，T(n) <= 2^n，时间复杂度为 O(2^n)
备忘录（Memoization）优化
备忘录是一种动态规划的优化技巧，它通过存储已经计算过的子问题的结果，避免重复计算，从而提高算法的效率。 在递归斐波那契算法中，我们可以使用一个数组 memo 来存储已经计算过的 fib(i) 的值。 当我们需要计算 fib(i) 时，首先检查 memo[i] 是否已经存在值。如果存在，则直接返回 memo[i]，否则计算 fib(i) 并将其存储到 memo[i] 中。
以下是使用备忘录优化的递归斐波那契算法的示例代码：
private static long[] memo;
private static long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) {
return memo[n];
}
long result = fibMemo(n - 1) + fibMemo(n - 2);
memo[n] = result;
return result;
}
public static long fibonacci(int n) {
memo = new long[n + 1];
return fibMemo(n);
}数学证明时间复杂度为 O(n)
使用备忘录后，递归调用树发生了显著的变化。 很多分支变成了叶子节点，因为它们的结果已经被计算并存储在 memo 数组中。 因此，递归调用次数从 2^n 降低到 2*n 级别。
递归关系仍然存在：
- T(n) = T(n - 1) + T(n - 2)
但是，由于备忘录的存在，T(n-2) 的计算只需要常数时间，因为它的值已经被存储在 memo 数组中。
因此，我们可以将递归关系简化为：
- T(n) = T(n - 1) + c
- T(n - 1) = T(n - 2) + c
- T(n - 2) = T(n - 3) + c
- ...
- T(1) = c
将上述等式逐个代入，我们可以得到：
- T(n) = T(n - 1) + c = T(n - 2) + 2 c = T(n - 3) + 3 c = ... = T(1) + (n - 1) c = c + (n - 1) c = n * c
因此，T(n) = O(n)。
总结
通过使用备忘录，我们成功地将递归斐波那契算法的时间复杂度从 O(2^n) 降低到 O(n)。 这是动态规划的一个典型应用，它通过存储中间结果，避免重复计算，从而显著提高算法的效率。 备忘录方法适用于具有重叠子问题的递归算法。
