在同一个Big-Θ复杂度类中是2 ^ n还是4 ^ n？

Question

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

我很确定2 ^ n不在Ω(4 ^ n)中,因此不在Θ(4 ^ n)中,但我的大学导师说它是.这让我很困惑,我找不到每个Google的明确答案.

Answer 1

2^n是不是大的2θ(Θ) 4^n,这是因为2^n是不是大的omega(Ω) 4^n.

根据定义,我们f(x) = ?(g(x))只有if f(x) = O(g(x))和f(x) = ?(g(x)).

要求

2^n is not ?(4^n)

证明

假设2^n = ?(4^n),然后根据big-omega的定义存在常量c > 0,n0并且:

2^n ? c * 4^n 对全部 n ? n0

通过重新安排不平等,我们有:

(1/2)^n ? c 对全部 n ? n0

但请注意,n ? ?不平等的左侧倾向于0,而右侧等于c > 0.因此,这种不平等不能适用于所有人 n ? n0,所以我们有一个矛盾!因此,我们在开始时的假设必定是错误的2^n is not ?(4^n).

更新

正如提到Ordous,你的导师可能指的是复杂类EXPTIME,在参考该帧,都2^n和4^n在同一个班级.另请注意,我们有2^n = 4^(?(n)),也可能是您的导师的意思.