我正在尝试理解这两个大O符号。显然,2^n的大O是O(2^n),但我不确定是否可以简化4^n。如果可以,我会将4^n = (2^2)^n。然后我们可以展开成2^(2n),我会将其简化为O(2^n),因为n前面的常数并不重要。这样正确吗?谢谢。
让我们自己尝试理解这个问题。假设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显然不能是恒定的,这是一个矛盾。
4^n <= C 2^n
。 - Mark Dickinson