3

请注意，我在这里要求 little-o（请参阅此处的类似问题）-对于 big-o，这显然是错误的-对于 little-o，感觉正确但似乎无法证明...

编辑：很高兴我提出了辩论:) 为简单起见假设 f,g > 0

4

3 回答 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 回答