complexity-theory - 2^n 和 4^n 是否属于同一个 Big-Θ 复杂度类？

Question

是 2^n = Θ(4^n) 吗？

我很确定 2^n 不在 Ω(4^n) 中，因此不在 Θ(4^n) 中，但我的大学导师说它是。这让我很困惑，我无法通过谷歌找到明确的答案。

Answer 1

Answer 2

是的：看到这一点的一种方法是注意4^n = 2^(2n)。2^n与4^n（指数）相同的复杂性也是如此，因为n和2n是相同的复杂性（线性）。

总之，基础不会影响这里的复杂性；重要的是指数具有相同的复杂性。

编辑：这个答案只表明4^n和2^n具有相同的复杂性，而不是2^n大Theta 4^n：你是正确的，情况并非k如此，因为k*n^2 >= n^4对于所有n. 在某个时候，n^4会超车k*n^2。（感谢@chiwangc / @Ordous 在他们的回答/评论中强调了区别。）

Answer 3

是的。两者都具有指数复杂性。

Answer 4

是的，即使大欧米茄不满足，theta 也是可能的，但通过使用斯特林近似存在相等性。因此 (2^n)=θ(3^n)。