如何用数学方法证明带Memoization的递归斐波那契程序时间复杂度

标准递归斐波那契的复杂度回顾 #

首先回顾标准递归斐波那契的时间复杂度上限证明：

T(n-1)=T(n-2)

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 , hence 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的实现代码 #

使用动态规划Memoization优化后的代码如下：

private static long fib(int n) {
    if (n <= 1) return n;
    
    if (memo[n] != 0) {
        return memo[n];
    }
    
    long result = fib(n - 1) + fib(n - 2);
    memo[n] = result;
    
    return result;
}

上下界分析法证明O(n)复杂度 #

定义递归式 #

设T(n)为计算fib(n)的时间复杂度，其中：

• 基础情况：T(0) = c₀，T(1) = c₁（c₀、c₁为常数，对应直接返回的时间）
• 对于n > 1：当memo[n]未被填充时，计算fib(n)需要先递归计算fib(n-1)（该过程会填充memo[2]到memo[n-1]），再直接读取已填充的memo[n-2]，最后完成加法与存储操作，因此递归式为：

  T(n) = T(n-1) + c （c为常数，对应判断、加法、存储的固定时间）
  

上界证明（O(n)） #

用数学归纳法：

1. 假设对于所有k < n，存在常数a、b，使得T(k) ≤ a*k + b
2. 对于n ≥ 2：

   T(n) = T(n-1) + c ≤ a*(n-1) + b + c = a*n + (b + c - a)
   

   只需取a ≥ c，b ≥ T(1) - a*1（例如a=c，b=T(1)），即可满足T(n) ≤ c*n + T(1)，因此T(n) = O(n)。

下界证明（Ω(n)） #

同样用数学归纳法：

1. 假设对于所有k < n，存在正数常数d、e，使得T(k) ≥ d*k + e
2. 对于n ≥ 2：

   T(n) = T(n-1) + c ≥ d*(n-1) + e + c = d*n + (e + c - d)
   

   只需取d ≤ c，e ≤ T(0)，即可满足T(n) ≥ d*n + e，因此T(n) = Ω(n)。

结合上下界，T(n) = Θ(n)，即时间复杂度为O(n)。

最坏与最优场景分析 #

• 最坏场景：memo数组初始全为0，且首次计算fib(n)。此时每个fib(k)（2 ≤ k ≤ n）都需要被计算一次，总时间为Θ(n)。
• 最优场景：memo数组已预先填充fib(0)到fib(n)的所有值，或之前已计算过fib(n)。此时直接返回memo[n]，时间复杂度为O(1)。

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