为什么视频提到 2 的 0 次方加到 2 的 6 次方等于 2 的 7 次方减 1？

适用条件

• 求和从 $2^0$ 开始。
• 公比为 2。
• 最后一项是 $2^6$。

理解与推导

1. 识别出需要对树的所有层级的节点数求和。
2. 提供具体的例子 $2^0+2^1+\cdots+2^6=2^7-1$。
3. 使用这个方程说明几何级数的和等于下一个次幂减一。
4. 得出总体规模由最高次幂主导的结论，从而引出 $O(2^n)$。

例子

讲师说：将 2 的 0 次方，加上 2 的 1 次方，依此类推直到 2 的 6 次方，实际上等于 2 的 7 次方减 1。这个方程本身是一个经典的有限几何级数求和，视频用它来支持这样的结论：当层数随输入规模增长时，节点总数由最高阶项主导。

容易误解的地方

• 认为这个特定的求和是 $f(7)$ 时间复杂度的确切公式，而不是几何级数的说明性例子。
• 假设视频提供了通用求和公式的严格形式化证明，而实际上它只给出了一个具体的口头例子。

观看对应讲解

继续追问

• 如何通过对每层节点数求和得出 $O(2^n)$？
• 视频中 $O(2^n)$ 被称为什么？
• 基本情况 $f(1) = f(2) = 1$ 在这个分析中起什么作用？