证明N！ =为O（n ^ N） [英] prove that n! = O(n^n)

问题描述

更新：对不起，我忘了把ñ^ N将O内（）

Update: Sorry I forgot to put n^n inside the O()

我的尝试是解决这个递推关系：

My attempt was to solve this recurrence relation:

T(n) = nT(n-1) +1
T(0) = 1;

使用我得到了迭代法第n的n次方，但林不知道这是否是要证明它的方式。

Using the iteration method I got the n^n but Im not sure if this is the way to prove it.

推荐答案

我假设你想证明函数 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:

定义：函数 F（N）是一组元素 O（G（N））如果存在一个 C＆GT; 0 这样存在一个 M ，使得对所有的 K＆GT;米我们有一个 F（K）＆LT; = C *克（K）

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).

所以，我们要比较 N！对ñ^ N 。让我们把它们写之一的另一个问题：

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

正如你可以看到，第一行（ N！）和第二行（ñ^ N ）有右侧两个完全 N 项目。如果我们比较这些产品，我们看到，每一个项目是至多一样大，因为它是在第二行相应的项目。因此， N！ ＆LT; = N ^ N （至少对N> 5）。

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 (at least for n>5).

因此​​，我们可以 - 看一下定义 - 也就是说，这存在 C = 1 等，存在着 M = 5 ，使得对所有的 K＆GT; 5 我们有一个 K！ ＆LT; K ^氏/ code>，这证明了 N！确实的元素为O（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).

这篇关于证明N！ =为O（n ^ N）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！