作业帮 > 数学 > 作业

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

来源:学生作业帮 编辑:灵鹊做题网作业帮 分类:数学作业 时间:2024/04/25 20:32:42
为什么合并排序算法时间复杂性T(n)=2T(n/2)+O(n)就会得出T(n)=nlogn
怎么通过T(n)=2T(n/2)+O(n)得出nlogn的呢,不懂nlogn是怎么来的
为什么合并排序算法时间复杂性T(n)=2T(n/2)+O(n)就会得出T(n)=nlogn
画个图:
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的幂时的特殊情况.对于一般情况,同样可证.