请注意，我在这里要求 little-o（请参阅此处的类似问题）-对于 big-o，这显然是错误的-对于 little-o，感觉正确但似乎无法证明...
编辑：很高兴我提出了辩论:) 为简单起见假设 f,g > 0
问问题
14486 次
3 回答
2
至少如果 g(n) 收敛到正无穷大，则 n 收敛到正无穷大（如果 g(n) 不容易找到反例）。
证明草图：
先决条件：g(n) 收敛到正无穷大，n 收敛到正无穷大。
o(g(n)) 中的 f(n) 表示：
for every eps > 0 exists a n0 so that for all n > n0 abs(f(n)) < abs(g(n)*eps).
形成如下：
2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) (for n > n0).
对于 eps < 1：
(2^eps)^n is in o(2^n) (as 2^eps < 2)
因此，对于每个 eps2 > 0 存在一个 n1，因此对于所有 n > n1
(2^eps)^n < eps2*(2^n).
选择 eps2 = eps 场：
(2^eps)^n < eps*(2^n) for all n > n1 (n1 is dependent on eps)
因为 g(n) -> pos。信息。对于 n -> 位置。信息。存在一个 n2 使得
g(n) > n1 for all n > n2
从那里开始
(2^eps)^g(n) < eps*2^g(n) for all n > n2.
所以对于每一个 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.
对于每个 eps3 > 1 也：
2^abs(f(n)) < eps*2^g(n) < eps3*2^g(n)
所以对于每个 eps > 0 存在一个 n3 使得
2^abs(f(n)) < eps*2^g(n) for all n > n3
因为对于所有 n，2^f(n) < 2^abs(f(n))，对于所有实数 x，2^x > 0，它遵循
abs(2^f(n)) < abs(eps*2^g(n)) for all n > n3
qed
如果有什么不清楚或错误的地方，请发表评论。
编辑：对其他 g(n) 的一些想法：
g(n) 的子序列受到限制，即它存在一些 x，因此对于所有 n > n0，不存在带有 abs(g(n))>=x 的 n0：
o(g(n)) 仅由在某个 n 之后为常数 0 或收敛到 0 的函数组成。然后 2^g(n) 也有一个受限子序列，但 2^f(n) 在某个点之后是常数 1。
没有 n0 所以 g(n) > 0 对于所有 n > n0：
如果 g(n) < 0，则 2^g(n) < 1，因此 g(n) 具有受限子序列，这意味着 o(2^g(n)) 仅包含在某个 n 之后为常数 0 或收敛到 0 的函数.
于 2012-03-30T10:31:31.990 回答
1
这是一个答案。结果取决于 g(n) 的收敛特性。
首先考虑相关限制：
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)
...现在，要将其转换为您帖子中原始问题的形式，如果切换限制和日志（我认为是）在数学上是正确的，那么我们将拥有：
lim(x->inf) log_2 ((2^(f(n))) / (2^(g(n))))
=
log_2 lim(x->inf) ((2^(f(n))) / (2^(g(n)))).
现在，继续回答这个问题。如果这是真的
2^(f(n)) = o(2^(g(n))),
然后在极限，右手边变成
log_2 (0) = - inf
...所以在这种情况下，它必须是真的
lim(x->inf) g(n) = inf
这个结果似乎是有道理的。考虑f(x) = exp(-x) and g(x) = 1 - exp(-x)。显然，在这个例子f(x) = o(g(x))中。然而，2^(f(x)) is not o(2^(g(x)))由于
lim(x->inf) (2^exp(-x)) / (2^(1-exp(-x))) = 1/2.
但是给定f(x) = exp(x), g(x) = exp(2x)wheref(x) = o(g(x))和 where 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
所以2^(f(x)) = o(2^(g(x)))。
于 2012-03-30T10:36:56.760 回答
-1
简单证明，举个例子，
如果 f(n) = O(g(n)),
2^(f(n)) 不等于 O(2^g(n)))
让 f(n) = 2log n 和 g(n) = log n
（假设 log 以 2 为底）
我们知道，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
我们知道
n^2 不是 O(n)
因此，2^(f(n)) 不等于 O(2^g(n)))
于 2017-02-28T05:51:27.783 回答