O(N)时间复杂度斐波那契生成器技术问询（基于《编程面试金典》）

嘿，刚好最近也在啃《编程面试金典》（第6版）的Big O章节，看到你提到的示例15，咱们来拆解下这段代码的复杂度和设计思路吧！

首先先把这段Java代码贴出来，方便大家对照：

void allFib(int n){ 
    int[] memo = new int[n+1]; 
    for(int i=0; i<n; i++){ 
        System.out.println(i + ":" + fib(i,memo)); 
    } 
}

int fib(int n, int[] memo){ 
    if(n<=0) return 0; 
    else if(n==1) return 1; 
    else if(memo[n]>0) return memo[n]; 
    memo[n]=fib(n-1,memo)+fib(n-2,memo); 
    return memo[n]; 
}

核心复杂度分析 #

这段代码用了**备忘录（Memoization）**来优化斐波那契数列的计算，直接把普通递归版的指数级复杂度砍到了线性：

• 时间复杂度：O(n)
  原因很简单：每个斐波那契数fib(i)只会被实际计算一次。当第一次计算fib(i)时，会递归计算fib(i-1)和fib(i-2)，但这些值都会存在memo数组里；之后再调用fib(i)（比如allFib循环里的后续调用，或者递归过程中重复用到），直接从memo里取值，是O(1)的操作。整个allFib循环执行n次，总操作数是线性的n级别。

• 空间复杂度：O(n)
  主要来自两部分：一是存储计算结果的memo数组，大小是n+1；二是递归调用栈的深度，最坏情况下递归到fib(1)，栈深度是n，所以整体空间复杂度是O(n)。

和普通递归版的对比 #

如果是不带备忘录的普通递归斐波那契，时间复杂度是O(2^n)——因为每个数都会被重复计算无数次，比如fib(5)会重复计算fib(3)两次、fib(2)三次，以此类推。而备忘录的本质就是用空间换时间，把已经计算过的结果缓存起来，避免重复计算，这也是动态规划里“自顶向下”解法的典型例子。

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