CSP-S 提高级 · CSP 2021 提高级第一轮 第 12 题

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

这题其实就考递归树和递推式两个视角，只要意识到每次调用都会分叉成两路，就能直接看出是指数级爆炸，别被‘斐波那契本身是 O(n)’的直觉带偏。

最容易选错 A 或 B，觉得递归 n 次或 n²次就够了。其实递归不是简单循环，每层都要拆成两个子问题，调用次数会像树枝一样疯狂分叉。另一种常见错误是以为斐波那契本身是 O(n)（指用循环实现的迭代版本），但题目明确是递归实现，必须按递归树或递推式来算。

考察知识点

递归函数、时间复杂度分析、斐波那契数列

概念定义

• 时间复杂度：算法执行时间随输入规模增长的增长率，用大 O 表示法描述上界。
• 递归斐波那契：$F(n) = F(n-1) + F(n-2)$，未做任何优化（无记忆化）。
• 递推关系法分析时间：设$T(n)$为计算$F(n)$所需时间，则$T(n) = T(n-1) + T(n-2) + O(1)$。