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

下面 count_triple 函数的时间复杂度为（ ）。

int count_triple(int n) {
    int cnt = 0;
    for (int a = 1; a <= n; a++)
        for (int b = a; a + b <= n; b++) {
            int c = sqrt(a * a + b * b);
            if (a + b + c > n)
                break;
            if (a * a + b * b == c * c)
                cnt++;
        }
    return cnt;
}

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

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

【考点】嵌套循环｜复杂度分析｜优化剪枝

1. 考纲定位：本题落在GESP七级“算法复杂度”模块，命题人用双重循环+提前break的混合结构，卡住大量考生“只数层数不看条件”的惯性思维。

2. 解题思维：外层a从1到n，内层b从a到满足a+b≤n且a+b+√(a²+b²)≤n的区间。因为break仅在某部分触发，最坏情况内层仍可能跑满O(n)次，故总复杂度为O(n²)。正确做法是先确定循环上限，再判断break是否对整体有保证。

3. 陷阱拆解：A误把break当成全局优化，忽略了break只在部分(a,b)上生效；C/D则把循环次数想得太夸张，没看到a+b≤n的剪枝。最阴险的是"a+b+√(a²+b²)>n"这个条件，它只在部分情况下成立，不能推出O(n)。

4. 反命题思维：若把break条件改为a+b+√(a²+b²)≤n，则break永远不触发，复杂度仍为O(n²)；若去掉break，内层上限仍是a+b≤n，仍是O(n²)。刷到类似题先问"这个break是否对所有循环都有效"。