调和级数

概述

调和级数是自然数倒数的求和 $H_{n} = \sum_{i = 1}^{n} 1/ i$ ，其增长速率为 $Θ (ln n)$ ，在算法分析中广泛出现。

定义

调和级数

$H_{n} = \sum_{i = 1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$

渐近展开： $H_{n} = ln n + γ + O (1/ n)$ ，其中 $γ \approx 0.5772156649$ 为欧拉-马斯刻若尼常数（Euler-Mascheroni constant）。
$H_{n} = Θ (ln n)$ ，增长极其缓慢，但发散（当 $n \to \infty$ 时趋于无穷）。
积分界： $ln (n + 1) \leq H_{n} \leq 1 + ln n$ ，可通过积分比较法证明。
调和级数常见于算法分析：如快速排序中划分不均匀时的平均比较次数分析。