NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 15 题

$T(n)$ 表示某个算法输入规模为 $n$ 时的运算次数。如果 $T(1)$ 为常数，且有递归式 $T(n) = 2\times T(\dfrac{n}{2}) + 2n$，那么 $T(n) =$ （ ）。

拿到这题别急着套公式，先识别出这是典型的分治递归结构：a=2,b=2，合并代价是线性的2n。用Master定理一眼定阶数，再简单展开几层验证一下，就能排除干扰项。

最容易栽跟头的就是觉得前面那个系数2会改变复杂度阶数，或者把2n当成O(1)忽略掉。记住常数因子和线性系数在Θ记号里都不影响阶数，真正决定的是log_b a和k的大小关系。还有人会死算递归树，把每一层的2n加起来算成n^2，其实只要注意到层数是log n，总和就是n log n。

考点定位

这道题考的是分治算法的时间复杂度分析，核心工具就是Master定理。在NOIP初赛里，这类题目年年都有，命题人特别喜欢把a、b、k凑成临界值（log_b a = k），然后看学生能不能准确判断是Θ(n^k)还是Θ(n^k log n)。2013年这道题就是典型的临界案例。

概念拆解

先说清楚Master定理的适用场景：解决形如 T(n) = a·T(n/b) + f(n) 的递归式。其中a是子问题个数，b是规模缩减倍数，f(n)是除递归外的合并代价。定理把f(n)写成O(n^k)，然后比较log_b a和k的大小：

• 若log_b a > k，主项占优，结果是Θ(n^{log_b a})；
• 若log_b a = k，两项同阶，结果多出一个对数因子，变成Θ(n^k log n)；
• 若log_b a < k，合并代价占优，结果是Θ(n^k)。