GESP 五级 · GESP 202409 C++ 五级 第 3 题

对下面两个函数，说法错误的是（ ）。

int sumA(int n) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}

int sumB(int n) {
    if (n == 1)
        return 1;
    int res = n + sumB(n - 1);
    return res;
}

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

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

【考点】循环迭代｜递归算法｜时间复杂度分析

先看功能：两个函数都是计算1到n的累加和，D项正确。再看实现：sumA用for循环，sumB用函数自调用，A、B项描述无误。关键在C项比较效率——sumA只需n次加法，sumB每次调用都产生栈帧，递归开销远大于迭代，所以C项错误。

命题人把"效率"这个词玩得很溜。sumB代码行数少，但每次递归调用都要压栈、恢复栈，阶乘级调用栈深度让时间复杂度变成O(n)但常数项巨大。如果你只盯着代码长度就选C，掉进这个陷阱——算法效率要看实际执行时间，不是看谁写得少。

若把sumB改成求阶乘，sumA的迭代版本在n很大时反而更快，因为递归栈空间消耗远超计算本身。刷到类似题先问：命题人想考我什么？