如何不使用斯特林公式证明lg n! = Θ(n lg n)？

当然可以！不用斯特林公式的话，我们完全可以通过对n!的上下界进行放缩，结合对数的基本性质来推导，核心思路就是分别证明上界（O(n lg n)）和下界（Ω(n lg n)），两者结合就能得到Θ的结果了。

第一步：证明lg n! = O(n lg n) #

这一步非常直观：

• 首先，n! 是从1到n的所有整数乘积，即 n! = 1×2×3×…×n。显然每个因子都不会超过n，所以我们可以直接把每个因子替换成n，得到放缩式：n! ≤ n×n×…×n = nⁿ。
• 两边同时取以2为底的对数（其实用任何底数的对数都可以，因为不同底数的对数之间只差一个常数倍数，不影响Θ的判定），就有：lg n! ≤ lg(nⁿ) = n lg n。
• 根据大O的定义，这就说明lg n! 是O(n lg n)——我们找到了常数C=1和n₀=1，当n≥n₀时，lg n! ≤ C·n lg n恒成立。

第二步：证明lg n! = Ω(n lg n) #

这一步需要点小技巧，核心是把n!拆成前后两部分，用后半部分的因子来构造下界：

• 把n!拆成前半段和后半段的乘积：n! = (1×2×…×⌊n/2⌋) × (⌊n/2⌋+1 × … ×n)。
• 观察后半段的每个因子：当n≥2时，后半段里的每个数都大于等于n/2（比如n是偶数时，后半段从n/2+1到n，都比n/2大；n是奇数时，后半段从(n+1)/2到n，同样都大于n/2）。
• 后半段一共有多少项呢？至少有⌈n/2⌉项（比如n=5时后半段有3项，n=4时后半段有2项，都等于⌈n/2⌉）。
• 所以我们可以把后半段的每个因子都替换成n/2，得到下界：n! ≥ (n/2)^⌈n/2⌉。
• 进一步放缩，因为⌈n/2⌉ ≥ n/2，所以(n/2)^⌈n/2⌉ ≥ (n/2)^(n/2)。
• 两边取对数：lg n! ≥ lg[(n/2)^(n/2)] = (n/2)(lg n - lg 2) = (n/2)lg n - n/2。
• 现在要说明这个式子是Ω(n lg n)：当n足够大时（比如n≥4，此时lg n≥2），(n/2)lg n - n/2 = (n/2)(lg n - 1)，而lg n -1 ≥ lg n / 2（因为lg n≥2时，lg n -1 ≥ 1 ≥ lg n/2），所以(n/2)(lg n -1) ≥ (n/2)(lg n /2) = n lg n /4。
• 这就满足了大Ω的定义：存在常数C=1/4和n₀=4，当n≥n₀时，lg n! ≥ C·n lg n恒成立。

总结 #

既然lg n! 既是O(n lg n)又是Ω(n lg n)，根据Θ符号的定义，我们就可以得出结论：lg n! = Θ(n lg n)。

这种方法完全依赖基本的不等式和对数运算性质，不需要斯特林公式的近似，逻辑非常严谨扎实。

内容的提问来源于stack exchange，提问作者Dan