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

时间资源

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

相关文章

来自专栏CDA数据分析师

提升R代码运算效率的11个实用方法

众所周知,当我们利用R语言处理大型数据集时,for循环语句的运算效率非常低。有许多种方法可以提升你的代码运算效率,但或许你更想了解运算效率能得到多大的提升。本文...

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

LOJ #108. 多项式乘法

内存限制:256 MiB时间限制:1000 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: 匿名 提交提交记录统计讨论测试数据 题目描述 这是一道...

3238
来自专栏专注数据中心高性能网络技术研发

HERD--位运算

判断一个数是否是2的次方 1 static inline int hrd_is_power_of_2(uint32_t n) 2 { 3 retur...

3439
来自专栏大数据

概率数据结构简介

在处理大型的数据集时,我们常常进行一些简单的检查,如稀有项(Unique items)的数量、最常见的项,以及数据集中是否存在某些指定的项。通常的做法是使用某种...

1916
来自专栏技术碎碎念

大数据量下的集合过滤—Bloom Filter

1564
来自专栏从流域到海域

Python惰性序列

Python的iterator就是一个惰性序列,要说明什么是惰性序列,首先我们得知道什么是惰性计算。 事实上,很多如Java在内的高级语言都支持惰性序...

1856
来自专栏TensorFlow从0到N

讨厌算法的程序员 3 - 算法分析基础

? 时间资源 上一篇,我们知道了如何用循环不变式来证明算法的正确性,本篇来看另一个重要方面:算法分析。分析算法的目的,是预测算法所需要的资源。资源不仅是指内存...

2453
来自专栏技术翻译

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

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

893
来自专栏余林丰

8.动态规划(1)——字符串的编辑距离

  动态规划的算法题往往都是各大公司笔试题的常客。在不少算法类的微信公众号中,关于“动态规划”的文章屡见不鲜,都在试图用最浅显易懂的文字来描述讲解动态规划,甚至...

3189
来自专栏xingoo, 一个梦想做发明家的程序员

《大话数据结构》冒泡排序错误修正

书中本意是想省略后端顺序表中无用的查找,但是忽略了一个问题。 原书中代码大意为: void bubblesort(Graph *g,int len){ ...

1918

扫描关注云+社区