2 ^ n和4 ^ n在同一Big-Θ复杂度类别中吗? [英] Are 2^n and 4^n in the same Big-Θ complexity class?

问题描述

2 ^ n =Θ(4 ^ n)?

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

解决方案

2^n是否 4^n的大θ(θ)，这是因为2^n是不是 4^n的大欧米(Ω).

根据定义，当且仅当f(x) = O(g(x))和f(x) = Ω(g(x))时，我们才具有f(x) = Θ(g(x)).

要求

2^n is not Ω(4^n)

证明

假设2^n = Ω(4^n)，那么根据big-omega的定义，存在常量c > 0和n0使得:

所有n ≥ n0

的

2^n ≥ c * 4^n

通过重新排列不等式，我们得到:

所有n ≥ n0

的

(1/2)^n ≥ c

但是请注意，不等式的左侧趋向于0，而n → ∞趋于c > 0.因此，这种不平等不能满足 all n ≥ n0的所有要求，因此我们有一个矛盾！因此，我们一开始的假设一定是错误的，因此是2^n is not Ω(4^n).

更新

如 Ordous 所述，您的导师可能会引用复杂度类 EXPTIME ，在该参考框架中，2^n和4^n都属于同一类.另外请注意，我们有2^n = 4^(Θ(n))，这也可能是您的导师想要表达的意思.

Is 2^n = Θ(4^n)?

I'm pretty sure that 2^n is not in Ω(4^n) thus not in Θ(4^n), but my university tutor says it is. This confused me a lot and I couldn't find a clear answer per Google.

解决方案

2^n is NOT big-theta (Θ) of 4^n, this is because 2^n is NOT big-omega (Ω) of 4^n.

By definition, we have f(x) = Θ(g(x)) if and only if f(x) = O(g(x)) and f(x) = Ω(g(x)).

Claim

2^n is not Ω(4^n)

Proof

Suppose 2^n = Ω(4^n), then by definition of big-omega there exists constants c > 0 and n0 such that:

2^n ≥ c * 4^n for all n ≥ n0

By rearranging the inequality, we have:

(1/2)^n ≥ c for all n ≥ n0

But notice that as n → ∞, the left hand side of the inequality tends to 0, whereas the right hand side equals c > 0. Hence this inequality cannot hold for all n ≥ n0, so we have a contradiction! Therefore our assumption at the beginning must be wrong, therefore 2^n is not Ω(4^n).

Update

As mentioned by Ordous, your tutor may refer to the complexity class EXPTIME, in that frame of reference, both 2^n and 4^n are in the same class. Also note that we have 2^n = 4^(Θ(n)), which may also be what your tutor meant.

这篇关于2 ^ n和4 ^ n在同一Big-Θ复杂度类别中吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！