为何$3^n = O(2^n)$不成立而$2^n = O(3^n)$成立？证明误区解析

嘿，这个问题的核心是你在处理对数不等式的时候忽略了不等号方向的反转，咱们一步步捋清楚：

首先得明确大O符号的严格定义：如果说 $f(n) = O(g(n))$，意味着存在两个常数 $c>0$ 和 $n_0 \geq 0$，使得对于所有 $n \geq n_0$，都有 $f(n) \leq c \cdot g(n)$ 成立。重点是「所有足够大的n」都要满足，不是某几个n。

为什么 $3^n = O(2^n)$ 确实不成立 #

你的这部分推导是对的：

• 从 $3^n \leq c \times 2^n$ 变形得到 $\left(\frac{3}{2}\right)^n \leq c$
• 因为 $\frac{3}{2} > 1$，$\left(\frac{3}{2}\right)^n$ 是随n增大指数增长的函数，不管你选多大的c，只要n足够大，这个式子一定会不成立（比如c=1000，n=20时 $\left(\frac{3}{2}\right)^{20} \approx 3325$，远大于1000）
• 你推导到 $n \leq \frac{\log_2 c}{\log_2(3/2)}$，这里右边是个固定常数，意味着只有n小于这个数时式子成立，但大O要求所有足够大的n都成立，显然做不到，所以命题不成立。

你推导 $2^n = O(3^n)$ 时的错误 #

这里的关键坑点出在对数的符号和不等号的处理：

• 从 $2^n \leq c \times 3^n$ 变形得到 $\left(\frac{2}{3}\right)^n \leq c$，这一步没问题
• 接下来两边取 $\log_2$（因为 $\log_2$ 是单调递增函数，不等号方向不变），得到 $n \times \log_2\left(\frac{2}{3}\right) \leq \log_2 c$
• 注意！$\log_2\left(\frac{2}{3}\right)$ 是负数（因为 $\frac{2}{3} < 1$，底数大于1的对数函数中，小于1的数的对数为负）。当你把不等式两边除以一个负数时，不等号方向必须反转！
• 所以正确的推导应该是：$n \geq \frac{\log_2 c}{\log_2(2/3)}$

现在看这个结论：

• 比如我们选 $c=1$，$\log_2 1 = 0$，右边就是 $\frac{0}{\log_2(2/3)} = 0$，也就是 $n \geq 0$。这意味着所有自然数n都满足 $\left(\frac{2}{3}\right)^n \leq 1$，显然成立，因为小于1的数的非负整数次方都不会超过1，对应的 $2^n \leq 1 \times 3^n$ 也恒成立。
• 就算选更大的c，比如c=2，右边是 $\frac{1}{\log_2(2/3)} \approx -1.71$，也就是 $n \geq -1.71$，对于自然数n来说，所有n≥0都满足，同样符合大O的定义。

说白了，你之前的推导没处理负数除法导致的不等号反转，把结论搞反了，才误以为这个真命题不成立。

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