GESP 七级 · GESP 202409 C++ 七级 第 14 题

下面 fib 函数的时间复杂度为（ ）。

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

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

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

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

1. 🎯 考纲定位

GESP 七级"递归基础"模块。命题人放这道题，就是卡住那些"只会看表面"的考生——看到递归就条件反射 $O(2^n)$，却完全忽略状态缓存这个关键优化。