判断表达式6n^4−3n^2+3是否具有Ω(n⁴)复杂度

大Ω（Ω）复杂度的核心定义 #

函数$f(n)$属于$\Omega(g(n))$，当且仅当存在正常数$c$和正整数$n_0$，使得对所有$n \geq n_0$，都满足：
$$f(n) \geq c \cdot g(n)$$
本质是说，当$n$足够大时，$f(n)$的增长速度不会慢于$g(n)$——$g(n)$是$f(n)$的一个渐近下界。

代入例子验证 #

对于$f(n)=6n^4 -3n^2 +3$和$g(n)=n^4$，我们可以直接构造符合条件的$c$和$n_0$：

• 取$c=5$，需要证明当$n$足够大时，$6n^4 -3n^2 +3 \geq 5n^4$。
• 整理不等式得：$n^4 -3n^2 +3 \geq 0$。令$k=n^{2$（$k>0$），式子变为二次函数$k}2 -3k +3$，其判别式$\Delta=9-12=-3<0$，且二次项系数为正，因此该函数对所有$k>0$恒大于0。
• 这意味着对所有$n \geq 1$，$n^4 -3n^2 +3 \geq 0$都成立，即$f(n) \geq 5n^4$。

显然存在$c=5$和$n_0=1$满足大Ω的定义，因此原语句为真。

大O与大Ω的区别补充 #

你提到大O情况下该语句肯定为真，这个判断完全正确：大O描述的是渐近上界，$f(n)=6n^4 -3n^2 +3$显然被$n^{4$的常数倍上界约束（比如取$c=12$，当$n\geq1$时，$f(n)\leq6n}4+3n⁴⁺³ⁿ4=12n^4$）。
而大Ω是渐近下界，核心是证明$f(n)$不会比$g(n)$增长得慢，这次的例子里我们通过构造不等式，直接验证了这一点。

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