私がここでlittle-oを求めていることに注意してください（ここで同様の質問を参照してください）-大きなOhの場合は明らかに間違っています-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。inf。n->posの場合。inf。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）のサブシーケンスは制限されています。つまり、すべてのn> n0に対してabs（g（n））> = xのn0が存在しないように、いくつかのxが存在します。
o（g（n））は、あるnの後で定数0であるか、0に収束する関数のみで構成されます。2^ g（n）にも制限されたサブシーケンスがありますが、2 ^ f（n）はある時点の後で定数1です。
n0がないため、すべてのn> n0に対してg（n）> 0：
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)、どこでも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
そう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 に答える