GESP 四级 · GESP 202412 C++ 四级 第 12 题

给定如下代码，其时间复杂度为（ ）。

int cellRecur(int n) {
    if (n == 1)
        return 1;
    return cellRecur(n - 1) + cellRecur(n - 1) + 1;
}

答案B。综合分析各选项，运用相关知识推导。

仔细审题，注意"不正确""不属于""不是"等否定词。用排除法缩小范围。

【考点】递归复杂度分析｜递推关系建模｜指数增长陷阱

命题人考的是四级必考点：递归调用树的规模估算。这道题之所以卡住大多数考生，是因为他们习惯只看递归深度（n层），却忽略了每层产生的分支数——这是区分O(n)与O(2^n)的核心分水岭。

解题通法：把递归式写成T(n) = 2·T(n-1) + O(1)，展开得T(n) = 2·(2·T(n-2) + O(1)) + O(1) = 4·T(n-2) + O(2) … 归纳可得T(n) = 2^{n-1}·T(1) + O(2^{n-1})，即Θ(2^n)。记住：每次调用产生k个子调用，深度为d，总节点数约为k^d，时间复杂度为O(k^d)。

陷阱拆解：A项O(n^2)是误把深度和分支数相乘得到的假象；C项O(1)完全无视递归；D项O(n)只盯着深度，忽略了每层两路分叉。命题人最爱在递归题里埋"分支因子"这个隐形条件——不提醒的话，绝大多数人都会按线性递归去算。

反命题思维：如果把函数改成cellRecur(n-1) + cellRecur(n-2) + 1，会变成斐波那契式递归，复杂度降为O(1.618^n)；若加一层循环则升为O(n·2^n)。刷到类似题时，先问自己"这层递归到底产生几个子任务"，这才是破题关键。