GESP 四级 · GESP 202603 C++ 四级 第 25 题

下面用递推方式计算斐波那契数列第 $n$ 项的程序，时间复杂度是 $O(2^n)$。

int fib(int n) {
    if (n <= 1) return n;
    int f0 = 0, f1 = 1, cur = 0;
    for (int i = 2; i <= n; i++) {
        cur = f0 + f1;
        f0 = f1;
        f1 = cur;
    }
    return cur;
}

答案B。指针和数组的代码追踪：画出变量和指针的内存示意图，追踪每次赋值后值的变化。

指针和数组追踪时画内存布局图可以大大简化理解。

【考点】循环控制结构｜时间复杂度分析｜递归与迭代区别

🎯 考纲定位：GESP 四级 C++ 考查循环控制结构、时间复杂度分析。命题人用"递推方式"迷惑考生，想测试是否真正理解算法复杂度而非背诵结论，尤其要区分递推与递归的复杂度差异是四级必考点。

🧠 解题思维：看到循环 for (int i = 2; i <= n; i++)，迭代次数就是 n-1 次。循环体内执行 cur = f0 + f1; f0 = f1; f1 = cur; 三条语句，每条都是 O(1)。总时间 = O(n)。递归版每次调用产生两个子调用，导致 O(2^n)；迭代版复用变量，复杂度降为 O(n)。

🪤 陷阱拆解：选项 A 正确是典型"只看名字不看实现"的陷阱。很多学生背过"斐波那契是指数级"的结论，但本题是线性递推，并非递归版。命题人故意写"递推方式"来误导。另外，若学生误以为递归版 O(2^n) 是标准，就会掉坑。

🔄 反命题思维：若把循环改成递归，时间复杂度会指数级增长。所以原题是考学生区分递归与迭代。答案：B