1

请注意:在这个问题中,日志 (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

但这似乎是不可能的,所以我试图以传统方式解决它,但被卡住了。

4

1 回答 1

2

从前提上来说,对于所有人来说c = 2,都有一个N0 > 0这样的。通过单调性this 相当于for all 。f(n) >= 2 log(n)n > N0y = 2^x2^f(n) >= n^2n > N0

对于任何人来说,都d > 0存在N1 > 0这样的情况,因为二次的增长速度比任何线性的都要快。n^2 >= n/dn > N1n^2n/d

结合这两个不等式,n/d <= n^2 <= 2^f(n)对于所有n > max(N0, N1).

于 2020-11-06T01:14:26.210 回答