讨厌算法的程序员 | 第三章 算法分析基础

时间资源

上一篇,我们知道了如何用循环不变式来证明 算法的正确性,本篇来看另一个重要方面:算法分析。分析算法的目的,是预测算法所需要的资源。资源不仅是指内存、CPU等硬件资源,人们更关注的是计算时间(时间资源)。

到这里可能会产生一个疑问,计算时间与硬件资源强相关,不同的硬件配置下计算时间就不同。那么如何来衡量算法的效率呢?

答案是必须有一个稳定的硬件模型。在此基础上,才能屏蔽掉硬件配置不同导致的算法运行时间的差异,从而单单显露出算法本身的优劣。

算法分析的环境模型

《算法导论》中,明确的定义了该模型:通用的单处理器/RAM计算模型(RAM,随机访问)。这是大多数讲算法的书里没有提到的重要前提。

模型指标:

  • 单处理器;
  • RAM;
  • 基于真实计算机中常见的指令:算术指令(加法、减法、乘法、除法、取余、向下取整、向上取整),数据移动指令,控制指令;
  • 指令一条一条的执行,无并发执行;
  • 假设每条指令所需时间都为常量,2k指数操作也看成一个常量时间操作(k是一个足够小的正整数);
  • 不关心数据的精度,假设每个数据字有最大长度限制;
  • 不区分内存层次——高速缓存和虚拟内存。

所有算法的运行,都基于上述环境模型,比较的基础就有了。

算法分析基础

算法分析的两个重要概念就是输入规模和运行时间。

输入规模

拿 插入排序 举例,排序1000个数肯定比排序10个数需要更长的时间。这里的1000和10就是不同的输入规模。

输入规模的度量,对于不同的问题其度量的单位是不同的。对于插入排序来说,其度量是数组中数的个数n。对于某个算法的输入是一个图(Graph)的,则输入规模可以用该图中的顶点数n1和边数n2——两个量来描述。每个具体问题,我们都要指出所使用的输入规模度量。

运行时间

运行时间的度量,并非我们所用的时、分、秒。前面的环境模型中,我们假设了每条指令所需时间都是常量,这里我们再更进一步,执行第i行代码的每次执行需要时间为ci,无论该行代码循环多少次,每次都一样。那么程序运行的总时间就是,每行代码执行时间ci之和。

算法需要的时间与输入的规模同步增长,所以通常把一个程序的运行时间描述成其输入规模的函数。

插入排序算法的分析

有了“输入规模”和“运行时间”两个基本概念,我们仍以插入排序为例,对其伪码进行分析。具体做法就是:计算每行代码执行时间ci之和,得出输入规模与运行时间的关系。

以下逐行分析代码的执行时间:

代码分析

要点说明:

  • for或while循环,“循环头”中的测试执行的次数,由于退出时的测试,会比其“循环体”执行的次数多1次;
  • 代码的5~7行,是for循环中嵌套的while循环,因此是由外层for的循环变量j从2到n求tj的和;
  • tj是while“循环头”的执行次数;
  • tj-1,表示“循环体”的执行次数比“循环头”少1次。

运行时间

每行代码的运行时间,乘以每行代码运行的次数,再对其求和,就能得到总运行时间。同时,也得到了输入规模n与运行时间T(n)的关系。

算法运算时间

最好情况

运行时间虽然得到了,但是我们很难从复杂的函数表达中看出规律,因此需要进一步的简化。

一个简化的方向就是考虑其最好情况。也就是说,排序算法执行之前,输入已经是排序好的数组,那么tj应为1。tj=1是因为while的“循环头”还是要做1次测试的,while循环体的代码是执行不到的。将tj代入:

最好情况

此时的表达式就清晰多了,因为ci是常量,我们再次将其简化成T(n)=an+b,这不就是个线性函数吗?线性函数具有的一切特性都可以用于分析“输入规模”与“运行时间”的关系。

最坏情况

考虑过最好情况,当然还需要考虑最坏情况。最坏情况就是,排序之前,数组是按照降序排列的(排序之后升序)。具体的说,while“循环头”的每次测试都成立直到i≤0,“循环体”每次都要执行。此时,tj=j,将其代入:

最坏情况

再次简化,就可以得到T(n)=an2+bn+c,它是一个二次函数,随着输入规模n的增大,T(n)会急剧的增加。

小结

此时,我们对于插入排序算法的分析基本结束了。可能有人会问,只分析了最好和最坏的情况,那“平均情况”是什么?

《算法导论》明确的解释说,我们大多数时候应该关注最坏情况的运行时间,理由是:

  • 最坏情况给出了任何输入运行时间的一个上限(做最坏的打算);
  • 对某些算法,最坏情况经常出现,比如检索一条不存在的信息;
  • “平均情况”往往与最坏情况大致一样差。

当然也有特别的情况,就是“平均情况”可以用“概率分析”来描述,以后介绍“随机化算法”时再讨论。

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员宝库

用 PHP 的方式实现的各类算法合集

项目地址: https://github.com/PuShaoWei/arithmetic-php About 如果说各种编程语言是程序员的招式,那么数据结构和...

3626
来自专栏数据结构与算法

牛客NOIP提高组(二)题解

好难啊,$30$分的枚举颜色dp应该比较好想把,$f[i][j]$表示第$i$个位置,填了$j$个颜色,然后先枚举一下$1$的颜色,前缀和优化一下,$O(n a...

801
来自专栏常用编程思想与算法

常用编程思想与算法

本文是在阅读Aditya Bhargava先生算法图解一书所做的总结,文中部分代码引用了原文的代码,在此感谢Aditya Bhargava先生所作出的这么简单的...

511
来自专栏tkokof 的技术,小趣及杂念

小聊聊NGUI中Panel的Clip功能(之一)

  首先来看顶点着色器(即vert),前几行都比较传统:使用ModelViewProjection来变换顶点,然后设置顶点颜色和纹理坐标,只是最后一步有些奇怪:

442
来自专栏数说工作室

统计师的Python日记【第3天:Numpy你好】

本文是【统计师的Python日记】第3天的日记 回顾一下,第1天学习了Python的基本页面、操作,以及几种主要的容器类型;第2天学习了python的函数、循环...

38712
来自专栏CreateAMind

pytorch初体验

一部分的内容在2017年1月18日Facebook发行的PyTorch相比TensorFlow、MXNet有何优势? - 罗若天的回答 - 知乎 已有。

771
来自专栏点滴积累

PhiloGL学习(4)——三维对象、加载皮肤

前言 上一篇文章中介绍了如何响应鼠标和键盘事件,本文介绍如何加载三维对象并实现给三维对象添加一个漂亮的皮肤。 一、 原理分析 我对三维的理解为:所谓三维对象无非...

3296
来自专栏郭耀华‘s Blog

剑指offer第七天

30.连续子数组的最大和 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最...

2509
来自专栏哈雷彗星撞地球

算法之路(一)----求最大子序列

对于IT行业者来说,刚参加工作,还能找点借口,说自己不擅长算法。可是工作三年以上的IT开发者,还说自己不会算法,不会设计模式就说不过去了。所以最近开始撸算法和设...

673
来自专栏技术翻译

与机器学习算法相关的数据结构

我不认为机器学习中使用的数据结构与在软件开发的其他领域中使用的数据结构有很大的不同。然而,由于许多问题的规模和难度,掌握基本知识是必不可少的。

1073

扫码关注云+社区