CSP-S 2021 第一轮 第12题：斐波那契数列的定义为：F1=1，F2=1，Fn=Fn-1+Fn-2（n =3)。

题目

斐波那契数列的定义为： $F_{1}=1$，$F_{2}=1$，$F_{n}=F_{n-1}+F_{n-2}$$(n\geq 3)$ 。现在用如下程序来计算斐波那契数列的第 $n$ 项，其时间复杂度为（ ）。

F(n):
  if n<=2 return 1
  else return F(n-1) + F(n-2)

选项

• A. $O(n)$
• B. $O(n^{2})$
• C. $O(2^{n})$
• D. $O(n\ log\ n)$

答案

C

题解

选 C. \(O(2^n)\)。

当 \(n>2\) 时，每次调用都会递归计算 F(n-1) 和 F(n-2)，所以时间满足： \[ T(n)=T(n-1)+T(n-2)+O(1). \]

把递归过程看成一棵树：

• 每个节点最多产生 2 个子节点；
• 递归深度不超过 \(n\)；
• 因而总节点数不超过 \(1+2+4+\cdots+2^{n-1}=2^n-1\)。

每个节点自身的操作是常数时间，因此时间复杂度为 \(O(2^n)\)。耗时的原因是大量重复计算，比如 F(n-2) 既会直接计算，又会在 F(n-1) 中再次计算。

严格来说，更紧确的复杂度是 \(\Theta\!\left(\left(\frac{1+\sqrt5}{2}\right)^n\right)\)，但本题给出的选项中应选 C。