第12题下述斐波那契数列计算的时间复杂度是（）。

第 238 题 / 共 301 题

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

🎉

回答正确！

你真棒！

📝 题目解析

【考纲知识点】递归算法的时间复杂度分析

【正确答案】D

【题目解析】

该递归函数在计算fibonacci(n)时会调用自身两次（fibonacci(n-1)和fibonacci(n-2)），形成一棵二叉树结构。

每个节点的时间开销为O(1)，递归树的总节点数近似为2ⁿ（实际为 Θ(φⁿ)，其中ϕ是黄金比例≈1.618，但通常简化为指数级O(2ⁿ)）。

因此，正确答案为D。