NOIP 提高 2013 第一轮 第 7 题：斐波那契数列的定义如下：F_1 = 1, F_2 = 1, F_n = F_{n

题目

斐波那契数列的定义如下：$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);
}

选项

• A. $O(1)$
• B. $O(n)$
• C. $O(n^2)$
• D. $O(F_n)$

答案

D

题解

考点定位

本题考「递归斐波那契复杂度」,对应大纲 4.1.1 复杂度（难度【3】）。

解题过程

朴素递归 F(n)=F(n−1)+F(n−2)：调用次数 Θ(Fₙ)（黄金比增长率），比 2ⁿ 精确。选项中 O(Fₙ) 最准确。

选 D。

易错提醒

① 递归调用次数 T(n)=T(n−1)+T(n−2)+1 ⇒ T(n)=2Fₙ−1；② O(2ⁿ) 是粗上界，Fₙ≈φⁿ/√5 更紧。