如何通过对每层节点数求和得出 $O(2^n)$？

适用条件

• 时间成本通过递归调用的次数来衡量。
• 采用使用完美二叉树的上界估计。
• 求和从 $2^0$ 开始，公比为 2。

理解与推导

1. 将每层的节点数计算为 2 的幂（$2^0, 2^1, 2^2, \dots$）。
2. 对所有层级的节点数求和以找到树的总规模。
3. 使用几何级数示例 $2^0+2^1+\cdots+2^6=2^7-1$ 来说明增长趋势。
4. 观察到总和由最高次幂主导。
5. 得出时间复杂度为 $O(2^n)$ 的结论。

例子

为了说明这种求和的增长趋势，他给出了一个具体的例子：$2^0+2^1+\cdots+2^6=2^7-1$。这个方程本身是一个经典的有限几何级数求和，视频用它来支持这样的结论：当层数随输入规模增长时，节点总数由最高阶项主导，因此时间复杂度可以写为 $O(2^n)$。

容易误解的地方

• 假设对于任何 $n$，节点的确切数量总是 $2^n - 1$，而不是将其用作渐近上界。
• 认为基本情况的截断降低了复杂度的理论指数规模。

观看对应讲解

继续追问

• 为什么视频提到 2 的 0 次方加到 2 的 6 次方等于 2 的 7 次方减 1？
• 视频中 $O(2^n)$ 被称为什么？
• 基本情况 $f(1) = f(2) = 1$ 在这个分析中起什么作用？