NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 6 题

若某算法的计算时间表示为递推关系式：

• $T(N) = 2T(\dfrac{N}{2}) + N \log N$
• $T(1) = 1$

则该算法的时间复杂度为（ ）。

a=2,b=2→基准n；f(n)多log因子，主定理情形二推广得log平方

别惯性选O(N log N)；f(n)比n^(log_b a)多log^k n时，结果多log^{k+1} n

考点：主定理（情形二推广）

解析

基准 n^(log_b a)=n，f(n)=n log n 多一个 log 因子，属情形二推广，结果再乘 log n。