我在 Kormen 的书“Algorithms. Construction and analysis”中做任务。86页e小段这样的题我有一点看不懂：
在 o(o small) 的情况下，在 A=lg(n!) 和 B=lg(n^n) 的答案中写着-不。虽然我的回答是肯定的。我正在使用书中的公式来证明 lg(n!)=o(lg(n^n))：
0 <= lg(n!) < c * lg(n^n)。
因为 lg(n!) <= lg(n^n) 对于 n > 1。然后对于任何 c：lg(n!) <= c * lg(n^n)。事实证明 lg(n!)=o(lg(n^n))。但是我查看了不同来源的答案，它说事实并非如此。请解释我错了什么。
有这样一个斯特林公式：
我认为，从哪里开始，一切都会立即变得显而易见 :)
如果我们考虑对数n! 和n n，则该比值的极限为 1。
lg(n!) = ∑ 1≤i≤n lg(i) ≥ （只保留和的高半部分）
≥ ∑ n/2≤i≤n lg(i) ≥ （元素的较低估计）
≥ ∑ n/2≤i≤n lg(n/2) = (折总和)
= (n/2)lg(n/2) = （与总和nlg(n)分开）
= (n/2)(lg(n) - lg(2)) = (n/2)(lg(n)(1 - lg(2)/lg(n))) = ((1 - lg(2 )/lg(n))/2) n lg(n) ≥
（我们引入常量C = (1 - lg(2)/lg(n 0 ))/2）
≥ C n lg(n)
从任何n 0 > 2开始，最后一个不等式为真。
lg(n!) ≤ lg(n n )（阶乘的对数增长不比阶数的对数增长快）这一事实您已经知道。上面证明了反向估计——次数的对数增长不比阶乘的对数增长得快。
正确答案是θ。