f(n)属于O(g(n))时，是否可能与g(n)拥有相同的增长速率？

结论 #

完全有可能，这本身就是大O记号定义覆盖的合法场景。

核心原因 #

大O记号本质是渐近上界的描述，从来没有要求f(n)的增长速度必须严格慢于g(n)。
先看大O的标准定义：

对于非负函数f(n)和g(n)，如果存在正的常数C和n₀，使得所有满足n ≥ n₀的n都符合0 ≤ f(n) ≤ C·g(n)，就可以记作f(n) = O(g(n))。
从定义就能看出来，只要f(n)的增长不超过g(n)的常数倍就符合要求，完全允许两者增长速率相等的情况。

示例验证 #

比如取f(n) = 3n²，g(n) = n²：
显然存在C=3、n₀=1，使得所有n≥1时3n² ≤ 3*n²成立，完全符合f(n) = O(g(n))的要求，而两者的增长速率完全相同，都属于平方阶复杂度。

易混淆记号区分 #

如果需要更精准的速率描述，可以用另外两个渐近记号：

• 要表示f(n)严格慢于g(n)，用小o记号o(g(n))，其定义为极限lim(n→∞) f(n)/g(n) = 0，不存在等于的情况
• 要表示f(n)和g(n)增长速率完全相等，用Θ记号Θ(g(n))，要求同时满足f(n) = O(g(n))和g(n) = O(f(n))

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