1. 定位导航假设一个算法的运行时间可以写成T(n)3n210n100 T(n) 3n^2 10n 100T(n)3n210n100前面已经知道它的主要增长趋势是平方级因此可以说它和n2n^2n2属于同一类增长量级。但如果进一步追问它是 O(n²) 吗 它是 Ω(n²) 吗 它是 Θ(n²) 吗这三个问题看起来很像但含义并不一样。2. 概念术语术语直观含义常见理解O 记号上界增长不会超过这个级别Ω 记号下界增长至少达到这个级别Θ 记号紧确界上下界都在这个级别上界天花板运行时间最多被它盖住下界地板运行时间至少不会低于它渐近输入规模足够大时忽略小规模下的局部差异常数倍允许乘一个固定常数3n23n^23n2和n2n^2n2属于同一量级关键澄清O不是“精确等于”它只是上界。Ω不是“最坏情况”它是下界。Θ才表示增长级别被上下界共同确定。很多时候口语里说“复杂度是 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)3n210n100 T(n) 3n^2 10n 100T(n)3n210n100当n足够大时可以找到一个常数c让T(n)≤cn2 T(n) \le c n^2T(n)≤cn2例如选择c 5当n足够大时3n210n100≤5n2 3n^2 10n 100 \le 5n^23n210n100≤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)3n210n100 T(n) 3n^2 10n 100T(n)3n210n100很容易看到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)3n210n100 T(n) 3n^2 10n 100T(n)3n210n100我们可以同时找到两个常数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²)下面用一个动态图把判断过程串起来。过程可以分成四步先观察目标函数T(n)T(n)T(n)找到一个上界函数说明它是O(n2)O(n^2)O(n2)找到一个下界函数说明它是Ω(n2)\Omega(n^2)Ω(n2)上下界同时成立所以得到Θ(n2)\Theta(n^2)Θ(n2)。这就是复杂度边界判断的核心逻辑。8. 数值推演看一个具体例子T(n)3n210n100 T(n) 3n^2 10n 100T(n)3n210n100我们尝试用n2n^2n2来描述它。nT(n)2n²5n²是否满足2n2≤T(n)≤5n22n² \le T(n) \le 5n²2n2≤T(n)≤5n210500200500满足2015008002000满足508100500012500满足100311002000050000满足可以看到从某个规模开始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*n10*n100defcheck_bounds(n):lower2*n*n upper5*n*n valueT(n)returnlowervalueupperfornin[1,5,10,20,50,100,1000]:print(fn{n:4}f2n²{2*n*n:8}fT(n){T(n):10}f5n²{5*n*n:10}f是否夹住{check_bounds(n)})可能输出n1 2n²2 T(n)113 5n²5 是否夹住False n5 2n²50 T(n)225 5n²125 是否夹住False n10 2n²200 T(n)500 5n²500 是否夹住True n20 2n²800 T(n)1500 5n²2000 是否夹住True n50 2n²5000 T(n)8100 5n²12500 是否夹住True n100 2n²20000 T(n)31100 5n²50000 是否夹住True n1000 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. 现代延伸复杂度记号在工程系统里并不抽象它经常决定一个系统是否能扩展。场景复杂度视角全表扫描通常是O(n)哈希索引查找平均接近O(1)B 树索引通常接近O(log n)排序常见比较排序是O(n log n)嵌套循环 Join可能接近O(n²)图遍历常写作O(V E)注意力计算标准注意力常与序列长度平方相关例如数据库查询优化器本质上就是在多个执行计划之间估算成本避免选中增长过快的路径。再比如大模型推理中序列长度越长注意力计算和 KV Cache 管理都会带来明显成本复杂度视角可以帮助判断瓶颈在哪里。12. 思考题为什么说O(n²)只是上界不一定是精确复杂度一个函数如果是Θ(n²)它一定是O(n²)吗一定是Ω(n²)吗为什么T(n)n也可以说是O(n²)这种说法有什么问题Ω为什么不能简单理解成“最坏情况”对于T(n)7n log n 20n 300它的紧确界应该是什么13. 本篇小结本篇讲清楚了三种最重要的复杂度记号O表示上界像天花板Ω表示下界像地板Θ表示紧确界说明上下界同时成立如果一个函数既是O(g(n))又是Ω(g(n))那么它就是Θ(g(n))日常说“大 O 复杂度”时要注意是否只是上界还是已经隐含了紧确增长级别。后面继续学习时看到复杂度表达式不要只机械记忆符号而要问它是在描述上界、下界还是准确增长级别