Wil*_*era 4 algorithm recursion complexity-theory big-o
更新:对不起,我忘了把n ^ n放在O()里面
我的尝试是解决这种递归关系:
__PRE__
使用迭代方法我得到了n ^ n,但我不确定这是否是证明它的方法.
phi*_*mue 21
我假设你想证明函数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).