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

时间资源

上一篇,我们知道了如何用循环不变式来证明 算法的正确性,本篇来看另一个重要方面:算法分析。分析算法的目的,是预测算法所需要的资源。资源不仅是指内存、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 条评论
登录 后参与评论

相关文章

来自专栏跟着阿笨一起玩NET

c#实现打印功能

2762
来自专栏hbbliyong

WPF Trigger for IsSelected in a DataTemplate for ListBox items

<DataTemplate DataType="{x:Type vm:HeaderSlugViewModel}"> <vw:HeaderSlug...

4064
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5456
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3145
来自专栏魂祭心

原 canvas绘制clock

4074
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5327
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

4848
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.2K7
来自专栏码匠的流水账

聊聊NettyConnector的start及shutdown

reactor-netty-0.7.6.RELEASE-sources.jar!/reactor/ipc/netty/NettyConnector.java

851
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

4025

扫码关注云+社区