note[19]

题：问 \[ \mathcal{O}(\log (n!)) \] 解： \[ \begin{aligned} \mathcal{O}(\log (n!)) &= \mathcal{O}\left(\int_1^n \log x \, \mathrm{d} x\right) \\[8pt] &= \mathcal{O}\left( {(x-1)\log x\Big|_1^n} \right) \\[8pt] &= \mathcal{O}(n \log n) \end{aligned} \]

---

这里用到了 \(\int \log x \, \mathrm{d}x\) 的公式 \[ \int \log x \, \mathrm{d}x = (x - 1) \log x + C \] 证明：

考虑分部积分法 \[ \int u \, \mathrm{d} v = uv - \int v \, \mathrm{d} u \] 其中 \(u = \log x,~ \mathrm{d}u = \frac{1}{x}\mathrm{d}x,~v = x,~ \mathrm{d} v = 1\) ，则 \[ \begin{aligned} \int \log x \, \mathrm{d}x &= x\log x - \int 1\, \mathrm{d} x \\[6pt] &= (x - 1) \log x + C \end{aligned} \] 证毕。