SCP 模拟 · SCP 2021 第一轮（初赛）模拟 第 10 题

假设某算法的计算时间表示为递推关系式 $T(n)=3T(\dfrac{n}{2})+\Theta(n)$，$T(1)=\Theta(1)$，则算法的时间复杂度为

这题就是主定理（Master Theorem）的送分题。拿到递推式 T(n)=aT(n/b)+f(n) 后，别急着套公式，先算那个关键指数 log_b a，再跟 f(n) 的幂次 n^d 做个大小比较，答案立马就出来了。

学生最容易在两个地方翻车：一是把递推式里的系数看错，以为 a=1 或者 b=3，导致算出的 log_b a 完全不对；二是把 f(n) 的阶搞混，把 Θ(n) 当成 Θ(n log n) 或者 Θ(n^2)，结果比较时方向反了，最后选成 n log n 甚至 n^2 的选项。还有就是把主定理的三个情况记混，尤其是当 f(n) 恰好等于 n^{log_b a} 时，很多人会下意识选 n^{log_b a} log n，其实那是情况二里 f(n) 多一个 log 因子才有的结果，纯匹配时应该直接就是 Θ(n^{log_b a})。

这道题考查的是递归算法时间复杂度的经典工具——主定理（Master Theorem）。很多同学在看到递推式 T(n) = aT(n/b) + f(n) 时，第一反应是去画递归树或者展开几层，但对于这种标准形式，主定理才是命题人最想让你用的“武器”。

先把题目里的参数拎出来：a = 3，b = 2，f(n) = Θ(n)。主定理的核心就是比较两个量：一个是递归带来的“分治代价”所对应的指数 log_b a，另一个是 f(n) 本身的增长阶数 n^d（这里 d = 1）。算一下 log_2 3，大约是 1.585，显然比 1 大。

根据主定理的情况一：当 log_b a > d 时，递归树中每一层的代价都在变大，最终整个算法的复杂度由最底层的叶子节点主导，即 Θ(n^{log_b a})。本题正好符合这一条，所以答案就是 Θ(n^{log_2 3})，也就是选项 B。

这里有个常见的坑：很多同学看到 f(n) = n，就会想当然地认为复杂度是 Θ(n log n)，那是情况二（log_b a = d）才有的结果，而且情况二要求 f(n) 还要带一个 log 因子。或者有人会把 log_2 3 算成 1.5 甚至 2，导致误选 C 或 D。记住，只要 log_b a 严格大于 d，不管 f(n) 是不是 n，结果都是 Θ(n^{log_b a})。

从命题视角看，这种题通常不会让你真的去推导递归树，而是考察你对主定理三个情况的熟练程度和参数提取能力。如果题目改成 T(n) = 2T(n/2) + n，那 log_2 2 = 1，刚好等于 d，答案就会变成 Θ(n log n)；如果改成 T(n) = 4T(n/2) + n^2，那 log_2 4 = 2，等于 d，但 f(n) 没有额外的 log 因子，依然是 Θ(n^2)。所以关键是别被 f(n) 的形式带偏，老老实实比较指数。

避坑指南：做题前先把 a、b、d 三个数圈出来，算出 log_b a 和 d 的大小关系，这一步做对了，后面几乎不用动脑子。另外，大 O 表示法里常数和低阶项都可以忽略，但主定理里的指数差一点都不能错，哪怕 log_2 3 和 1.5 只差 0.085，选错就是选错。

根据我手头的历年真题数据，主定理在 CSP-J/S 和 GESP 中属于高频考点，近五年至少出现过 7 次，其中 2021 年这次是单选题，难度适中，主要用来区分对递推式理解不深的同学。从趋势上看，命题人很喜欢在简单递推式里藏参数陷阱，比如把 a 和 b 的位置颠倒，或者把 f(n) 写成 n log n 来诱导情况二。未来如果继续考，大概率还是这种送分题，但可能会稍微增加一点干扰项，比如选项里混入 Θ(n^{log_2 3} log n) 这种看起来很像但实际上不对的答案，专门卡那些记混情况二的同学。

所以，这道题的正确答案就是 B：Θ(n^{log_2 3})。