讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。

这个过程中会解释清楚在各种时间复杂度中经常看到的一个记号——“lgn”(以2为底的对数函数)是如何产生的。

递归式

代码分析

对归并排序代码进行逐行分析,当有n > 1个元素时,分解运行时间如下:

分解:第1行是判断,第2行是分解步骤(仅仅计算中间位置),都只需要常量时间,因此D1(n) = Θ(1),D2(n) = Θ(1)。

解决:原问题分解成了2个子问题,每个子问题的规模是原问题的1/2。为了求解一个规模为n/2的子问题,第3行和第4行,各需要T(n/2)的时间,所以一共需要2T(n/2)的时间来求解2个子问题。

合并:在合并算法中已经知道在一个具有n个元素的数组上进行两个子数组MERGE需要Θ(n)的时间,即第5行C(n) = Θ(n)。

将每行的执行时间相加:

T(n) = 2T(n/2) + D1(n) + D2(n) + C(n) (当n > 1)

T(n)的表达式中又包含了T,所以上式称为T(n)的递归式。

根据分析进行简化可得到:

T(n) = 2T(n/2) + Θ(n) (当n > 1)

求解递归式

求解递归式,即得到描述T(n)与输入规模n关系的函数表达式的过程。为方便起见,假设n刚好是2的幂(子数组总可以被2整除直到只有1个元素为止)。该假设不影响递归式解的增长量级。

重写递归式为:T(n) = 2T(n/2) + cn (当n > 1),然后手绘出“递归”层层展开的样子——递归树:

  • 图(a)为T(n),是未进行递归时的表达;
  • 图(b)为扩展成一棵描绘递归式的等价树,cn是树根(代表递归的顶层算法中的代价),根的两棵子树是两个较小的递归式T(n/2);
  • 图(c)是继续扩展T(n/2)后的样子。

构造递归树

如此层层递归扩展,得到一颗完整的递归树如下:

完整递归树

将递归式完全扩展后,形成了完整的递归树,一共是lgn+1层(如果n是8,则树有lg8+1=4层),每层的代价是cn,那么总代价cnlgn+cn,忽略低阶项和常量c,即有T(n) = Θ(nlgn)。

关于Θ(nlgn)

现在知道时间复杂度中的lgn是如何产生的了:是基于递归的原因。

lgn即log2n,是以2为底的对数函数,比任何线性函数增长要慢,所以在足够大的输入情况下,在最坏情况下,运行时间为Θ(nlgn)的归并排序将优于运行时间为 Θ(n2)的插入排序。

y=x与y=lgx

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2017-09-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏糊一笑

非比较排序算法总结与实现

之前一篇文章介绍了几种常用的比较排序算法,下面介绍的是几种非比较排序算法。 非比较排序算法内部引用的都是计数排序,当然你也可以将计数排序换为其他的比较排序算法。...

3128
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之为用于高考名次排序的排序算法

  在高考结束以后,所有人都在等着成绩,政府部门面对几百万的数据,你知道他们是怎么算名次的么?上一次学到递归排序以及快排,确实,用他们可以实现,可是他们的时间复...

501
来自专栏TensorFlow从0到N

讨厌算法的程序员 7 - 归并排序的时间复杂度分析

? 递归树 上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度...

2496
来自专栏Java开发者杂谈

重读算法导论之算法基础

重读算法导论之算法基础 ---- 插入排序 ​ 对于少量数据的一种有效算法。原理: 整个过程中将数组中的元素分为两部分,已排序部分A和未排序部分B 插入过程中,...

3899
来自专栏玄魂工作室

面试题解:输入一个数A,找到大于A的一个最小数B,且B中不存在连续相当的两个数字

昨天发的算法有一处情况没考虑到,比如加一后有进位,导致又出现重复数字的情况,修正后今天重新发一次。

1091
来自专栏小樱的经验随笔

Codeforces Round #410 (Div. 2)(A,字符串,水坑,B,暴力枚举,C,思维题,D,区间贪心)

A. Mike and palindrome time limit per test:2 seconds memory limit per test:256 m...

4114
来自专栏Web项目聚集地

面试前你必须知道的三个排序算法

今天分享的是三种排序算法,在面试、实际编程中经常会碰到和使用到的,我会带领大家从分析排序算法技巧上以及代码实现上全面理解这一知识点的掌握。

992
来自专栏小詹同学

Leetcode打卡 | No.008 字符串转整数

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

963
来自专栏LEo的网络日志

关于算法复杂度

3558
来自专栏机器学习和数学

[编程经验]Python生成器、迭代器与yield语句小结

今天要分享的内容是Python的生成器、迭代器与yield语句。主要包括什么是生成器,如何定义一个生成器,如何调用生成器包含的元素。迭代器也是一样的,最后介绍y...

3046

扫码关注云+社区