math - 证明 lg(n!) = O(n!)

Question

出于某种原因，我很难想出一个证明这一点的好方法。一般来说，我对解决极限和数学非常生疏。

首先：我的印象是您可以根据乘法定律分离限制。所以，目前我刚刚开始

lim _n→∞ ( lg(n)⋅n ^0.5 ) ⋅ lim _n→∞ ( (e/n) ⁿ )

等于某物的极限乘以极限0。所以，它一定是0。

这是否有效，还是我应该回去学习推导 n ^0.5 ⋅lg(n) 和其他类似的复合函数？

显然这个问题是微不足道的，我只是想知道我是否采取了有效的方法。

Answer 1

这很容易证明。请记住，f(z) = O(z)如果存在 M 和 z0，那么对于所有z > z0: |f(z)| < M|z|。

现在，由于我们|log(z)| < |z|对所有人都微不足道z > 1，因此我们只需替换z = n!，这就是我们的证明。要清楚，z0 = 1并且M = 1会这样做。

如果有人说这不是真的，他们可能忘记了最常见的 Big Oh 符号（Capital omicron）提供了一个上限，因此该界限不必很紧。

更新：关于限制乘法定律的注释。如果两个限制都存在，您只能打破这样的限制。例如，如果当 n 接近无穷大时有 n/n 的极限，则不能将其分离为 n 乘以 1/n 的极限，因为 n 的极限不存在。您的第一个限制明显不同，因此您不能使用这种方法。