GESP 七级 · GESP 202403 C++ 七级 第 13 题

下面 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++)
            for (int c = b; a + b + c <= n; c++)
                if (a * a + b * b == c * c)
                    cnt++;
    return cnt;
}

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

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

【考点】循环复杂度 | 嵌套循环 | Big-O 表示法

🎯 考纲定位：GESP七级算法模块典型题，绝大多数考生只关注变量范围，忽略循环嵌套的乘积效应，本题考查循环嵌套的迭代次数乘积规律，命题人用三层循环强制检验Big-O推导能力而非代码执行经验。

🧠 解题思维：外层a遍历n次，中层b从a到n-a，迭代次数为n-a，中层总迭代次数为∑(n-a) = O(n²)；内层c从b到n-a-b，迭代次数为n-a-b，内层总迭代次数为∑∑(n-a-b) = O(n³)。条件判断为常数时间，总复杂度O(n³)。

🪤 陷阱拆解：A项误判为单层循环；B项忽略内层循环；D项把中层误算成O(n²)或内层误判为O(n²)；若将循环条件改为a+b+c<=n，则内层循环次数仍为O(n)。关键在于三层循环均为O(n)量级，相乘得O(n³)。若只背结论不理解本质，就会掉进这个陷阱。

🔄 反命题思维：把中层改为b=1到n则降为O(n²)，把内层改为c=1到n则升为O(n⁴)。若将判断改为遍历所有三元组，则复杂度升为O(n⁴)。刷到类似题时，先问自己"命题人想考我什么"。