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

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

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

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

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

【考点】递归时间复杂度｜记忆化递归｜斐波那契数列

1. 🎯 考纲定位

本题考查 GESP 七级大纲中"分治与递归"模块的核心思想：递归算法的时间复杂度分析。命题人卡住的是考生对"递归树结构"与"记忆化是否生效"这两个条件的辨析——七级普遍卡在"看到递归就套公式"，忽略代码里藏着的缓存机制。