algorithm - 我如何推理各种功能的大 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是正确的。