NOIP 提高 2017 第一轮 第 6 题：则该算法的时间复杂度为（ ）

题目

若某算法的计算时间表示为递推关系式：
- $T(N) = 2T(\dfrac{N}{2}) + N \log N$
- $T(1) = 1$
则该算法的时间复杂度为（   ）。

选项

• A. $O(N)$
• B. $O(N \log N)$
• C. $O(N \log^2 N)$
• D. $O(N^2)$

答案

C

题解

考点定位

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

解题过程

T(N)=2T(N/2)+N log N：每层工作量 2^k·(N/2^k)log(N/2^k) = N·log(N/2^k)，逐层求和 = N(log N + (log N −1)+…+1) = Θ(N log²N)。

选 C。

易错提醒

① 主定理第三情形扩展：f(n)=n log n 高于 n^{log_b a}=n ⇒ +f(n) 累加对数层；② 结果 N log²N（log 的平方）。