若某算法的计算时间表示为递推关系式:T(N)=2T(N/2)+NlogN T(1)=1则该算法的时间复杂度为

Question

NOIP2017提高组初赛试题第6题……
若某算法的计算时间表示为递推关系式：T(N)=2T(N/2)+NlogN T(1)=1
则该算法的时间复杂度为( )。
A.O(N) B.O(NlogN)
C.O(N log²N) D.O(N²)
答案是C 跪求各位大牛详解！

Answer 1

利用分叉树来做，根结点nlogn，每次下分两个子树，结点为n/2logn/2，一直做到最后，发现最后的log里面的真数为1，也就是0。对每一层加和，第一层nlogn，第二层nlogn/2也就是nlogn-nlog2，以此类推，nlogn-nlog4，nlogn-nlog8，....,nlogn-nlogn。树高以2为底logn，乘进去为nlogn*logn - n/2*logn -n/2*(logn)^2,就是O（n（logn）^2）。（手机百度回答不会插入图片，我是这么做的，有错误还请指出）

Answer 2

参考以上最新的主定理，这个题是可以用最新的主定理来解答，非常便捷。