GESP 八级 · GESP 202403 C++ 八级 第 10 题

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

int fib(int n) {
    if (n <= 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

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

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

【考点】递归时间复杂度分析｜斐波那契数列递推｜黄金分割比

解析： 1. 考纲定位：GESP八级"递归与分治"模块第3题，专门卡住"把递归当成线性"的惯性思维。命题人用斐波那契这个经典指数爆炸案例，逼你分清"调用次数"和"返回值大小"。 2. 解题思维：设T(n)为fib(n)耗时。T(n)=2T(n−1)+O(1)（每次调用还有一次加法）。解特征方程r²−r−1=0，得r=(1±√5)/2，取正根φ≈1.618，故T(n)=Θ(φⁿ)。选项A的2ⁿ是上界但不够紧，C、D显然低估。 3. 陷阱拆解：错误选项A利用"两次递归调用"的直观印象，但忽略了φ<2，所以2ⁿ是宽松上界；C、D把递归当成循环或常数时间，属于"只记结论不推过程"的典型掉坑。 4. 反命题思维：若把递归改为迭代，复杂度降至O(n)；若用记忆化，T(n)=O(n)。刷到"递归+斐波那契"先问"是求值还是计数？"——本题考的是调用次数，答案必带φ。