问题描述
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-Θ复杂度类别中吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!