基本情况 $f(1) = f(2) = 1$ 在这个分析中起什么作用？

适用条件

• 递推关系为 $f(n) = f(n-1) + f(n-2)$。
• 基本情况为 $f(1) = 1$ 和 $f(2) = 1$。
• 复杂度分析使用满二叉树进行理论估算。

理解与推导

1. 识别基本情况 $f(1) = 1$ 和 $f(2) = 1$。
2. 认识到当分支到达这些基本情况时停止分裂。
3. 注意到由于这种截断，实践中不需要绘制完整的树。
4. 理解节点数的理论估算仍然假设满二叉树，以得出上界 $O(2^n)$。

例子

然后，讲师补充了一个重要的区别：因为基本情况是 $f(1)=f(2)=1$，所以在绘制时不需要完全展开整棵树；但对于理论分析，我们仍然将规模估算为“这么多节点”。换句话说，图中显示的省略号仅仅是绘图的简化，并不改变复杂度分析的对象。

容易误解的地方

• 看到图中没有画出完整的树，可能会错误地认为递归调用的理论规模也减小了。
• 假设基本情况改变了时间复杂度的渐近上界。

观看对应讲解

继续追问

• 如何通过对每层节点数求和得出 $O(2^n)$？
• 为什么每层的节点数是 2 的幂？
• 这个递归算法的时间复杂度是多少？