时间资源
上一篇,我们知道了如何用循环不变式来证明 算法的正确性,本篇来看另一个重要方面:算法分析。分析算法的目的,是预测算法所需要的资源。资源不仅是指内存、CPU等硬件资源,人们更关注的是计算时间(时间资源)。
到这里可能会产生一个疑问,计算时间与硬件资源强相关,不同的硬件配置下计算时间就不同。那么如何来衡量算法的效率呢?
答案是必须有一个稳定的硬件模型。在此基础上,才能屏蔽掉硬件配置不同导致的算法运行时间的差异,从而单单显露出算法本身的优劣。
算法分析的环境模型
《算法导论》中,明确的定义了该模型:通用的单处理器/RAM计算模型(RAM,随机访问)。这是大多数讲算法的书里没有提到的重要前提。
模型指标:
所有算法的运行,都基于上述环境模型,比较的基础就有了。
算法分析基础
算法分析的两个重要概念就是输入规模和运行时间。
输入规模
拿 插入排序 举例,排序1000个数肯定比排序10个数需要更长的时间。这里的1000和10就是不同的输入规模。
输入规模的度量,对于不同的问题其度量的单位是不同的。对于插入排序来说,其度量是数组中数的个数n。对于某个算法的输入是一个图(Graph)的,则输入规模可以用该图中的顶点数n1和边数n2——两个量来描述。每个具体问题,我们都要指出所使用的输入规模度量。
运行时间
运行时间的度量,并非我们所用的时、分、秒。前面的环境模型中,我们假设了每条指令所需时间都是常量,这里我们再更进一步,执行第i行代码的每次执行需要时间为ci,无论该行代码循环多少次,每次都一样。那么程序运行的总时间就是,每行代码执行时间ci之和。
算法需要的时间与输入的规模同步增长,所以通常把一个程序的运行时间描述成其输入规模的函数。
插入排序算法的分析
有了“输入规模”和“运行时间”两个基本概念,我们仍以插入排序为例,对其伪码进行分析。具体做法就是:计算每行代码执行时间ci之和,得出输入规模与运行时间的关系。
以下逐行分析代码的执行时间:
代码分析
要点说明:
运行时间
每行代码的运行时间,乘以每行代码运行的次数,再对其求和,就能得到总运行时间。同时,也得到了输入规模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)会急剧的增加。
小结
此时,我们对于插入排序算法的分析基本结束了。可能有人会问,只分析了最好和最坏的情况,那“平均情况”是什么?
《算法导论》明确的解释说,我们大多数时候应该关注最坏情况的运行时间,理由是:
当然也有特别的情况,就是“平均情况”可以用“概率分析”来描述,以后介绍“随机化算法”时再讨论。