NOIP 提高 2013 第一轮 第 15 题：T(n) 表示某个算法输入规模为 n 时的运算次数。如果 T(1) 为常数，且有

题目

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

选项

• A. $\Theta(n)$
• B. $\Theta (n \log n)$
• C. $\Theta(n^2)$
• D. $\Theta(n^2 \log n)$

答案

B

题解

考点定位

本题考「递推式主定理」,对应大纲 4.1.1 复杂度（难度【3】）。

解题过程

T(n)=2T(n/2)+2n：递归树每层总工作量 2n，共 log₂n 层：

$$T(n)=\Theta(n\log n)$$

选 B。

易错提醒

① 主定理第二情形（a=2,b=2,f(n)=Θ(n)）；② 归并排序正是此递推。