GESP 五级 · GESP 202509 C++ 五级 第 18 题

下面递归实现的斐波那契数列的时间复杂度为 $O(2^n)$。

long long fib_memo(int n, long long memo[]) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

int main() {
    int n = 40;
    long long memo[100];
    fill_n(memo, 100, -1);
    long long result2 = fib_memo(n, memo);
    return 0;
}

斐波那契数列：f(1)=f(2)=1，f(n)=f(n-1)+f(n-2)。递归实现简单但效率低（O(2^n)），循环实现O(n)。

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

【考点】记忆化递归｜大 O 表示法｜递归树剪枝

1. 🎯 考纲定位

GESP 五级"递归与记忆化"模块第 3 题，命题人专卡"见到递归就默认指数级"的惯性思维，用 memo 数组把递归树剪成线性链，迫使考生识别 O(n) 而非 O(2^n)。