note[14]

话说我好像对于 OI 和 笔记 这两个分类有点模糊啊。

题：估计 \(\displaystyle\sum_{i=1}^n \frac{i}{\ln i}\) 的大小（时间复杂度估计）

解： \[ \begin{aligned} \sum_{i=1}^n \frac{i}{\ln i} & =O\left(\int_1^n \frac{x}{\ln x} \mathrm{~d} x\right) \\[6pt] & =O\left(\int_0^{\ln n} \frac{\mathrm{e}^{2 t}}{t} \mathrm{~d} t\right) && t=\ln x \\[6pt]& =O\left(\int_0^{2 \ln n} \frac{\mathrm{e}^{2 t}}{2 t} \mathrm{~d}(2 t)\right) \\[8pt]& =O(\operatorname{Ei}(2 \ln n)) && \operatorname{Ei}(x) \sim \mathrm{e}^x / x \\[8pt]& =O\left(\frac{n^2}{\ln n}\right) \end{aligned} \]

---

参考文献：

[1] https://www.cnblogs.com/CDOI-24374/p/17588706.html