算法基础（六）—— 大 O、Ω、Θ如何描述算法增长边界

1. 定位导航

假设一个算法的运行时间可以写成：

T(n)=3n2+10n+100 T(n) = 3n^2 + 10n + 100T(n)=3n2+10n+100

前面已经知道，它的主要增长趋势是平方级，因此可以说它和n2n^2n2属于同一类增长量级。

但如果进一步追问：

它是 O(n²) 吗？ 它是 Ω(n²) 吗？ 它是 Θ(n²) 吗？

这三个问题看起来很像，但含义并不一样。

2. 概念术语

关键澄清：

1. O不是“精确等于”，它只是上界。
2. Ω不是“最坏情况”，它是下界。
3. Θ才表示增长级别被上下界共同确定。
4. 很多时候口语里说“复杂度是 O(n²)”，其实真正想表达的是“Θ(n²)”。

3. 为什么需要三种记号

同一个函数，可以从不同角度被描述。

可以把三种记号想成：

O：天花板 Ω：地板 Θ：上下都夹住

比如一个人的身高是 180cm。

你可以说：

他不超过 200cm

这是上界。

也可以说：

他至少超过 150cm

这是下界。

但如果说：

他的身高大约就是 180cm 这个级别

这才更接近紧确描述。

算法增长也类似。

4. O 记号：描述上界

4.1 直观理解

O记号描述的是上界。

如果说：

T(n)=O(n2) T(n) = O(n^2)T(n)=O(n2)

直观意思是：

当 n 足够大以后，T(n) 不会比某个常数倍的 n² 增长得更快。

换句话说，O(n²)像一个天花板，把T(n)盖住。

4.2 例子

仍然看：

T(n)=3n2+10n+100 T(n) = 3n^2 + 10n + 100T(n)=3n2+10n+100

当n足够大时，可以找到一个常数c，让：

T(n)≤cn2 T(n) \le c n^2T(n)≤cn2

例如选择c = 5，当n足够大时：

3n2+10n+100≤5n2 3n^2 + 10n + 100 \le 5n^23n2+10n+100≤5n2

所以：

T(n)=O(n2) T(n) = O(n^2)T(n)=O(n2)

4.3 注意

如果一个函数是O(n²)，它也可以是O(n³)、O(n⁴)。

因为更高的函数也能作为上界。

但我们通常希望找一个尽可能贴近的上界，否则描述会太松。

5. Ω 记号：描述下界

5.1 直观理解

Ω记号描述的是下界。

如果说：

T(n)=Ω(n2) T(n) = \Omega(n^2)T(n)=Ω(n2)

直观意思是：

当 n 足够大以后，T(n) 至少不会低于某个常数倍的 n²。

换句话说，Ω(n²)像一个地板，托住T(n)。

5.2 例子

对于：

T(n)=3n2+10n+100 T(n) = 3n^2 + 10n + 100T(n)=3n2+10n+100

很容易看到：

T(n)≥2n2 T(n) \ge 2n^2T(n)≥2n2

当n足够大时，这个不等式成立。

所以：

T(n)=Ω(n2) T(n) = \Omega(n^2)T(n)=Ω(n2)

5.3 注意

下界不是“最坏情况”。

它只是在描述某个函数增长至少达到什么程度。

不要把：

Ω = 最坏情况

这样理解，这是常见误区。

6. Θ 记号：描述紧确界

6.1 直观理解

Θ记号描述紧确界。

如果说：

T(n)=Θ(n2) T(n) = \Theta(n^2)T(n)=Θ(n2)

意思是：

当 n 足够大以后，T(n) 既不会超过某个常数倍 n²，也不会低于某个常数倍 n²。

也就是同时满足：

T(n)=O(n2) T(n) = O(n^2)T(n)=O(n2)

和：

T(n)=Ω(n2) T(n) = \Omega(n^2)T(n)=Ω(n2)

6.2 例子

对于：

T(n)=3n2+10n+100 T(n) = 3n^2 + 10n + 100T(n)=3n2+10n+100

我们可以同时找到两个常数：

2n2≤T(n)≤5n2 2n^2 \le T(n) \le 5n^22n2≤T(n)≤5n2

当n足够大时成立。

因此：

T(n)=Θ(n2) T(n) = \Theta(n^2)T(n)=Θ(n2)

6.3 为什么 Θ 更精确

O(n²)只说明它不超过平方级。

Ω(n²)只说明它至少达到平方级。

Θ(n²)说明它基本就是平方级。

所以如果你想表达“这个算法的增长级别就是平方级”，更准确的说法是：

Θ(n2) \Theta(n^2)Θ(n2)

7. 动态推演：从函数到 Θ(n²)

下面用一个动态图，把判断过程串起来。

过程可以分成四步：

1. 先观察目标函数T(n)T(n)T(n)；
2. 找到一个上界函数，说明它是O(n2)O(n^2)O(n2)；
3. 找到一个下界函数，说明它是Ω(n2)\Omega(n^2)Ω(n2)；
4. 上下界同时成立，所以得到Θ(n2)\Theta(n^2)Θ(n2)。

这就是复杂度边界判断的核心逻辑。

8. 数值推演

看一个具体例子：

T(n)=3n2+10n+100 T(n) = 3n^2 + 10n + 100T(n)=3n2+10n+100

我们尝试用n2n^2n2来描述它。

可以看到，从某个规模开始，T(n)T(n)T(n)稳定地夹在2n22n^22n2和5n25n^25n2中间。

所以可以说：

T(n)=Θ(n2) T(n) = \Theta(n^2)T(n)=Θ(n2)

9. 代码实践

下面用 Python 验证这个夹逼关系：

defT(n):return3*n*n+10*n+100defcheck_bounds(n):lower=2*n*n upper=5*n*n value=T(n)returnlower<=value<=upperfornin[1,5,10,20,50,100,1000]:print(f"n={n:<4}"f"2n²={2*n*n:<8}"f"T(n)={T(n):<10}"f"5n²={5*n*n:<10}"f"是否夹住={check_bounds(n)}")

可能输出：

n=1 2n²=2 T(n)=113 5n²=5 是否夹住=False n=5 2n²=50 T(n)=225 5n²=125 是否夹住=False n=10 2n²=200 T(n)=500 5n²=500 是否夹住=True n=20 2n²=800 T(n)=1500 5n²=2000 是否夹住=True n=50 2n²=5000 T(n)=8100 5n²=12500 是否夹住=True n=100 2n²=20000 T(n)=31100 5n²=50000 是否夹住=True n=1000 2n²=2000000 T(n)=3010100 5n²=5000000 是否夹住=True

注意看：小规模时可能不满足，但从n = 10开始就稳定满足。

这就是“渐近”的含义：只要求输入规模足够大以后成立。

10. 常见误区

误区一：O 就是精确复杂度

不是。O只是上界。

如果一个函数是：

T(n)=n T(n) = nT(n)=n

那么它也是：

O(n2) O(n^2)O(n2)

因为n2n^2n2也能作为它的上界，只是这个上界太松。

误区二：Ω 表示最坏情况

不是。Ω是下界，它和最好、最坏、平均情况不是同一个维度。

你可以说：

最坏情况下是 Ω(n²)

也可以说：

最好情况下是 Ω(n)

关键看你描述的是哪个运行时间函数。

误区三：Θ 和 O 可以随便混用

不严谨。

如果已经知道上下界一致，应该用Θ表达更准确。

口语里常说“复杂度 O(n²)”，但严格来说，很多时候想表达的是“Θ(n²)”。

误区四：只要大 O 一样，性能就完全一样

不对。

两个算法都属于O(n²)，但常数因子、缓存友好性、实现方式不同，实际性能可能差很多。

复杂度用于判断大规模趋势，工程落地仍然需要测试。

11. 现代延伸

复杂度记号在工程系统里并不抽象，它经常决定一个系统是否能扩展。

例如数据库查询优化器，本质上就是在多个执行计划之间估算成本，避免选中增长过快的路径。

再比如大模型推理中，序列长度越长，注意力计算和 KV Cache 管理都会带来明显成本，复杂度视角可以帮助判断瓶颈在哪里。

12. 思考题

1. 为什么说O(n²)只是上界，不一定是精确复杂度？
2. 一个函数如果是Θ(n²)，它一定是O(n²)吗？一定是Ω(n²)吗？
3. 为什么T(n)=n也可以说是O(n²)？这种说法有什么问题？
4. Ω为什么不能简单理解成“最坏情况”？
5. 对于T(n)=7n log n + 20n + 300，它的紧确界应该是什么？

13. 本篇小结

本篇讲清楚了三种最重要的复杂度记号：

• O表示上界，像天花板；
• Ω表示下界，像地板；
• Θ表示紧确界，说明上下界同时成立；
• 如果一个函数既是O(g(n))，又是Ω(g(n))，那么它就是Θ(g(n))；
• 日常说“大 O 复杂度”时，要注意是否只是上界，还是已经隐含了紧确增长级别。

后面继续学习时，看到复杂度表达式，不要只机械记忆符号，而要问：

它是在描述上界、下界，还是准确增长级别？