GESP 八级 · GESP 202606 C++ 八级 第 11 题

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

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

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】嵌套循环复杂度｜平方根边界分析｜大 O 渐进记号

1. 考纲定位 本题考查 GESP 八级算法分析核心：嵌套循环复杂度计算。命题人卡住的是考生对非标准循环边界的敏感度——很多人看到√n 就慌，误以为要解方程，其实只需数迭代次数。

2. 解题思维 思维链：先看外循环 i 从 1 到 n，执行 n 次；再看内循环 j 满足 j*j <= n，即 j <= √n，执行约 √n 次。总运算量 = n × √n = n^(3/2)。因此选 C。通法：嵌套循环复杂度 = 外循环次数 × 内循环平均次数，注意内循环边界是平方根而非线性。

3. 陷阱拆解 A 项 O(n) 是初学者典型误区，只盯着外循环 i 到 n 就以为整体是 n 次，完全忽略内循环 j 也要跑一次；B 项 O(n log n) 偷换概念，把√n 当成 log n 混为一谈；D 项 O(n²) 最阴险——它利用考生对循环边界的视觉惯性，把 j*j <= n 看成 j <= n，仿佛两个循环都是 n 次，这是命题人专门测试你是否真的读懂了条件语句。记住：j <= √n 不是常数，是随 n 增长的函数，任何试图把它"化简"成 O(1) 或 O(n) 的直觉都是错的。

4. 反命题思维 如果内循环改成 j <= n，答案立刻变 D；改成 j <= log n 变 B；改成 j <= n / i 变 A。命题人真正想考的不是计算能力，而是你对循环边界的敏感度——看到 j*j <= n 时，第一反应要是"√n 次"，而不是"n 次"或"常数"。刷到这类题，先问自己：内循环的终止条件是什么？它和 n 的函数关系是什么？