看《数据结构与算法分析》有不懂的地方

《数据结构与算法分析》马克艾伦维斯 C语言描述第二版 第24页
前提:若N=2的k次，则T(N)=N*(k+1)。那为什么T(N)=NlogN+N=O(NlogN)？

T(n)=2T(n/2)+n
    =2(2T(n/2*2)+n)+n
    =2(2(2T(n/2*2*2)+n)+n)+n
    =2^3T(n/2^3)+3n
    =...
    =2^kT(n/2^k)+kn            现在设 n=2^k
    =nT(1)+kn
    =n(T(1)+k)            T(1)是常数，可以忽略
    =kn
    =nlogn

因为i T(N)=N*(k+1)。
而N=2的k次方，那么k就等于logN，所以T(N) = N*(logN+1) = NlogN + N
对于时间复杂度来说，只考虑多项式的最高阶，因此 T(N)=NlogN+N=O(NlogN)

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632