Notice that I am asking for little-o here (see similar question here) - for big Oh it's clearly wrong - for little-o it feels right but can't seem to prove it...
请注意，我在这里要求的是little-o(这里也有类似的问题)——对于big Oh来说，这显然是错的，因为little-o的感觉是对的，但似乎不能证明它……
EDIT: glad I raised a debate :) Assume f,g > 0 for simplicity
编辑:很高兴我提出了一个辩论:)假设f,g > 0为简单。
3 个解决方案
#1
2
It is, at least if g(n) is converging to positive infinity for n to positive infinity (if g(n) isn't there are easy to find counterexamples).
它是，至少如果g(n)收敛到正无穷(n)到正无穷(如果g(n)不是很容易找到反例)。
Sketch of a proof:
素描的证明:
Prerequsites: g(n) is converging to positive infinity for n to positive infinity.
前位:g(n)收敛到正无穷，n为正无穷。
f(n) in o(g(n)) means:
在o f(n)(g(n))的意思是:
for every eps > 0 exists a n0 so that for all n > n0 abs(f(n)) < abs(g(n)*eps).
Form this follows:
形成这个:
2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) (for n > n0).
For eps < 1:
对eps < 1:
(2^eps)^n is in o(2^n) (as 2^eps < 2)
it follows that for every eps2 > 0 exists a n1 so that for all n > n1
每个eps2 > 0都有一个n1，所以对于所有的n > n1。
(2^eps)^n < eps2*(2^n).
Choosing eps2 = eps vields:
选择eps2 = eps vields:
(2^eps)^n < eps*(2^n) for all n > n1 (n1 is dependent on eps)
Because g(n) -> pos. inf. for n -> pos. inf. there exists a n2 so that
因为g(n) -> pos，对于n -> pos，有一个n2。
g(n) > n1 for all n > n2
Following from there is
从那后
(2^eps)^g(n) < eps*2^g(n) for all n > n2.
So for every 0 < eps < 1 there exists a n3 >= max(n0,n2) so that
所以对于每一个0 < eps < 1存在一个n3 >= max(n0,n2)
2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) < eps*2^g(n) for all n > n3.
For every eps3 > 1 also:
每个eps3 > 1也:
2^abs(f(n)) < eps*2^g(n) < eps3*2^g(n)
So for every eps > 0 there exists a n3 so that
所以对于每一个eps > 0都有一个n3。
2^abs(f(n)) < eps*2^g(n) for all n > n3
Becase 2^f(n) < 2^abs(f(n)) for all n, and 2^x > 0 for all real x, it follows
因为2 ^ f(n)< 2 ^ abs(f(n))n,和2 ^ x > 0,所有真正的x,它遵循
abs(2^f(n)) < abs(eps*2^g(n)) for all n > n3
q.e.d.
q.e.d。
If something is unclear or wrong, please comment.
如果某事不清楚或错误，请评论。
EDIT: Some thoughts on other g(n):
编辑:关于其他g(n)的一些想法:
A subsequence of g(n) is restricted i.e. it exists some x so that there isn't an n0 with abs(g(n))>=x for all n > n0:
g(n)的子序列是受限制的，即它存在某个x，这样就不存在带有abs的n0 (g(n))>=x对所有的n > n0:
o(g(n)) consists only of functions that are constant 0 after some n or converge to 0. Then 2^g(n) also has a restricted subsequence, but 2^f(n) is constant 1 after some point.
o(g(n))只包含在某个n或收敛到0后的常数为0的函数。然后2 ^ g(n)也有一个限制子序列,但2 ^ f(n)为常数1后。
There is no n0 so g(n) > 0 for all n > n0:
没有n0那么g(n) > 0对于所有n > n0:
2^g(n) < 1 if g(n) < 0, so g(n) has a restricted subsequence meaning o(2^g(n)) consists only of functions that are constant 0 after some n or converge to 0.
2 ^ g(n)< 1如果g(n)< 0,所以g(n)有限制子序列含义o(2 ^ g(n))只包含函数的常数0后n或收敛于0。
#2
1
Here's an answer. The result depends on the convergence properties of g(n).
这是一个答案。结果取决于g(n)的收敛性。
First consider the related limit:
首先考虑相关的限制:
lim(x->inf) log_2 ((2^(f(n))) / (2^(g(n))))
=
lim(x->inf) ( log_2(2^(f(n))) - log_2(2^(g(n))) )
=
lim(x->inf) ( f(n) - g(n) ) = lim(x->inf) ( g(n) * f(n) / g(n) - g(n) )
=
lim(x->inf) ( -g(n) ) = - lim(x->inf) g(n)
... Now, to get this into the form of the original question in your post, IF it is mathematically correct to switch the limit and the log (which I think it is), then we would have:
…现在，为了把这个问题转化成你文章中原始问题的形式，如果它在数学上是正确的，可以改变极限和log(我认为它是)，那么我们就有:
lim(x->inf) log_2 ((2^(f(n))) / (2^(g(n))))
=
log_2 lim(x->inf) ((2^(f(n))) / (2^(g(n)))).
Now, moving on to answer the question. If it is true that
现在，继续回答这个问题。如果这是真的。
2^(f(n)) = o(2^(g(n))),
then in the limit, the right-hand side becomes
然后在极限，右边变成。
log_2 (0) = - inf
... so in this scenario it must be true that
…所以在这种情况下，肯定是这样的。
lim(x->inf) g(n) = inf
This result does seem to make sense. Consider f(x) = exp(-x) and g(x) = 1 - exp(-x). Clearly, in this example f(x) = o(g(x)). However, 2^(f(x)) is not o(2^(g(x))) because
这个结果似乎是有道理的。考虑f(x) = exp(-x)和g(x) = 1 - exp(-x)。显然，在这个例子中f(x) = o(g(x))。然而,2 ^(f(x))不是o(2 ^(g(x)))因为
lim(x->inf) (2^exp(-x)) / (2^(1-exp(-x))) = 1/2.
But given f(x) = exp(x), g(x) = exp(2x), where also f(x) = o(g(x)) and where lim(x->inf) g(x) = inf, meeting the above condition, we have
但给定f(x) = exp(x)， g(x) = exp(2x)，其中f(x) = o(g(x))，其中lim(x->inf) g(x) = inf，满足上述条件，我们有。
lim(x->inf) (2^exp(x)) / (2^exp(2x))
=
lim(x->inf) 1 / 2^(exp(x)*(exp(x) - 1)) = 0
so 2^(f(x)) = o(2^(g(x))).
所以2 ^(f(x)= o(2 ^(g(x)))。
#3
-1
Easy Proof with an example,
举个例子，
If f(n) = O(g(n)),
2^(f(n)) not equal to O(2^g(n)))
Let, f(n) = 2log n and g(n) = log n
(Assume log is to the base 2)
让f(n) = 2log n和g(n) = logn(假设log以2为底)
We know, 2log n <= c(log n) therefore f(n) = O(g(n))
我们知道，2log n <= c(log n)因此f(n) = O(g(n))
2^(f(n)) = 2^log n^2 = n^2
2^(g(n)) = 2^log n = n
2 (f(n)) = 2 2 = n 2 2 (g(n)) = 2 log n = n。
We know that
n^2 is not O(n)
Therefore, 2^(f(n)) not equal to O(2^g(n)))
我们不知道n ^ 2是O(n)因此,2 ^(f(n))不等于O(2 ^ g(n)))
#1
2
It is, at least if g(n) is converging to positive infinity for n to positive infinity (if g(n) isn't there are easy to find counterexamples).
它是，至少如果g(n)收敛到正无穷(n)到正无穷(如果g(n)不是很容易找到反例)。
Sketch of a proof:
素描的证明:
Prerequsites: g(n) is converging to positive infinity for n to positive infinity.
前位:g(n)收敛到正无穷，n为正无穷。
f(n) in o(g(n)) means:
在o f(n)(g(n))的意思是:
for every eps > 0 exists a n0 so that for all n > n0 abs(f(n)) < abs(g(n)*eps).
Form this follows:
形成这个:
2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) (for n > n0).
For eps < 1:
对eps < 1:
(2^eps)^n is in o(2^n) (as 2^eps < 2)
it follows that for every eps2 > 0 exists a n1 so that for all n > n1
每个eps2 > 0都有一个n1，所以对于所有的n > n1。
(2^eps)^n < eps2*(2^n).
Choosing eps2 = eps vields:
选择eps2 = eps vields:
(2^eps)^n < eps*(2^n) for all n > n1 (n1 is dependent on eps)
Because g(n) -> pos. inf. for n -> pos. inf. there exists a n2 so that
因为g(n) -> pos，对于n -> pos，有一个n2。
g(n) > n1 for all n > n2
Following from there is
从那后
(2^eps)^g(n) < eps*2^g(n) for all n > n2.
So for every 0 < eps < 1 there exists a n3 >= max(n0,n2) so that
所以对于每一个0 < eps < 1存在一个n3 >= max(n0,n2)
2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) < eps*2^g(n) for all n > n3.
For every eps3 > 1 also:
每个eps3 > 1也:
2^abs(f(n)) < eps*2^g(n) < eps3*2^g(n)
So for every eps > 0 there exists a n3 so that
所以对于每一个eps > 0都有一个n3。
2^abs(f(n)) < eps*2^g(n) for all n > n3
Becase 2^f(n) < 2^abs(f(n)) for all n, and 2^x > 0 for all real x, it follows
因为2 ^ f(n)< 2 ^ abs(f(n))n,和2 ^ x > 0,所有真正的x,它遵循
abs(2^f(n)) < abs(eps*2^g(n)) for all n > n3
q.e.d.
q.e.d。
If something is unclear or wrong, please comment.
如果某事不清楚或错误，请评论。
EDIT: Some thoughts on other g(n):
编辑:关于其他g(n)的一些想法:
A subsequence of g(n) is restricted i.e. it exists some x so that there isn't an n0 with abs(g(n))>=x for all n > n0:
g(n)的子序列是受限制的，即它存在某个x，这样就不存在带有abs的n0 (g(n))>=x对所有的n > n0:
o(g(n)) consists only of functions that are constant 0 after some n or converge to 0. Then 2^g(n) also has a restricted subsequence, but 2^f(n) is constant 1 after some point.
o(g(n))只包含在某个n或收敛到0后的常数为0的函数。然后2 ^ g(n)也有一个限制子序列,但2 ^ f(n)为常数1后。
There is no n0 so g(n) > 0 for all n > n0:
没有n0那么g(n) > 0对于所有n > n0:
2^g(n) < 1 if g(n) < 0, so g(n) has a restricted subsequence meaning o(2^g(n)) consists only of functions that are constant 0 after some n or converge to 0.
2 ^ g(n)< 1如果g(n)< 0,所以g(n)有限制子序列含义o(2 ^ g(n))只包含函数的常数0后n或收敛于0。
#2
1
Here's an answer. The result depends on the convergence properties of g(n).
这是一个答案。结果取决于g(n)的收敛性。
First consider the related limit:
首先考虑相关的限制:
lim(x->inf) log_2 ((2^(f(n))) / (2^(g(n))))
=
lim(x->inf) ( log_2(2^(f(n))) - log_2(2^(g(n))) )
=
lim(x->inf) ( f(n) - g(n) ) = lim(x->inf) ( g(n) * f(n) / g(n) - g(n) )
=
lim(x->inf) ( -g(n) ) = - lim(x->inf) g(n)
... Now, to get this into the form of the original question in your post, IF it is mathematically correct to switch the limit and the log (which I think it is), then we would have:
…现在，为了把这个问题转化成你文章中原始问题的形式，如果它在数学上是正确的，可以改变极限和log(我认为它是)，那么我们就有:
lim(x->inf) log_2 ((2^(f(n))) / (2^(g(n))))
=
log_2 lim(x->inf) ((2^(f(n))) / (2^(g(n)))).
Now, moving on to answer the question. If it is true that
现在，继续回答这个问题。如果这是真的。
2^(f(n)) = o(2^(g(n))),
then in the limit, the right-hand side becomes
然后在极限，右边变成。
log_2 (0) = - inf
... so in this scenario it must be true that
…所以在这种情况下，肯定是这样的。
lim(x->inf) g(n) = inf
This result does seem to make sense. Consider f(x) = exp(-x) and g(x) = 1 - exp(-x). Clearly, in this example f(x) = o(g(x)). However, 2^(f(x)) is not o(2^(g(x))) because
这个结果似乎是有道理的。考虑f(x) = exp(-x)和g(x) = 1 - exp(-x)。显然，在这个例子中f(x) = o(g(x))。然而,2 ^(f(x))不是o(2 ^(g(x)))因为
lim(x->inf) (2^exp(-x)) / (2^(1-exp(-x))) = 1/2.
But given f(x) = exp(x), g(x) = exp(2x), where also f(x) = o(g(x)) and where lim(x->inf) g(x) = inf, meeting the above condition, we have
但给定f(x) = exp(x)， g(x) = exp(2x)，其中f(x) = o(g(x))，其中lim(x->inf) g(x) = inf，满足上述条件，我们有。
lim(x->inf) (2^exp(x)) / (2^exp(2x))
=
lim(x->inf) 1 / 2^(exp(x)*(exp(x) - 1)) = 0
so 2^(f(x)) = o(2^(g(x))).
所以2 ^(f(x)= o(2 ^(g(x)))。
#3
-1
Easy Proof with an example,
举个例子，
If f(n) = O(g(n)),
2^(f(n)) not equal to O(2^g(n)))
Let, f(n) = 2log n and g(n) = log n
(Assume log is to the base 2)
让f(n) = 2log n和g(n) = logn(假设log以2为底)
We know, 2log n <= c(log n) therefore f(n) = O(g(n))
我们知道，2log n <= c(log n)因此f(n) = O(g(n))
2^(f(n)) = 2^log n^2 = n^2
2^(g(n)) = 2^log n = n
2 (f(n)) = 2 2 = n 2 2 (g(n)) = 2 log n = n。
We know that
n^2 is not O(n)
Therefore, 2^(f(n)) not equal to O(2^g(n)))
我们不知道n ^ 2是O(n)因此,2 ^(f(n))不等于O(2 ^ g(n)))