求证log n! = n log n - O(n)：如何推导O(n)项？

1. 展开阶乘的对数 #

首先，阶乘的对数可直接展开为求和形式：
log(n!) = log1 + log2 + log3 + ... + logn

2. 用积分做上下界估计 #

函数f(x)=logx是单调递增函数，因此求和式log(n!)可通过定积分做上下界近似：

• 下界：求和式大于等于从1到n的logx积分：∫₁ⁿ logx dx ≤ log(n!)
• 上界：求和式小于等于从1到n+1的logx积分：log(n!) ≤ ∫₁ⁿ⁺¹ logx dx

3. 计算积分值 #

通过分部积分法计算∫logx dx，结果为：
∫logx dx = xlogx - x + C

计算下界积分：

∫₁ⁿ logx dx = [xlogx - x]₁ⁿ = nlogn - n - (1·log1 - 1) = nlogn - n + 1

这说明log(n!) ≥ nlogn - n + 1

计算上界积分：

∫₁ⁿ⁺¹ logx dx = [(n+1)log(n+1) - (n+1)] - (1·log1 -1) = (n+1)log(n+1) - n

将(n+1)log(n+1)展开为(n+1)(logn + log(1+1/n))，利用log(1+1/n) ≤ 1/n（n≥1时成立），可推导出：

(n+1)log(n+1) -n = nlogn + nlog(1+1/n) + log(n+1) -n ≤ nlogn + 1 + log(n+1) -n

其中1 + log(n+1)是O(logn)量级，属于O(n)范畴，因此上界可简化为log(n!) ≤ nlogn -n + O(logn)

4. 合并结论 #

结合上下界结果：
nlogn -n +1 ≤ log(n!) ≤ nlogn -n + O(logn)
由于O(logn)包含在O(n)中，因此可写成：
log(n!) = nlogn - O(n)

补充：斯特林公式验证 #

斯特林公式给出阶乘的近似表达式：
n! ≈ √(2πn) · (n/e)^n
对两边取对数：

log(n!) ≈ (1/2)log(2πn) + nlogn -n

其中(1/2)log(2πn)是O(logn)量级，同样属于O(n)，因此也能得到log(n!) = nlogn - O(n)的结论

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