算法中的Big O表示法：为何f(n)=n²+3n+2增长速度快于g(n)

非形式化定义下，O(g(n))是所有增长速度不超过g(n)的数学函数构成的集合，因此以下函数都属于O(n²)集合：
f(n) = n²+3n + 2, f(n) = n log(n), f(n) = 3n+1

首先要明确：你提到的“f(n) = n²+3n + 2增长速度快于g(n)”是误解，这里O(n²)对应的g(n)就是g(n) = n²，二者的渐进增长速度是同阶的，完全符合“增长速度不超过g(n)”的要求，因此可以归入O(n²)集合。

具体说明如下：

• 大O表示法描述的是n趋近于无穷大时的渐进上界，判定规则为：只要存在正的常数c和自然数n₀，当所有n ≥ n₀时，都满足f(n) ≤ c * g(n)，就可以判定f(n)属于O(g(n))。它只关心最高阶的增长趋势，会忽略低阶项和常数系数的差异。
• 对f(n) = n²+3n + 2的验证非常简单：当n ≥ 1时，3n ≤ 3n²、2 ≤ 2n²，代入原式可得f(n) ≤ n² + 3n² + 2n² = 6n²，也就是取c=6、n₀=1时，完全满足大O的判定规则，因此它属于O(n²)集合。
• 我们也可以通过极限计算验证二者的增长阶：lim(n→∞) f(n)/g(n) = lim(n→∞) (n²+3n+2)/n² = 1，结果为有限常数，说明二者的渐进增长速度是同阶的，f(n)并没有比g(n)增长更快，只是同等规模下的绝对数值更大而已。
• 补充说明：大O是宽松的上界定义，只要增长阶不高于g(n)的函数都可以归入O(g(n))，因此比n²低阶的n log(n)、3n+1自然也符合O(n²)的要求。

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