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

时间资源

上一篇，我们知道了如何用循环不变式来证明算法的正确性，本篇来看另一个重要方面：算法分析。分析算法的目的，是预测算法所需要的资源。资源不仅是指内存、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)会急剧的增加。

小结

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

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

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

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