调和级数求和

调和级数求和（Harmonic Series）模型是时间复杂度分析中稍微进阶一点的考点。它通常出现在**“跳跃式”循环或者“倍数”相关**的题目中。

如果说前面的题目是“送分题”，这个模型就是**“分水岭题”**，掌握了它，你的算法分析水平就上了一个台阶。

一、 经典代码长什么样？（识别特征）

最典型的代码特征是：内层循环的步长（increment）依赖于外层循环变量i。

请看这段经典代码：

// 外层：标准的线性循环for(inti=1;i<=n;i++){// 内层：注意看步长！是 j += i，而不是 j++// 这意味着 j 每次跳跃 i 个单位for(intj=1;j<=n;j+=i){sum++;// 基本操作}}

特征识别：

1. 外层循环i从 1 到n。
2. 内层循环j每次增加i（即j遍历的是i的倍数：i,2i,3i,…i, 2i, 3i, \dotsi,2i,3i,…）。

二、 为什么叫“调和级数”？（数学推导）

我们像之前一样，把每一步内层循环执行的次数列出来：

1. 当i=1i = 1i=1时：
   j每次加 1，从 1 走到nnn。执行次数 =n/1=nn/1 = nn/1=n次。
2. 当i=2i = 2i=2时：
   j每次加 2 (2, 4, 6…)。执行次数 =n/2n/2n/2次。
3. 当i=3i = 3i=3时：
   j每次加 3 (3, 6, 9…)。执行次数 =n/3n/3n/3次。
   …
4. 当i=ki = ki=k时：
   执行次数 =n/kn/kn/k次。

总执行次数T(n)T(n)T(n)求和：
T(n)=n1+n2+n3+⋯+nnT(n) = \frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n}T(n)=1n​+2n​+3n​+⋯+nn​

我们提取公因数nnn：
T(n)=n×(1+12+13+⋯+1n)T(n) = n \times \left( 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)T(n)=n×(1+21​+31​+⋯+n1​)

重点来了：
括号里的部分1+12+13+⋯+1n1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}1+21​+31​+⋯+n1​就是数学上著名的调和级数。

数学结论告诉我们：
1+12+⋯+1n≈ln⁡n+C(C 是欧拉常数)1 + \frac{1}{2} + \dots + \frac{1}{n} \approx \ln n + C \quad (C \text{ 是欧拉常数})1+21​+⋯+n1​≈lnn+C(C是欧拉常数)
换句话说，调和级数的和，增长趋势等于log⁡n\log nlogn。

三、 最终复杂度

T(n)=n×O(log⁡n)=O(nlog⁡n)T(n) = n \times O(\log n) = O(n \log n)T(n)=n×O(logn)=O(nlogn)

结论：
如果你看到内层循环是j += i(按倍数跳跃)，那么这个两层循环的总复杂度不是O(n2)O(n^2)O(n2)，而是O(nlog⁡n)O(n \log n)O(nlogn)。

四、 哪里会用到这个知识点？（实战场景）

这个模型最著名的应用就是**“素数筛法”（埃氏筛，Sieve of Eratosthenes）**。

场景：找出nnn以内的所有素数。
算法逻辑：

1. 找到 2，把 2 的倍数（4, 6, 8…）划掉。
2. 找到 3，把 3 的倍数（6, 9, 12…）划掉。
3. …
4. 找到iii，把iii的倍数划掉。

这个“划掉倍数”的过程，代码写出来就是上面的那个循环结构。
所以，埃氏筛的时间复杂度是O(nlog⁡log⁡n)O(n \log \log n)O(nloglogn)（比nlog⁡nn \log nnlogn还要快一点点，因为外层只遍历素数，但考试中如果问通用倍数循环，答O(nlog⁡n)O(n \log n)O(nlogn)即可）。

五、 考前极速记忆卡

在你的复习表格里，可以加上这一行：

掌握了这个，关于循环嵌套的时间复杂度题目，你就基本上没有盲区了。