Big O表示法幂次判定疑问：为何函数的Big O被升幂判定？

两个函数的正确渐近复杂度 #

• 对于 a(n) = 2n + 3n² + nlog(n)，最精确的Big O表示是 O(n²) —— 当n足够大时，3n²是增长最快的项，其他项（2n、nlogn）的增速都远慢于n²，完全可以被常数系数的n²覆盖。
• 对于 b(n) = 5nlog(n) + 10n³ + n²，最精确的Big O表示是 O(n³) —— 10n³是主导项，其他项的增速都赶不上它。

为什么会出现更高次的结果？ #

Big O的严格定义是：只要存在常数C和n₀，当n ≥ n₀时，|f(n)| ≤ C·g(n)，那f(n)就属于O(g(n))。按这个定义：

• a(n)确实能算O(n³)，因为n²的增速远慢于n³，随便找个足够大的C就能满足不等式，但这是过于宽松的上界，没有实际分析价值。
• 同理，b(n)也能算O(n⁴)，但同样是没必要的宽泛结论。

所谓“升幂规则”是误解 #

根本不存在什么升幂规则，算法分析里我们默认用渐近紧上界（也就是增速最慢的那个有效上界），这样才能准确反映算法的实际复杂度。那些给出更高次结果的情况，要么是对Big O的定义理解太死板，要么是混淆了Big O和其他渐近符号（比如Θ才是专门表示紧界的符号）。

结论 #

你最初的判断完全正确，Big O确实表示上界，但我们只会取最紧的那个上界才有意义。更高次的结果虽然符合严格定义，但属于无效的宽泛结论。

内容的提问来源于stack exchange，提问作者Banan