我如何推理各种功能的大 O？

Question

考虑以下函数：

f(n)   = 2^n
g(n)   = n!
h(n)   = n^logn

以下关于 f(n)、g(n) 和 h(n) 的渐近行为的陈述中，哪些是正确的？

(A) f(n) = O(g(n)); g(n) = O(h(n))
(B) f(n) = \Omega(g(n)); g(n) = O(h(n))
(C) g(n) = O(f(n)); h(n) = O(f(n))
(D) h(n) = O(f(n)); g(n) = \Omega(f(n))

我已经知道了

According to order of growth: h(n) < f(n) < g(n)

(g(n) is asymptotically greater than f(n) and f(n) is asymptotically greater than h(n) )

通过获取给定 3 个函数的日志，我们可以很容易地看到上面的顺序

lognlogn < n < log(n!)  (logs of the given f(n), g(n) and h(n)).

注意 log(n!) = \theta(nlogn)

但是如何找出正确的选项呢？

Answer 1

从微积分很容易看出，如果

lim {n -> inf} a(n) / b(n) < inf

然后

a(n) = O(b(n))

还要注意这里所有的函数都是无穷大的，所以我们可以用L'Hôpital's rule.

最后，请注意，Stirling's Approximation 渐近地给出

lim {n -> inf} n! / (sqrt(2 pi n) (n / e)^n) = 1

如果将这三件事结合起来，您会发现：

lim {n -> inf} 2^n / n! = lim {n -> inf} 2^n / (sqrt(2 pi n) (n / e)^n) = 0

和

lim {n -> inf} n^{log(n)} / 2^n = < inf

所以D是正确的。