CSP-S 提高级 · CSP 2023 提高级第一轮 第 15 题

现在用如下代码来计算 $x^n$，其时间复杂度为（）。

double quick_power(double x, unsigned n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    return quick_power(x, n / 2)
        * quick_power(x, n / 2)
        * ((n & 1) ? x : 1);
}

这题考递归时间复杂度，别被 n/2 骗了，关键看递归调用次数，递推式 T(n)=2T(n/2)+O(1) 直接定胜负。

最容易踩的坑就是看到 n/2 就下意识选 O(log n)，那是只调用一次递归的情况。这题特意把 quick_power(x, n/2) 写了两次，每次规模减半但调用翻倍，导致总计算量线性增长。还有学生容易把递归树每层的总规模算成 n 然后乘以层数 log n 得出 O(n log n)，其实每层节点数翻倍，每层总耗时也是翻倍，累加下来是等比数列求和，主导项就是 O(n)。

这道题考查递归函数的时间复杂度分析，属于算法基础中非常典型的陷阱题。命题人故意写了一个看似‘快速幂’的代码，但把递归调用重复了一次，看学生能不能透过现象看本质，不被 n/2 的表象迷惑。

先说概念：时间复杂度看的是基本操作次数随输入规模 n 的增长趋势。对于递归，核心就是看递推关系——每次调用会产生多少个子问题，子问题的规模是多少。这题的代码是：

return quick_power(x, n / 2)
    * quick_power(x, n / 2)
    * ((n & 1) ? x : 1);

注意看，这里调用了两次 quick_power(x, n/2)。每次调用规模都减半，但调用次数是 2 次。这就是解题的突破口。

命题人挖坑的思路很清晰：快速幂的标准写法是算一次 t = quick_power(x, n/2)，然后返回 t*t*...，这样递推式是 T(n) = T(n/2) + O(1)，解出来是 O(log n)。但这题把 t 算了两次，递推式就变成了 T(n) = 2T(n/2) + O(1)。很多学生看到 n/2 就条件反射选 C，完全忽略了前面的系数 2。这就是典型的‘形似神不似’。

思考心法：拿到这种递归题，第一步别急着套公式，先画递推式。这题的递推关系非常明确：

T(n) = 2T(n/2) + O(1)

为什么是 2T(n/2)？因为函数体里有两处 quick_power(x, n/2)，每处都产生一个规模为 n/2 的子问题，所以系数是 2。常数项 O(1) 来自最后的乘法运算。

现在用主定理（Master Theorem）秒杀：a=2, b=2, f(n)=O(1)。比较 log_b a = log_2 2 = 1，发现 f(n) = O(n^{1-ε})（这里 ε 可以取 0.5）。属于主定理第一种情况，解是 T(n) = Θ(n^{log_b a}) = Θ(n^1) = O(n)。

为了保险，我们再用递归树验证一下。根节点规模 n，耗时 O(1)。下一层两个节点，每个规模 n/2，总耗时 2×O(1)=O(2)。再下一层四个节点，总耗时 4×O(1)=O(4)。可见每层总耗时是上一层的两倍，形成等比数列：O(1) + O(2) + O(4) + ... + O(2^{log n})。等比数列求和公式告诉我们，总和等于最后一项乘以 (2-1)/(2-1)，也就是 O(2^{log n}) = O(n)。递归树每层节点数翻倍，每层总耗时也翻倍，累加下来主导项就是 O(n)，而不是 O(n log n)。

避坑重点：学生最容易错选 D（O(n log n)），这是把递归树每层总耗时当成 O(n) 然后乘以层数 log n 得到的。实际上每层总耗时是 O(2^k)，是指数增长的，求和时后面的项占主导，结果就是 O(n)。另一种错误是选 C（O(log n)），这是没注意到系数 2，误以为只调用了一次递归。

考频与趋势：快速幂在题库中一共考过 8 题，覆盖 2009 到 2026 年，近年热度明显上升。2023 年就考了 2 题，2025 年 1 题，2026 年更是考了 2 题，说明命题人很青睐这种‘形似快速幂但细节不同’的变体。递归函数作为基础考点，历年考频极高，2024 年单年就到 25 题，2025 年 15 题，2026 年 18 题，可见递归相关题目在 CSP 提高级和 GESP 八级中持续高频出现。

基于数据预测：未来几年，这类‘看似快速幂实则线性递归’的题目大概率还会出现，命题人可能会继续用重复调用、多余乘法等细节来制造陷阱。同时，递归树分析、主定理应用这类考点在算法基础部分会保持高频，因为它们是后续学习动态规划、分治算法的基石。

总结：这题答案就是 A（O(n)）。解题关键就是抓住递推式中的系数 2，别被 n/2 骗了。写代码时，如果真要用快速幂，记得只算一次递归，把重复调用去掉，才能降到 O(log n)。