证明n! = O(n^n)

发布于 2024-10-17 04:44:33 字数 26 浏览 2 评论 0原文

我怎样才能证明n! = O(n^n)?

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

你的呼吸 2024-10-24 04:44:33

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

定义：如果存在 c> ，则函数 f(n) 是集合 O(g(n)) 的元素。 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< /code> 右侧的项目。如果我们比较这些项目，我们会发现每个项目最多与第二行中对应的项目一样大。因此n！ <= n^n。

因此，我们可以 - 查看定义 - 说，存在 c=1 使得存在 m=5 使得对于所有 k>5< /code> 我们有 k！ < k^k，证明n!确实是O(n^n)的元素。

I assume that you want to prove that the function n! is an element of the set O(n^n). This can be proven quite easily:

Definition: A function f(n) is element of the set O(g(n)) if there exists a c>0 such that there exists a m such that for all k>m we have that f(k)<=c*g(k).

So, we have to compare n! against n^n. Let's write them one under another:

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

As you can see, the first line (n!) and the second line (n^n) have both exactly n items on the right side. If we compare these items, we see that every item is at most as large as it's corresponding item in the second line. Thus n! <= n^n.

So, we can - look at the definition - say, that there exists c=1 such that there exists m=5 such that for all k>5 we have that k! < k^k, which proves that n! is indeed an element of O(n^n).

回复收藏 0 原文

~没有更多了~