证明 n! = O(n^n)

Question

7

How can I prove that n! = O(n^n)?

- Wilbert Barrera

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phimuemue · Accepted Answer

我假设您想证明函数n!是集合O(n^n)的元素。这可以很容易地证明：

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

因此，我们需要比较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。

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