2.2 分析算法
分析算法的结果意味着预测算法需要的资源。虽然有时我们主要关心像内存、通信带宽或计算机硬件这类资源，但是通常我们想度量的是计算时间。一般来说，通过分析求解某个问题的几种候选算法，我们可以选出一种最有效的算法。这种分析可能指出不止一个可行的候选算法，但是在这个过程中，我们往往可以抛弃几个较差的算法。
在能够分析一个算法之前，我们必须有一个要使用的实现技术的模型，包括描述所用资源及其代价的模型。对本书的大多数章节，我们假定一种通用的单处理器计算模型——随机访问机（random-access machine，RAM）来作为我们的实现技术，算法可以用计算机程序来实现。在RAM模型中，指令一条接一条地执行，没有并发操作。
严格地说，我们应该精确地定义RAM模型的指令及其代价。然而，这样做既乏味又对算法的设计与分析没有多大意义。我们还要注意不能滥用RAM模型。例如，如果一台RAM有一条排序指令，会怎样呢？这时，我们只用一条指令就能排序。这样的RAM是不现实的，因为真实的计算机并没有这样的指令。所以，我们的指导性意见是真实计算机如何设计，RAM就如何设计。RAM模型包含真实计算机中常见的指令：算术指令（如加法、减法、乘法、除法、取余、向下取整、向上取整）、数据移动指令（装入、存储、复制）和控制指令（条件与无条件转移、子程序调用与返回）。每条这样的指令所需时间都为常量。
RAM模型中的数据类型有整数型和浮点实数型。虽然在本书中，我们一般不关心精度，但是在某些应用中，精度是至关重要的。我们还对每个数据字的规模假定一个范围。例如，当处理规模为n的输入时，我们一般假定对某个大于等于1的常量c，整数由clgn位来表示。我们要求c大于等于1，这样每个字都可以保存n的值，从而使我们能索引单个输入元素。我们限制c为常量，这样字长就不会任意增长。（如果字长可以任意增长，我们就能在一个字中存储巨量的数据，并且其上的操作都在常量时间内进行，这种情况显然不现实。）
23
真实的计算机包含一些上面未列出的指令，这些指令代表了RAM模型中的一个灰色区域。例如，指数运算是一条常量时间的指令吗？一般情况下不是；当x和y都是实数时，计算xy需要若干条指令。然而，在受限情况下，指数运算又是一个常量时间的操作。许多计算机都有“左移”指令，它在常量时间内将一个整数的各位向左移k位。在大多数计算机中，将一个整数的各位向左移一位等价于将该整数乘以2，结果将一个整数的各位向左移k位等价于将该整数乘以2k。所以，只要k不大于一个计算机字中的位数，这样的计算机就可以由一条常量时间的指令来计算2k，即将整数1向左移k位。我们尽量避免RAM模型中这样的灰色区域，但是，当k是一个足够小的正整数时，我们将把2k的计算看成一个常量时间的操作。
在RAM模型中，我们并不试图对当代计算机中常见的内存层次进行建模。也就是说，我们没有对高速缓存和虚拟内存进行建模。几种计算模型试图解释内存层次的影响，对真实计算机上运行的真实程序，这种影响有时是重大的。本书中的一些问题考查了内存层次的影响，但是本书的大部分分析将不考虑这些影响。与RAM模型相比，包含内存层次的模型要复杂得多，所以可能难于使用。此外，RAM模型分析通常能够很好地预测实际计算机上的性能。
采用RAM模型即使分析一个简单的算法也可能是一个挑战。需要的数学工具可能包括组合学、概率论、代数技巧，以及识别一个公式中最有意义的项的能力。因为对每个可能的输入，算法的行为可能不同，所以我们需要一种方法来以简单的、易于理解的公式的形式总结那样的行为。
即使我们通常只选择一种机器模型来分析某个给定的算法，在决定如何表达我们的分析时仍然面临许多选择。我们想要一种表示方法，它的书写和处理都比较简单，并能够表明算法资源需求的重要特征，同时能够抑制乏味的细节。
插入排序算法的分析
过程INSERTION-SORT需要的时间依赖于输入：排序1000个数比排序三个数需要更长的时间。此外，依据它们已被排序的程度，INSERTION-SORT可能需要不同数量的时间来排序两个具有相同规模的输入序列。一般来说，算法需要的时间与输入的规模同步增长，所以通常把一个程序的运行时间描述成其输入规模的函数。为此，我们必须更仔细地定义术语“运行时间”和“输入规模”。
24
输入规模的最佳概念依赖于研究的问题。对许多问题，如排序或计算离散傅里叶变换，最自然的量度是输入中的项数，例如，待排序数组的规模n。对其他许多问题，如两个整数相乘，输入规模的最佳量度是用通常的二进制记号表示输入所需的总位数。有时，用两个数而不是一个数来描述输入规模可能更合适。例如，若某个算法的输入是一个图，则输入规模可以用该图中的顶点数和边数来描述。对于研究的每个问题，我们将指出所使用的输入规模量度。
一个算法在特定输入上的运行时间是指执行的基本操作数或步数。定义“步”的概念以便尽量独立于机器是方便的。目前，让我们采纳以下观点，执行每行伪代码需要常量时间。虽然一行与另一行可能需要不同数量的时间，但是我们假定第i行的每次执行需要时间ci，其中ci是一个常量。这个观点与RAM模型是一致的，并且也反映了伪代码在大多数真实计算机上如何实现。
这里有一些微妙的东西。我们用英语说明的计算步往往是一个过程的变种，该过程需要的时间不止一个常量。例如，本书后面可能会说“按x坐标排序这些点”，正如我们将看到的，该计算步需要的时间多于一个常量。注意到，一个调用子程序的语句也需要常量时间，尽管该子程序一旦被调用可能需要更多时间。也就是说，我们区分调用子程序的过程（传递参数到该子程序等）与执行该子程序的过程。
该特性对像内存这样的资源不必成立。访问m个存储字且执行n次的一条语句不必访问mn个不同的存储字。
在下面的讨论中，我们由繁到简地改进INSERTION-SORT运行时间的表达式，最初的公式使用所有语句代价ci，而最终的记号则更加简明、更容易处理，简单得多。这种较简单的记号比较易于用来判定一个算法是否比另一个更有效。
我们首先给出过程INSERTION-SORT中，每条语句的执行时间和执行次数。对j=2，3，…，n，其中n=A.length，假设tj表示对那个值j第5行执行while循环测试的次数。当一个for或while循环按通常的方式（即由于循环头中的测试）退出时，执行测试的次数比执行循环体的次数多1。我们假定注释是不可执行的语句，
25所以它们不需要时间。
该算法的运行时间是执行每条语句的运行时间之和。需要执行ci步且执行n次的一条语句将贡献cin给总运行时间。为计算在具有n个值的输入上INSERTION-SORT的运行时间T［n］，我们将代价与次数列对应元素之积求和，得：
T(n)=c1n+c2（n-1)+c4（n-1)+c5∑nj=2tj+c6∑nj=2（tj-1)+c7∑nj=2（tj-1)+c8（n-1）
即使对给定规模的输入，一个算法的运行时间也可能依赖于给定的是该规模下的哪个输入。例如，在INSERTION-SORT中，若输入数组已排好序，则出现最佳情况。这时，对每个j=2，3，…，n，我们发现在第5行，当i取其初值j-1时，有A［i］≤key。从而对j=2，3，…，n，有tj=1，该最佳情况的运行时间为：
T(n)=c1n+c2(n-1)+c4(n-1)+c5(n-1)+c8(n-1)
=(c1+c2+c4+c5+c8)n-(c2+c4+c5+c8)
我们可以把该运行时间表示为an+b，其中常量a和b依赖于语句代价ci。因此，它是n的线性函数。
若输入数组已反向排序，即按递减序排好序，则导致最坏情况。我们必须将每个元素A［j］与整个已排序子数组A［1..j-1］中的每个元素进行比较，所以对j=2，3，…，n，有tj=j。注意到
26
∑nj=2j=n(n+1)2-1
和
∑nj=2(j-1)=n(n-1)2
（对于如何求和，请参见附录A），我们发现在最坏情况下，INSERTION-SORT的运行时间为
T(n)=c1n+c2(n-1)+c4(n-1)+c5n(n+1)2-1
+c6n(n-1)2+c7n(n-1)2+c8(n-1)
=c52+c62+c72n2+c1+c2+c4+c52-c62-c72+c8n
-(c2+c4+c5+c8)
我们可以把该最坏情况运行时间表示为an2+bn+c，其中常量a、b和c又依赖于语句代价ci。因此，它是n的二次函数。
虽然在以后的章节中我们将看到一些有趣的“随机化”算法，即使对固定的输入，其行为也可能变化，但是通常的情况是像插入排序那样，算法的运行时间对给定的输入是固定的。
最坏情况与平均情况分析
在分析插入排序时，我们既研究了最佳情况，其中输入数组已排好序，又研究了最坏情况，其中输入数组已反向排好序。然而，在本书的余下部分中，我们往往集中于只求最坏情况运行时间，即对规模为n的任何输入，算法的最长运行时间。下面给出这样做的三点理由：
一个算法的最坏情况运行时间给出了任何输入的运行时间的一个上界。知道了这个界，就能确保该算法绝不需要更长的时间。我们不必对运行时间做某种复杂的猜测并可以期望它不会变得更坏。
对某些算法，最坏情况经常出现。例如，当在数据库中检索一条特定信息时，若该信息不在数据库中出现，则检索算法的最坏情况会经常出现。在某些应用中，对缺失信息的检索可能是频繁的。
27
“平均情况”往往与最坏情况大致一样差。假定随机选择n个数并应用插入排序。需要多长时间来确定在子数组A［1..j-1］的什么位置插入元素A［j］？平均来说，A［1..j-1］中的一半元素小于A［j］，一半元素大于A［j］。所以，平均来说，我们检查子数组A［1..j-1］的一半，那么tj大约为j/2。导致的平均情况运行时间结果像最坏情况运行时间一样，也是输入规模的一个二次函数。
在某些特定情况下，我们会对一个算法的平均情况运行时间感兴趣；贯穿于本书，我们将看到概率分析技术被用于各种算法。平均情况分析的范围有限，因为对于特定的问题，什么构成一种“平均”输入并不明显。我们常常假定给定规模的所有输入具有相同的可能性。实际上，该假设可能不成立，但是，有时可以使用随机化算法，它做出一些随机的选择，以允许进行概率分析并产生某个期望的运行时间。在第5章以及后续的其他几章中，我们将进一步探究随机化算法。
增长量级
我们使用某些简化的抽象来使过程INSERTION-SORT的分析更加容易。首先，通过使用常量ci表示这些代价来忽略每条语句的实际代价。其次，注意到这些常量也提供了比我们真正需要的要多的细节：把最坏情况运行时间表示为an2+bn+c，其中常量a、b和c依赖于语句代价ci。这样，我们不但忽略实际的语句代价，而且也忽略抽象的代价ci。
现在我们做出一种更简化的抽象：即我们真正感兴趣的运行时间的增长率或增长量级。所以我们只考虑公式中最重要的项（例如，an2），因为当n的值很大时，低阶项相对来说不太重要。我们也忽略最重要的项的常系数，因为对大的输入，在确定计算效率时常量因子不如增长率重要。对于插入排序，当我们忽略低阶项和最重要的项的常系数时，只剩下最重要的项中的因子n2。我们记插入排序具有最坏情况运行时间Θ（n2）（读作“theta n平方”）。本章非形式化地使用Θ记号，第3章将给出其精确定义。
如果一个算法的最坏情况运行时间具有比另一个算法更低的增长量级，那么我们通常认为前者比后者更有效。由于常量因子和低阶项，对于小的输入，运行时间具有较高增长量级的一个算法与运行时间具有较低增长量级的另一个算法相比，
28其可能需要较少的时间。但是对足够大的输入，例如，一个Θ（n2）的算法在最坏情况下比另一个Θ（n3）的算法要运行得更快。
练习
2.2-1 用Θ记号表示函数n3/1000-100n2-100n+3。
2.2-2 考虑排序存储在数组A中的n个数：首先找出A中的最小元素并将其与A［1］中的元素进行交换。接着，找出A中的次最小元素并将其与A［2］中的元素进行交换。对A中前n-1个元素按该方式继续。该算法称为选择算法，写出其伪代码。该算法维持的循环不变式是什么？为什么它只需要对前n-1个元素，而不是对所有n个元素运行？用Θ记号给出选择排序的最好情况与最坏情况运行时间。
2.2-3 再次考虑线性查找问题（参见练习2.1-3）。假定要查找的元素等可能地为数组中的任意元素，平均需要检查输入序列的多少元素？最坏情况又如何呢？用Θ记号给出线性查找的平均情况和最坏情况运行时间。证明你的答案。
2.2-4 我们可以如何修改几乎任意算法来使之具有良好的最好情况运行时间？
