令 $H_n$ 为第 n 项调和数
$$ H_n=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\sum_{i=1}^{n}\frac{1}{i} $$证明 $H_n$ 是 $O(\log n)$ 的
证明 如下图所示:
$\sum_{i=1}^{n}\frac{1}{i}$可以看作图中蓝色阴影的面积; 而橙色部分的面积则可以看作函数 $y=\frac{1}{x}$ 的积分 $\int_{0}^{n}\frac{1}{x}\mathrm{d}x$. 因此有
$$
\sum_{i=2}^{n}\frac{1}{i}\lt \int_{0}^{n}\frac{1}{x}\mathrm{d}x=\ln n
$$
$$
\sum_{i=1}^{n}\frac{1}{i}\lt \ln n + 1 = O(\log n)
$$
证毕.
PREVIOUS在Jekyll中使用LaTeX
NEXT在Lua中使用装饰器