为什么合并排序算法时间复杂性T(n)=2T(n/2)+O(n)就会得出T(n)=nlogn

为什么合并排序算法时间复杂性T(n)=2T(n/2)+O(n)就会得出T(n)=nlogn
怎么通过T(n)=2T(n/2)+O(n)得出nlogn的呢,不懂nlogn是怎么来的
慢的4cen 1年前 已收到1个回答 举报

jufan 幼苗

共回答了26个问题采纳率:88.5% 举报

画个图:
n
/
n/2 n/2
/ /
n/4 n/4 n/4 n/4
/ / / /
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
树高logn,每层加起来都是n,一共是logn×n
上面是n为2的幂时的特殊情况.对于一般情况,同样可证.

1年前

7
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 2.603 s. - webmaster@yulucn.com