algorithm - 正式证明 n^n 是 Ω(n!)

Question

使用正式定义：f(n)= Ω(g(n)) 当且仅当存在一个常数 'C' 使得 f(n)>= cg(n) 其中 C>0 且 n 接近无穷大。当非正式地展示这一点时，我能够通过图表看到该陈述是正确的。但是，我不确定如何正式展示这一点。任何帮助，将不胜感激

标签： algorithmtime-complexitybig-o

Answer 1

如果你想要一个正式的证明，你可以通过归纳证明 n^n > n! 对于任何 n>1。

基本情况是 2^2 > 2！（因为 4 > 2）。归纳步骤是 n! = n（n-1）！< n(n-1)^(n-1) < n*n^(n-1) = n^n。