大O表示法中O(n*2^n)是否等价于O(2^n)？

结论很明确：不能，二者是完全不同的复杂度量级。

先回到大O表示法的严格定义：如果要判定f(n) = O(g(n))，必须存在一个固定的正实数常数C，以及一个阈值n₀，使得所有满足n ≥ n₀的输入规模下，都成立f(n) ≤ C * g(n)。简单说就是，当n足够大时，f(n)和g(n)的差距不能超过一个固定的常数倍。

我们把两个函数代入验证：如果n*2^n = O(2^n)成立，就必须存在固定常数C，对所有足够大的n满足：
n * 2^n ≤ C * 2^n
由于2^n恒为正，两边直接约掉这个项，就得到n ≤ C。但输入规模n是可以无限增大的，根本不存在一个固定不变的常数C，能永远比任意大的n还大，因此这个等式不可能成立。

你直觉里认为O(2^n)的复杂度远差于O(n)这个判断是对的，但这里的n不是独立于指数项的低阶项，也不是可以忽略的常数因子：

• n=20时，n*2^n是2^n的20倍
• n=100时，n*2^n是2^n的100倍
• n越大，二者的倍数差会无限制拉大，完全不符合大O要求的「常数倍差距」前提。

这里要明确大O的化简规则：只有不随n变化的固定常数因子可以被丢弃，比如O(7*2^n)可以化简为O(2^n)，因为7是固定值，取C=7就能满足大O的定义；但所有随n增长的因子（比如n、log n等），都不能在化简时随意省略。

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