如何使用递归树分析递归算法的时间复杂度？

适用条件

• 递归算法可以用递归树清晰地表示。
• 假设每次函数调用的开销（不包括递归调用）是恒定的。

理解与推导

1. 将递归过程转换为可视化的递归树。
2. 将每个节点的计算意义定义为一次函数调用计算单元。
3. 认识到分析时间复杂度等同于计算树中节点的总数。
4. 对树的所有层级的节点数求和，以确定计算操作的总数。

例子

讲师介绍了分析此类递归算法时间复杂度的核心方法：将递归树中的每个节点视为一个“计算单元”。因此，评估总执行成本简化为一个简单的计数问题——计算递归树中的节点总数（包括内部节点和叶子节点）。

容易误解的地方

• 假设时间复杂度仅取决于树的深度，而不是节点的总数。
• 忘记叶子节点（基本情况）也算作计算单元。

观看对应讲解

继续追问

• 递归树中每层的节点数遵循什么规律？
• 为什么视频提到 2 的 0 次方加到 2 的 6 次方等于 2 的 7 次方减 1？
• 这个递归算法的时间复杂度是多少？