如何求常数c和n0以证明f(n) = n log n为Ω(n)？

认知修正：渐进符号与算法场景无关 #

你之前对三个符号的理解存在一个常见的入门误区：大O、大Ω、大Θ本身是描述函数渐进增长边界的数学工具，和算法的最好/最坏/平均运行场景是完全独立的概念：你可以用大O描述算法最好情况的增长上界，也可以用大Ω描述最坏情况的增长下界，二者没有绑定关系。三个符号的核心定义可以简化为：

• 大O(f(n))：所有增长速度不超过f(n)的函数集合，对应上界
• 大Ω(f(n))：所有增长速度不低于f(n)的函数集合，对应下界
• 大Θ(f(n))：所有增长速度和f(n)完全同阶的函数集合，是同时满足大O和大Ω要求的紧界

证明n log n = Ω(n) #

首先给出大Ω的严格数学定义：我们称g(n) = Ω(f(n))，当且仅当存在正的常数c和n₀，使得对于所有n ≥ n₀，都有0 ≤ c·f(n) ≤ g(n)成立。
本次证明中g(n) = n log n，f(n) = n，我们只需要找到符合要求的c和n₀即可：

1. 先对不等式两边同时除以n（输入规模n默认≥1，除以正数不改变不等号方向），不等式简化为c ≤ log n
2. 算法领域默认log底数为2（换底数只会带来常数倍差异，不影响渐进结论），我们可以任意取正的c值，这里取c=1
3. 代入简化后的不等式得1 ≤ log n，等价于n ≥ 2^1 = 2，因此取n₀=2
4. 验证：当n≥2时，1·n ≤ n log n恒成立，完全符合大Ω的定义
   因此n log n = Ω(n)得证。

常数因子c的作用 #

渐进符号的核心是描述n趋近于无穷大时，函数的核心增长趋势，我们不需要关心小输入规模下的数值差异，也不需要关心函数本身的常数倍缩放——比如运行时间为100n的算法和2n的算法，都是线性增长，属于同一复杂度等级，不需要做区分。
常数c的作用就是吸收这些不影响核心增长趋势的常数倍差异：不管原函数前面带有多大或者多小的常数系数，只要能找到一个固定的正c，让不等式在n足够大时恒成立，就说明两个函数的增长速度满足对应的上下界关系。
举个简单例子：如果要证明0.5n = Ω(n)，我们只需要取c=0.2，n₀=1，就能保证0.2·n ≤ 0.5n对所有n≥1成立，不需要纠结0.5比1小的问题，本质上就是忽略常数倍的差异，只看核心的增长阶。 #

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