证明n！= O(n^n)

Question

我如何证明n！= O(n^n)？

Answer 1

我假设您想证明函数n!是集合O(n^n)的一个元素。这一点很容易被证明：

定义:一个函数f(n)是集合O(g(n))的元素，如果存在一个c>0，使得存在一个m，使得对于所有k>m，我们都有那个f(k)<=c*g(k)。

因此，我们必须将n!与n^n进行比较。让我们将它们一个接一个地写下来：

n!  = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
n^n = n *  n    *  n    *  n    * ... * n * n * n

如您所见，第一行(n!)和第二行(n^n)的右侧都恰好都有n项。如果我们比较这些项目，我们看到每个项目最多与第二行中对应的项目一样大。因此n! <= n^n (至少对n>5而言)。

所以，我们可以-看看定义-，假设存在c=1，使得存在m=5，使得对于所有k>5，我们都有k! < k^k，这证明了n!确实是O(n^n)的一个元素。