关于小o阶关系与大O、Ω关系证明的疑问

嗨，这个问题问得特别好——其实核心是要紧扣小o符号的定义本质，以及反证法里矛盾的“明确性”来理解。

先回顾两个关键定义：

• 当我们说 $g(n) \in o(f(n))$，它的核心是：对于任意一个你能想到的正实数c，不管c有多小，只要n足够大，$g(n)$都会被$c \times f(n)$“压在下面”（也就是存在N，当$n\ge N$时$g(n) \le c \times f(n)$）。注意这里是“任意”c，不是“某个”c。
• 而$g(n) \in \Omega(f(n))$的定义是：存在至少一个正实数c，当n足够大时，$g(n)$会被$c \times f(n)$“托在上面”（存在$N_1$，$n\ge N_1$时$g(n) \ge c \times f(n)$）。这里是“存在”某个c，不是“任意”。

接下来看反证的逻辑：
我们假设$g(n) \in \Omega(f(n))$，那必然存在一个固定的$c_0>0$，使得n足够大时$g(n) \ge c_0 \times f(n)$。这时候，根据小o的“任意c”要求，我们可以主动选择一个比$c_0$更小的c——比如$c = c_0/2$（当然选$c_0/3$、$c_0/100$都可以，选1/2只是方便计算）。

为什么不能直接选$c=c_0$？
如果选$c=c_0$，根据小o定义，我们只能得到$g(n) \le c_0 \times f(n)$，结合Ω的假设$g(n) \ge c_0 \times f(n)$，这时候推出的是$g(n) = c_0 \times f(n)$。但这种“等于”的情况，其实已经和小o的定义矛盾了（因为小o要求$\lim_{n \to \infty} \frac{g(n)}{f(n)} = 0$，而等于$c_0$的话极限是$c_0 \neq 0$），但这个矛盾不够“直观”——毕竟等式本身看起来不像直接的冲突。

而选$c = c_0/2$的话，我们得到的是：当n足够大时，$g(n) \le \frac{c_0}{2} \times f(n)$，同时又有$g(n) \ge c_0 \times f(n)$。这时候因为$f(n)$在算法复杂度分析里都是正的函数，所以$\frac{c_0}{2} \times f(n) < c_0 \times f(n)$，直接推出$g(n) < g(n)$——这是一个绝对的、一眼就能看出来的矛盾，比“等于”的情况更有说服力，也避免了对“小o是否允许等于”的歧义（毕竟有些教材里小o的定义用的是$\le$，但本质是严格的渐近更小）。

总结一下：用$\frac{c}{2}$不是必须的，但它能让矛盾更直接、更清晰，完美贴合反证法需要“推出明显荒谬结论”的逻辑。

备注：内容来源于stack exchange，提问作者rosshjb