2^n与4^n的Big O比较。

Question

我正在尝试理解这两个大O符号。显然，2^n的大O是O(2^n)，但我不确定是否可以简化4^n。如果可以，我会将4^n = (2^2)^n。然后我们可以展开成2^(2n)，我会将其简化为O(2^n)，因为n前面的常数并不重要。

这样正确吗？谢谢。

- follmer

---

不，这是不正确的：不存在常数C使得对于所有足够大的n都有4^n <= C 2^n。 - Mark Dickinson

Answer 1

让我们自己尝试理解这个问题。假设4^n = O(2^n)，则存在某个m和某个c，使得对于所有n >= m，都有4^n <= c*2^n。因此，对于所有n >= m，我们有：

   (2*2)^n <= c*2^n
=> 2^n * 2^n <= c*2^n
=> c >= 2^n

所以c显然不能是恒定的，这是一个矛盾。

- Niklas B.

---

很好。比仅引用维基百科更好 :) - user3235832

这是一个非常有指导意义的好评论（同意，比只说它们不是相同顺序的引用要好得多）。它运用了指数的乘法法则：a^n * b^n = (a * b)^n 和反证法。 - Turing

Answer 2

以下是从维基百科关于大 O 表示法的解释中翻译而来：

然而，具有不同底数的指数函数并不属于相同的阶。例如， 2^n 和 3^n 不属于相同的阶。

- Buddy