用斯特林近似证明

Question

你如何使用斯特林近似来证明？

           log(n!)=Θ(nlogn)

有什么想法吗？

Answer 1

我会给你证明的大致轮廓。您必须填写详细信息。根据 this wikipedia article，斯特林的近似表明对于所有正整数 n:

使用一点代数重新排列项，我们得到

所以 n! 的上界和下界是函数

因为我们对 log(n!) 感兴趣，所以我们需要确定 log(f(n)) 的行为n 的值。做更多的代数：

对于较大的 n 值，第一项比其余项大得多，因此

这就完成了证明的大纲。