无论是在设计还是在应用一种广泛认可的算法时，我们必须了解这种算法的性能如何。

算法的性能可以通过很多方面评判，但是通常我们最关心的是算法的运算速度。但有些时候，如果一种算法消耗了大量的存储空间，那么我们也要关注算法对内存空间的要求。不管如何，都需要一种标准和确定的方法来确定算法的性能。 之所以要了解算法的性能，其原因是多方面的。

例如：当要解决一个问题时，有很多算法可供选择，理解算法的性能有助于区分它们。如果了解每种算法的性能就能够有效地帮助我们解决问题。举例来说，垃圾回收算法，它用来回收从堆上分配的动态存储空间，并且需要相当长的时间来运行。认识到这一点之后，我们就能非常注意只在适当的时候运用此算法，就像LISP和Java所做的那样。 本文内容包括：

最坏情况分析

这是大多数算法都采用的评估方法。在其他情况下，我们可能会考虑算法的平均情况和最佳情况。但是，对最坏情况的分析同样会带来一些好处。O表示法

这是表示算法性能的最为常用的正式方法。在一定的条件因素下，O表示法指明一个函数的上限。计算的复杂度

资源消耗的大小往往与算法所需要处理的数据量的大小相辅相成。O表示法可以很好地表示一个算法的复杂度。1 最坏情况分析

在所有的情况下，绝大多数算法都会表现出不同的性能；并且，随着传入数据的不同，算法的表现也不相同。通常用来评判算法性能的三种情况是：最佳情况、平均情况与最坏情况。

对于任何算法来说，理解每种情况是如何产生的对于分析算法来说非常重要，因为算法在不同的情况下性能差异可能很大。看一种线性搜索的简单算法。线性搜索是一种自然的但效率低下的搜索技术，它简单地从数据集的头部顺序遍历到尾部。在最佳情况下，要查找的元素处于数据集的第一个位置，所以在仅仅遍历一个元素之后就找到想查找的元素。然而，在最坏情况下，要查找的元素处于数据集的最后一个位置，所以必须在遍历完所有元素之后才能找到要查找的元素。在平均情况下，可能会在数据集的中间某个位置找到元素。

1.1 为什么要做最坏情况分析

理解一种算法在各种情况下有怎样的性能是非常重要的，但是通常情况下，我们更关心算法在最坏情况下的性能如何。原因如下：

许多算法在最坏情况下执行会消耗相当长的时间。例如：在搜索元素时，数据集中根本就没有我们想查找的那个元素。我们可以想象一下，这种情况在数据库的查找应用中经常出现。考虑算法在最佳情况下的性能没有太多的意义，因为很多算法在最佳情况下的表现都相同。例如：在最佳情况下，几乎所有搜索算法都可以在一次查询中找到元素，而这并不能说明到底哪种算法更好，所以分析算法的最佳情况没有太多的意义。分析算法平均情况下的性能往往不是那么容易。甚至我们很难去界定哪种情况叫做“平均情况”。通常我们不能精确地获得平均情况下的算法性能，这是因为我们无法准确地控制算法的执行状态。最坏情况可以告诉我们算法性能的上限。分析一个算法的最坏情况可以保证在任何情况下此算法的表现都不会比最坏情况差，而其他情况肯定比最坏情况要好。

虽然我们把最坏情况当做很多算法性能的度量，但也有例外。因为有些时候我们也会用平均情况来评判算法性能。例如：随机算法中的快速排序算法，它使用了概率论的理论基础，从而有效地保证了平均情况下性能的准确性。

2 O表示法

O表示法是用来表示算法性能的最常见正式的标记法。从形式上看，在一定的条件因素下，O表示法指明了一个函数的上限值。具体来说，如果g(n)是f(n)的一个上限值，那么对于常数c，我们总是可以找到一个n(称为n0)，当n≥n0时，f(n)≤cg(n)。 通常我们以函数所处理的数据量来表示算法的性能。也就是说，对于大小为n的数据，我们用函数f(n)来表示它的算法性能。在很多情况下，我们可以完全确定f的具体值，但通常我们不需要关注此具体值。我们需要关注的是当算法处理的数据量变得无穷大时，算法的性能将趋近一个什么样的值。一个算法的增长速率或者说一个算法的增长规律非常重要，因为当输入数据量变得无穷大时，它可以用来描述算法的效率到底有多高。O表示法正是这样一种表示算法增长规律的方法。

2.1 O表示法的简单规则

当我们以增长率的角度去观察函数f(n)时，有几件事情就会变得很明显。首先，我们可以忽略常数项，因为随着n的值变得越来越大，常数项最终变得可忽略不计。例如：如果T(n)=n+50表示一个计算运行时间的算法，当所要处理的数据n的大小仅仅为1024时，此表达式的常数项对运行时间的影响就已经不到5%了。其次，我们可以忽略常数因子，同样，因为随着n的值逐渐变大，常数因子也可以忽略不计。例如：如果有两个都是用来计算运行时间的算法：T1(n)=n2和T2(n)=10n，当T1表达式中的n大于10时，T1就会大于T2。最后，我们只需要考虑高阶项的因子。因为，随着n的增加，高阶项因子的值会迅速超过低阶项因子的值。例如：如果T(n)=n2+n表示一个计算运行时间的算法，当n为1024时，表达式中低阶项因子的值已经占不到运行时间值的0.1%了。这些简单的规则用O表示法列举出来如下：

常数项用O(1)表示。当分析一个算法的运行时间时，如果知道无论它处理多大的数据量，它都至少得消耗一段固定的时间，那么就可以用常数项表示此固定的时间。对某些常数c，正式地表述为：O(c)=O(1)常量因子往往被忽略。当分析一个算法的运行时间时，如果有某些任务都将执行相同数量的次数，就可以运用此规则。例如：有三个任务的运行时间为T(n)=n，运行结果表示为O(3n)，根据规则可以简化为O(n)。对某些常数c，正式地表述为：O(cT)=cO(T)=O(T)加法运算取最大值。当分析一个算法的运行时间时，如果一个任务在另一个任务之后顺序执行，可以运用此规则。例如，有两个顺序执行的任务，其运行时间分别为：T(n)=n和T(n)=n2，运行结果表示为O(n)+O(n2)，根据规则，可以简化为O(n2)。正式地表述为：O(T1)+O(T2)=O(T1+T2)=max(O(T1), O(T2))乘法结果不需要改变，但往往可以用更紧凑的方法表示。当分析一个算法的运行时间时，如果一个任务的执行引起了另一个任务的迭代执行，可以运用此规则。2.2 O表示法的例子以及工作原理

下一节，将讨论这些规则如何帮助我们来推断算法的性能。现在，让我们来看一个具体的例子，这个例子将告诉我们在描述函数增长速率时运用这些规则有多么方便。假设某算法的运行时间由函数T（n）=3n2+10n+10来表示。 若用O表示法，此函数可以简化为：O（T（n））=O（3n2+10n+10）=O（3n2）=O（n2） 这表明，当n增长到任意大时，算法的运行时间将主要由n2项来决定。随着n不断增大，我们可以通过每一项所占整个运行时间的百分比来证明这一点。例如：当n=10时，计算结果如下：

Running time for 3n 2: 3(10)2/(3(10)2 + 10(10) + 10) = 73.2%

Running time for 10n: 10(10)/(3(10)2 + 10(10) + 10) = 24.4%

Running time for 10: 10/(3(10)2 + 10(10) + 10) = 2.4%

我们已经看到，n2占据了整个运行时间的大部分比例。现在，考虑当n=100时的结果，如下：

Running time for 3n 2: 3(100)2/(3(100)2 + 10(100) + 10) = 96.7% (Higher)

Running time for 10n: 10(100)/(3(100)2 + 10(100) + 10) = 3.2%

(Lower) Running time for 10: 10/(3(100)2 + 10(100) + 10) < 0.1% (Lower)

这里我们可以看到，n2项占据了几乎整个运行时间，同时其他项的影响力变得更小。试想一下，如果n=106，将占用多少运行时间！

3 计算复杂度

计算的复杂度在谈到算法的性能时，我们通常关注的是它的复杂度，复杂度与它处理数据量所需要的资源（通常是时间）的增长速率密切相关。O表示法能够描述一个算法的复杂度。使用O表示法，通过观察算法的整体构造，我们很容易就可以描述最坏情况下的算法复杂度。有些时候，我们也会借助于利用迭代公式和统计方法。为了理解复杂度，我们来看一种推测算法所用资源的方法。假设有一种算法，它由k条语句组成，每条语句都要消耗ci资源（通常是时间）。如果要计算它的整个运行时间，无论每条语句以什么顺序执行，我们只需要将它们的运行时间相加求和即可，也就是说从c1加到ck。通常每条语句并不是简单地按照顺序执行的，所以在计算整个运行时间时必须考虑其他更复杂的情况。例如：有些语句是在循环中执行的，那么这样一些语句所消耗的资源必须乘上迭代的次数。假设在这种算法中k=6，其中语句3~5均在循环中（1~n）执行，其他语句顺序执行，那么此算法的整体运行时间表示为：

T(n) = c 1 + c 2 + n(c 3 + c 4 + c 5) + c 6

用O表示法的规则来计算，此算法的复杂度是O（n），因为可以忽略常数项。用消耗固定资源的算法来分析问题是很透彻的。然而，回顾之前谈到的增长速度，我们并不需要非常精确的结果。当观察一个算法的整体构造时，只需要做两步：

首先，必须知道算法的哪个部分是由非常量的数据决定的；

然后，用函数列出每个部分的性能。那些消耗资源为常数项的部分在计算整个算法复杂度的过程中可以忽略。 在之前的例子中，假设T（n）表示算法的运行时间，我们必须明白，它的复杂度O（n）并没有具体表明运行此算法实际需要多少时间。

换句话说，一个增长速率低的算法并不意味着它会消耗更少的运行时间。事实上，算法的复杂度并没有具体的计量单位。它只是表明当计算数据量的大小变化时，将如何影响算法所消耗的资源。

例如：用O（n）表示T（n）复杂度只说明算法的运行时间与因素n成正比，在特定n的取值条件下，T（n）能够达到上限值。正式地说，当我们谈到T（n）≤cn时，随着数据的变化，c作为一个常量因子不会影响到算法的运行时间。这就像在某种类型的计算机上运行算法，编译器会生成与算法有关的机器码和相关常量。 很多时候我们都会遇到很多复杂的计算，所以需要非常熟悉这些计算方法。表4-1列出一些常见的复杂计算发生时的复杂度。表4-2列出了当n变化时，这些复杂度的增长速率是如何变化的。图4-1是表4-2的图形式表示。

表4-1

表4-2

就像一种算法的复杂度几乎不关注算法具体的运行时间，衡量算法的复杂度也没有高效或低效之说。虽然复杂度在一定程度上说明了算法的运算效率，但一个特定的复杂度要根据具体的情况来衡量它是否高效。一般来说，在给定一定标准的情况下，能够使此算法表现最佳时，我们就认为此算法是高效的。通常，在解决同一个问题时，如果一种算法的复杂度比其他算法的复杂度都低，并且没有过多的常数项，我们就可以认为此算法是高效的。但也会有一些棘手的问题，在这些问题中，如果不设定一个近似值就无法找到一个“有效的”解决方法。这是一类特殊的问题，称为NP完全问题（NP-complete problem）。

虽然算法的复杂度是衡量算法性能的重要参考因素，但在实际应用中，我们通常还要考虑其他更多的因素。例如：当两种算法有同样的复杂度时，就得考虑对算法影响不太大的条件和因素。如果有种算法，数据量大小的变化对它的性能没有太大的影响，那么一个复杂度大且常量很小的算法所表现出的性能可能比一个复杂度小但常量很大的算法所表现出的性能更好。其他一些值得考虑的因素包括：算法的复杂度会如何维持和发展，以及如何使一种算法在实际中更加有效地实现。一个高效的实现并不能总是影响算法的复杂度，但它可以降低常量因素的影响，从而使算法在实际应用中更加高效。

3.1 实例分析：插入排序

本节描述插入排序法在最坏情况下对运行时间的分析。

插入排序是一种简单的排序算法，它在一个有序的数据集中查找放置新元素的位置，并将新元素插入进去。插入排序的代码如示例4-1所示。

首先要知道，哪行代码会受要排序的数据量影响。我们看到代码中有一个嵌套循环，外层的迭代数从i到size-1，内层的迭代数从j-1到所要插入的新元素的正确位置。其他代码的运行都会消耗一段固定的时间，与要排序元素的个数无关。

通常情况下，变量n定义为与算法性能有关的参数。考虑到这一点，外层循环的运行时间T（n）=n-1，会固定消耗一段时间。检查一下内部矛盾循环，考虑到最坏情况，假设在插入每个元素之前不得不从头到尾遍历整个有序数据集。这是因为，内层循环要为第1个元素执行一遍，为第2个元素执行第二遍，依次类推，直到外部循环结束。实际上，这就是一个求1到n-1累加和的过程，求和的结果为：T（n）=（n（n+1）/2）-n，从结果看得出消耗了一定量的时间。（这个等式来源于著名的从1到n的求和公式。）结果如下：

#include <stdlib.h>#include <string.h>int issort(void *data, int size, int esize, int (*compare)(const void *key1,   const void *key2)) {char               *a = data;void               *key;int                i,                   j;// Allocate storage for the key element.                                     *if ((key = (char *)malloc(esize)) == NULL)   return -1;;;Repeatedly insert a key element among the sorted elements.             for (j = 1; j < size; j++) {     memcpy(key, &a[j * esize], esize);   i = j - 1;   // Determine the position at which to insert the key element   while (i >= 0 && compare(&a[i * esize], key) > 0) {      memcpy(&a[(i + 1) * esize], &a[i * esize], esize);      i--;   }   memcpy(&a[(i + 1) * esize], key, esize);}//Free the storage allocated for sorting.                                   *free(key);return 0;}