专栏首页人工智能LeadAI讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

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

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

这个过程中会解释清楚在各种时间复杂度中经常看到的一个记号——“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),作者:黑猿大叔

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BAT机器学习面试1000题系列(第150~279题)

    长文~可先收藏再看哟~ 150、在感知机中(Perceptron)的任务顺序是什么?深度学习 DL基础 易 1 随机初始化感知机的权重 2 去到数据集的下一批(...

    用户1332428
  • 使用RNN预测股票价格系列二

    在前文教程中,我们想继续有关股票价格预测的主题,并赋予在系列1中建立的具有对多个股票做出响应能力的RNN。 为了区分不同价格序列之间相关的模式,我们使用股票信号...

    用户1332428
  • Word2Vec教程-Skip-Gram模型

    原文:Word2Vec Tutorial - The Skip-Gram Model(http://mccormickml.com/2016/04/19/wor...

    用户1332428
  • 超全递归技巧整理,这次一起拿下递归

    大家好,我是多选参数的程序锅,一个正在 neng 操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇将主要介绍递归相关的内容,下面是本篇的内容提纲。

    syy
  • 算法导论第四章分治策略剖根问底(二)

       在上一篇中,通过一个求连续子数组的最大和的例子讲解,想必我们已经大概了然了分治策略和递归式的含义,可能会比较模糊,知道但不能用语言清晰地描述出来。但没关系...

    CloudDeveloper
  • 《算法图解》NOTE 3 递归1.定义2递归结构2.适用场合3.应用案例

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

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

    袁承兴
  • 读书笔记:《算法图解》第三章 递归

    孙亖
  • 什么是递归?

    一上来你肯定觉得读这句话好绕,好吃力。 其实你用递归来读就很简单了: 递归要有一个终点(小鲤鱼) 当递归尚未达到终点的时候,函数会反复调用自己。 ...

    阿珏
  • Python之路_递归

    py3study

扫码关注云+社区

领取腾讯云代金券