GESP 七级 · GESP202609 C++ 七级 第 14 题

下列代码片段的时间复杂度为（　　）。

long long s = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j += i)
s += i + j;

A. B. C. D.

看到双重循环且内层步长随外层变量变化，立刻想到"内层循环次数 = n / i"。总复杂度就是所有 i 对应的内层次数之和，即 n·(1/1+1/2+…+1/n)。这类题的通法是：先写出内层循环的迭代次数表达式，再对 i 求和，最后用级数知识判断阶。

选项 A 把内层当成 O(1) 误判为 O(n)；C 误以为内层固定 n 次导致 O(n²)；D 混淆了调和级数与对数级数。最阴险的是"j += i"——很多人会下意识认为内层循环次数就是 n，忽略步长变化。

1. 考纲定位

本题考查 GESP 七级"算法复杂度分析"模块，命题人专门卡住"内层步长与外层变量相关"的嵌套循环，这是七级高频考点，也是区分六、七级的关键。

2. 解题思维

外层 i 从 1 到 n，内层 j 从 1 开始每次加 i。内层循环次数 = n / i（向下取整）。总迭代次数 = Σ_{i=1}^{n} (n / i) = n·(1/1 + 1/2 + … + 1/n)。调和级数 H_n = 1 + 1/2 + … + 1/n 的渐近值是 ln n + γ，所以总次数 ≈ n·ln n，即 O(n log n)。