视频中 $O(2^n)$ 被称为什么？

适用条件

• 复杂度具有 $O(2^n)$ 或类似的指数增长形式。
• 背景是对推导出的时间复杂度进行命名和分类。

理解与推导

1. 通过计算递归树中的节点总数得出时间复杂度 $O(2^n)$。
2. 将这个特定结果命名为“指数复杂度”。
3. 总结使用树计算递归算法时间复杂度的方法。

例子

最后，讲师对这个结果进行了命名：$O(2^n)$ 属于“指数复杂度”。然后他用一句话总结了本段的方法——这是一种使用树来表示或计算递归算法时间复杂度的解决方案。

容易误解的地方

• 将指数复杂度与多项式复杂度混淆。
• 假设所有递归算法都有指数复杂度，而不是仅指这个特定的朴素斐波那契例子。

观看对应讲解

继续追问

• 如何通过对每层节点数求和得出 $O(2^n)$？
• 基本情况 $f(1) = f(2) = 1$ 在这个分析中起什么作用？
• 视频分析了哪个递归函数的时间复杂度？