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

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

int choose(int n, int m) {
    if (m == 0 || m == n)
        return 1;
    return choose(n - 1, m - 1) + choose(n - 1, m);
}

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

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

【考点】递归复杂度分析｜递推关系求解｜组合数增长

考纲定位：GESP 八级"递归与分治"模块，专卡"递归调用次数与组合数"的对应关系。命题人把递归写进选择题，就是看你是否能透过代码看到背后的组合爆炸，而不是死背 O(2^n) 这种暴力结论。

解题思维：先写递推式 T(n,m)=T(n−1,m−1)+T(n−1,m)+O(1)，边界 T(n,0)=T(n,n)=1。观察每层 n 减 1，总共 n 层；但第 k 层恰好有 C(k, i) 个节点，把所有层加起来就是 C(n,m)。这类"二叉递归且每步减 1"的通法：总调用次数 = 组合数 C(n,m)。

陷阱拆解：A 项 O(2^n) 是纯二叉递归的"上界"，忽略了 m 固定时大量分支提前终止；B 项 O(2^m·(n−m)) 把指数放进 m，实际指数在 n 上；D 项 O(m·(n−m)) 线性乘积，完全低估递归分支。最阴险的细节是"边界条件剪枝"，很多人只看递归式就选最大指数项。

反命题思维：把递归改成循环求 C(n,m) 的 DP 版，时间复杂度会变成 O(n·m)；空间复杂度问递归栈深度就是 O(n)。刷到递归题先问"递归式是什么？总调用次数对应什么组合数？"