小o与Ω记号关系：f(n)=Ω(g(n))时f(n)=o(g(n))是否成立

这个命题永远不成立：既不能从𝑓(𝑛) = Ω(𝑔(𝑛))推导出𝑓(𝑛) = 𝑜(𝑔(𝑛))，两个集合也不存在包含关系，更不可能相等。

我们直接从两个渐近记号的标准定义就能看出矛盾：

• Ω(g(n))：存在正常数c和n₀，使得对所有n ≥ n₀，满足0 ≤ c·g(n) ≤ f(n)。核心含义是f(n)的增长速度不会比g(n)慢，增长阶的下界是g(n)。
• o(g(n))：对任意正常数c，都存在n₀，使得对所有n ≥ n₀，满足0 ≤ f(n) < c·g(n)。核心含义是f(n)的增长速度严格比g(n)慢，属于比g(n)低阶的量级。

两个要求本身是互斥的（算法复杂度场景下不会考虑无意义的零值函数）：
如果f(n)属于Ω(g(n))，就说明至少存在一个正的常数c，能让f(n)在n足够大时始终大于等于c·g(n)；但o(g(n))的要求是，对所有正的常数c，f(n)在n足够大时都要小于c·g(n)，两个条件不可能同时满足。也就是说不存在任何f(n)、g(n)组合能同时满足f(n)=Ω(g(n))和f(n)=o(g(n))。

我们取最常见的幂函数举例就能验证：

1. 取f(n)=n，g(n)=n：
   • f(n)=Ω(g(n))成立，取c=1，n≥1时n ≥ 1·n恒成立
   • f(n)=o(g(n))完全不成立，哪怕取c=0.5，n < 0.5n永远不可能成立
2. 反过来取f(n)=n，g(n)=n²：
   • f(n)=o(g(n))成立，不管c取多小的正数，只要n>1/c，就有n < c·n²
   • f(n)=Ω(g(n))不成立，不存在任何正常数c能让n ≥ c·n²对足够大的n恒成立

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