请注意:在该问题中,日志(n)以2为底。
我知道f(n)=omega(log(n))
-换句话说,每个 c>0: f(n)>=c*log(n)
(从特定位置开始)
我想证明n=o(2^{f(n)})
-换言之,针对每一个 d>0: n<=d*2^{f(n)}
(从特定位置开始)
我如何证明这一点?
我做了什么?
我尝试使用可以在这里找到的限制:https : //math.stackexchange.com/questions/3895906/prove-that-the-following-limit-is-0
但似乎不可能,因此我试图以传统方式解决该问题,但遇到了麻烦。
从前提出发,所有人都有这样c = 2
一个前提。单调性就等于所有人。N0 > 0
f(n) >= 2 log(n)
n > N0
y = 2^x
2^f(n) >= n^2
n > N0
对于任何d > 0
存在N1 > 0
使得n^2 >= n/d
所有n > N1
由于二次n^2
增长高于任何线性更快n/d
。
结合两个不等式,n/d <= n^2 <= 2^f(n)
对所有n > max(N0, N1)
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句