GESP 五级 · GESP 202412 C++ 五级 第 4 题

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

int fibA(int n) {
    if (n <= 1) return n;
    int f1 = 0, f2 = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = f2;
        f2 = f1 + f2;
        f1 = temp;
    }
    return f2;
}

int fibB(int n) {
    if (n <= 1) return n;
    return fibB(n - 1) + fibB(n - 2);
}

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

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

【考点】递归与递推｜时间复杂度分析｜Fibonacci 序列

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

• 本题考查 GESP 五级「算法基础」模块中的递归、递推实现对比，以及时间复杂度的阶数判断
• 命题人卡住的是考生对「递归效率」的直观误判——大量考生凭感觉认为递归也是线性或平方级，其实裸递归 Fibonacci 是指数爆炸