我怎样才能证明 n! = O(n^n)?
最佳答案
我假设您想证明函数 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 .
所以，我们可以 - 查看定义 - 假设存在 c=1这样就存在 m=5这样对于所有k>5我们有k! < k^k , 这证明 n!确实是 O(n^n) 的一个元素.
关于algorithm - 证明 n! = O(n^n)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4999448/