GESP 七级 · GESP 202506 C++ 七级 第 12 题

下面程序的时间复杂度为（ ）。

int rec_fib[MAX_N];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] == 0)
        rec_fib[n] = fib(n - 1) + fib(n - 2);
    return rec_fib[n];
}

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

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

【考点】递归｜记忆化｜时间复杂度

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

GESP 七级递归模块第 2 单元，记忆化优化是七级区分八级的分水岭。命题人把这道题放进来，就是卡住那些只会背"斐波那契递归=指数级"结论、不会看代码实际行为的考生——他们把数学公式的复杂度当成程序复杂度，这是七级最典型的思维断层。