2.1 精确效率分析

在分析一个算法之前，要先建立有关实现技术的模型。在本书中，假设采用通用的单处理器即随机存储器（RAM）计算模型作为硬件资源。在RAM模型中，指令按一条接一条的顺序执行，没有并发操作。严格来说，应当精确的定义RAM模型的指令以及执行每条指令的代价，但是，这么做其实对理解算法的设计和分析并无本质上的帮助。RAM模型包含了真实计算机中常见的指令，包括算术指令（例如：加、减、乘、除等指令），数据移动指令（例如：存储、复制等指令）和控制指令（例如：条件和非条件转移、子程序调用等指令），其中每条指令所需的执行时间都为常量时间。一般来说，算法所需时间是与输入规模同步增长的，因而常常将一个程序的运行时间表示为其输入的函数。下面首先给出运行时间和输入规模的准确描述。

输入规模的表示方式与具体问题有关。对许多问题来说，可以用输入的元素个数来衡量输入规模，例如排序问题的输入可以用待排序数据的大小来表示。对另一些问题（如两个整数相乘），其输入规模的最佳度量是输入数在二进制表示下的位数。有时，用多个数字来表示输入规模会更精确，例如：某一个算法的输入是一个图，则输入规模可以由图中顶点数和边数来表示。在后面的内容中，都将明确给出所用的输入规模度量标准。

算法的运行时间是指在给定输入时，算法所需执行的基本操作数（步数）。在本书中，暂且假设每执行一条伪代码都要花一定量的时间。虽然每一条所花费的时间可能并非完全相同，但可以假定每次执行第i行所花时间都是常量c_i。

下面以第1章插入排序算法的伪代码为例来分析其时间复杂度。显然，该代码中的插入排序算法的时间开销与输入有关，排序1000个数字的时间比排序3个数字的时间要长，此外，即使对两个长度相同的数组进行排序，所需时间也有可能不同，这取决于两个数组原本的有序程度。

首先来分析插入排序算法中每一条指令的执行时间以及被执行的次数。表2-1给出了插入排序算法中每一条代码所需的执行时间（cost）以及被执行次数（times）。其中设n为数组A中的元素个数，t_j为第7行中while循环所做的测试次数。当for或while循环以通常方式退出时，测试要比循环体内的代码多执行1次，标志循环结束的end for或end while在不满足循环头部的测试条件时执行，因此每个结束标志只被执行1次，此外，由于注释在编译预处理阶段已被过滤掉，因此不会被执行，不占用运行时间。

表2-1 插入排序算法伪代码执行时间分析

从表2-1可知，该算法的总运行时间是每一条语句执行时间之和。如果执行一条语句需要时间c_i，该语句在整个算法执行过程中被执行了n次，那么它在总运行时间中占c_i⋅n。如果用T[n]表示该算法的总执行时间，那么有：

前面已经提到过，即便对于规模相同的输入，也会因输入的数据的有序性不同而消耗不同的运行时间。如果输入数组已经是按正序排好的，那么就会出现最佳情况，如果输入数组是按照逆序排序的，那么就会出现最坏情况。

对于最佳情况，显然对于j的任何取值，while循环体内的代码不会执行，因此，对于j=2,3,…,n，都有t_j=1。因此在最佳情况下的运行时间为：

T[n]=c₂⋅n+c₄⋅(n-1)+c₆⋅(n-1)+c₇⋅(n-1)+c₁₂⋅(n-1)

=(c₂+c₄+c₆+c₇+c₁₂)⋅n-(c₄+c₆+c₇+c₁₂)

这一运行时间可以表示为a⋅n+b，常量a和b的值依赖于各条语句的执行时间c_i，因此它是n的一个线性函数（Linear Function）。

对于最差情况，显然对于j的任何取值，while循环体内的代码会执行j-1次，因此，对于j=2,3,…,n，都有t_j=j。因此在最差情况下的运行时间为：

这一运行时间可以表示为a⋅n²+b⋅n+c，常量a、b和c的值依赖于各条语句的执行时间c_i，因此它是n的一个二次函数（quadratic function）。

至此，我们分析了插入排序的最佳情况与最坏情况。一般来说，分析算法的时间复杂度都是考察最坏情况运行时间，即：给定规模为n的任意输入，算法的最长运行时间。因为一个算法的最坏情况运行时间是在任意输入下运行时间的一个上界（upper bound），知道了这一点，就能确保算法的运行时间不会比这一时间长。而且，对于有些算法，最坏情况出现的频率相当高，重点考察最差情况具有实际意义。某些情况下，我们可能会对某个算法的平均运行时间或期望运行时间感兴趣，在这种情况下，可以借助概率分析技术来确定算法的平均或期望的运行时间。

对插入排序算法的分析还可以做一些简化。首先，上文得到在最坏情况下的运行时间是a⋅n²+b⋅n+c，现在再做进一步的抽象，重点考虑运行时间随着输入规模增大而增长的量级（order of growth），很显然，这时只需要关注a⋅n²+b⋅n+c中的最高阶项（a⋅n²），因为当n足够大时，低阶项对整个运行时间的影响可以被忽略。此外，还可以忽略最高阶项的系数a，因为对于增长率来说系数发挥的作用是次要的。因此经过两次抽象后，插入排序的最坏情况时间复杂度为Θ(n²)。符号Θ的含义将在下一节中详细介绍，暂且先知道它可以用来表示算法复杂度即可。