NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 7 题

斐波那契数列的定义如下：$F_1 = 1, F_2 = 1, F_n = F_{n - 1} + F_{n - 2} (n \geq 3)$。如果用下面的函数计算斐波那契数列的第 $n$ 项，则其时间复杂度为（ ）。

int F(int n) 
{ 
 if (n <= 2) 
  return 1; 
 else 
  return F(n - 1) + F(n - 2); 
}

别被'递归'两个字骗了，这道题考的是递归调用次数和斐波那契数值本身的增长关系。拿到题先别急着套公式，画个 n=4 的递归树，你会发现它长得跟数列本身一模一样，这是解题的关键直觉。

最容易栽跟头的就是凭感觉选 O(2^n)，觉得每次分支翻倍嘛。但斐波那契递归树是‘瘦高’的，很多分支会提前合并，实际调用次数远小于 2 的 n 次方。还有人会混淆迭代写法，以为只要 n 层递归就是 O(n)，忘了递归里其实藏着巨大的重复计算。

这道题考什么

这道题的核心是递归函数的时间复杂度分析，具体来说，是考察你对递归调用次数与斐波那契数列数值增长之间关系的理解。很多学生看到递归就想到 O(2^n) 或者 O(n)，但斐波那契这个特例非常典型，它的递归调用次数竟然跟数列本身的值 F_n 是同一个数量级。

概念：递归是怎么算时间的

我们通常用递推方程来算递归的时间复杂度。设 T(n) 为计算 F(n) 的时间，那么根据代码逻辑：

• 当 n <= 2 时，直接返回，时间常数 O(1)。
• 当 n > 2 时，要调用一次 F(n-1) 和一次 F(n-2)，再加上一次加法操作。

所以递推方程就是： $$T(n) = T(n-1) + T(n-2) + O(1)$$

这个方程长得跟斐波那契数列的定义 $F_n = F_{n-1} + F_{n-2}$ 简直一模一样，只是多了一个常数项。这意味着 T(n) 的增长速度和 F_n 的增长速度是同阶的。