GESP 八级 · GESP 202512 C++ 八级 第 9 题

下列代码的时间复杂度（以 $n$ 为自变量，忽略常数与低阶项）是（ ）。

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

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

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

【考点】嵌套循环分析｜时间复杂度估算｜求和级数渐近分析

1. 🎯 考纲定位（考点定位）

GESP 八级 C++ 算法与数据结构模块的核心考查点。八级不再满足于简单循环计数，而是要求考生能定量分析嵌套结构的总执行次数。命题人把这道题放在这里，就是要筛选掉那些只会背"双层循环就是 O(n²)"的模板化选手——他们无法处理内层循环边界随外层变量动态变化的情况。