某分治算法把规模为 n 的问题分成 2 个规模为 n/2 的子问题，分解与合并的总工作量为 Θ(n)。其递归式为 T(n)=2T(n/2)+n，则时间复杂度为（）。
递归树每层共有的子问题工作量为 n，问题规模每次减半，树高约为 log₂n，因此总代价为 n×log n，再加叶子层仍为同阶，得到 Θ(n log n)。
选项分析
错误。log n 只计算了递归层数，没有乘每层总工作量 n。
错误。单层是 n，但算法还有约 log n 层。
错误。各层总量没有按 n、2n、4n 增长到平方级。
正确。约log n层，每层总工作量Θ(n)，因此为Θ(n log n)。
本题为什么容易错
最常见的两个错法是只看“规模减半”选 log n，或只看“有两个子问题”选 n²。复杂度要同时看分支数、子问题规模和每层额外工作。
简短答案
递归式 T(n)=2T(n/2)+n 的时间复杂度是多少，正确答案是 D（Θ(n log n)）。递归树每层共有的子问题工作量为 n，问题规模每次减半，树高约为 log₂n，因此总代价为 n×log n，再加叶子层仍为同阶，得到 Θ(n log n)。
易混淆概念对比表
| 概念 | 本题判断 | 区别要点 | 记忆提示 |
|---|---|---|---|
| Θ(log n) | 本题干扰项 | 错误。log n 只计算了递归层数，没有乘每层总工作量 n。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| Θ(n) | 本题干扰项 | 错误。单层是 n，但算法还有约 log n 层。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| Θ(n²) | 本题干扰项 | 错误。各层总量没有按 n、2n、4n 增长到平方级。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| Θ(n log n) | 本题正确答案 | 正确。约log n层，每层总工作量Θ(n)，因此为Θ(n log n)。 | 看到题干核心场景时优先联想到它 |
本题易混淆选项怎么区分
- Θ(log n)：错误。log n 只计算了递归层数，没有乘每层总工作量 n。
- Θ(n)：错误。单层是 n，但算法还有约 log n 层。
- Θ(n²)：错误。各层总量没有按 n、2n、4n 增长到平方级。
知识点详解
主定理适用于形如 T(n)=aT(n/b)+f(n) 的常见分治递归。这里 a=2、b=2，所以 n^(log_b a)=n；f(n)=n 与其同阶，结果多一个对数因子。递归树也能直观看到：第 i 层有 2^i 个规模 n/2^i 的子问题，该层非递归工作总和为 n，层数为 Θ(log n)。边界条件 T(1)=Θ(1) 不改变最终阶。
备考速记
两半递归，每层合计 n，共 log n 层，所以 n log n。
Master Theorem 在时间复杂度场景中的作用
Master Theorem在本题中的核心价值，是解决“某分治算法把规模为 n 的问题分成 2 个规模为 n/2 的子问题，分解与合并的总工作量为 Θ(n)。其递归式为 T(n)=2T(n/2)+n，则时间复杂度为（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。
同类题怎么考
- 给出分治描述，先写递归式再求复杂度。
- 比较二分查找、归并排序和二叉递归的复杂度。
Master Theorem 在软件设计师软考中的考法
软考选择题通常不会只考概念定义，还会把Master Theorem放到时间复杂度场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。
解题思路
这题不必死背公式。第一层合并工作是 n；下一层两个子问题，每个做 n/2，总和还是 n；再下一层四个 n/4，加起来仍是 n。规模从 n 不断减半到 1，大约有 log₂n 层，所以是每层 n 乘层数 log n。归并排序就是这类递归式的典型例子。
考点定位
看到 a=2、b=2、f(n)=n 时，n^(log_b a)=n，与 f(n) 同阶，对应 Θ(n log n)。不熟主定理也能画递归树。
易错提醒
- 把 2T(n/2) 错当成每层工作量翻倍。
- 漏掉递归树叶子数量和层数。
- 未说明 n 不是 2 的幂时只影响常数和取整，不改变渐进阶。
备考提示
- 不会主定理时，固定写前三层的节点数、单节点代价和层总代价。
- 对比 T(n)=T(n/2)+1、2T(n/2)+1 和 2T(n/2)+n。
你可能还想了解
- 为什么递归树每一层的工作量都是 n？
- 主定理中的 a、b、f(n) 分别表示什么？
- T(n)=2T(n/2)+1 的复杂度是多少？
本文小结
T(n)=2T(n/2)+n的递归树约有log n层，每层非递归工作总量都是n，因此时间复杂度为Θ(n log n)。