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}$$

证毕。