调和级数为什么是 O(log n) 的
Jacky0909
·
·
个人记录
调和级数
调和级数（Harmonic series）定义为：
H(n)=\sum_{i=1}^n \frac{1}{i}
## 正片
首先我们把 $\frac{1}{n}$ 拆成积分形式：
$$
\frac{1}{n}=\int_n^{n+1}\frac{1}{\lfloor x \rfloor}dx
$$
于是：
$$
\begin{aligned}
H(n)&=\sum_{i=1}^n\frac{1}{i}\\
&=\sum_{i=1}^n\int_n^{n+1}\frac{1}{\lfloor x \rfloor}dx
\end{aligned}
$$
上下界是 $i,i+1$，显然可以合并：
$$
H(n)=\int_1^{n+1}\frac{1}{\lfloor x \rfloor}dx
$$
拆一下：
$$
\begin{aligned}
H(n)&=\int_1^{n+1}(\frac{1}{x}+\frac{1}{\lfloor x \rfloor}-\frac{1}{x})dx\\
&=\int_1^{n+1}\frac{1}{x}dx+\int_1^{n+1}(\frac{1}{\lfloor x \rfloor}-\frac{1}{x})dx
\end{aligned}
$$
左边是众所周知的积分，右边是一个魔法。
右边有一个神秘结论（收敛）：
$$
\gamma=\lim_{n \to \infty}\int_1^n(\frac{1}{\lfloor x \rfloor}-\frac{1}{x})dx=0.577\cdots
$$
于是：
$$
\begin{aligned}
H(n)&\approx\ln(n+1)+\gamma\\
&=O(\log n)
\end{aligned}
$$