算法导论教材

算法导论

INTRODUCTIONTO

ALGORITHMS

•ThomasH.Cormen

•CharlesE.Lciserson

•RonaldL.Rivest

•CliffordStein

TheMITPress

关于本书

本书是N1IT的电子工程系和计算机系的算法教材，四个作者都是计算机界赫赫有

名的大师，其中RonaldL.Rivest教授是RSA公钥加密算法的发明者，2002年ACM图

灵奖的获得者之一。

本书的第一部分是算法学习的数学基础知识介绍；第二部分分类介绍常用算法和

数据结构；第三部分是高级专题，介绍包括并行算法、NP问题、近似算法等在内的高

级科研专题。其中基础知识部分适合初学者，高级专题部分则适合作为研究生的研究

课题。本书的最大特点就是每条算法的设计分析都有严密的证明，令读者知其然而知

其所以然。本书既可以作为算法学习用书，也可以作为一本算法和数据结构的字典，

适合各类读者，十分具有收藏价值。本书使用类似Pascal的伪代码进行描述，并不拘

泥于语言的细节，适合使用各种编程语言的读者。

这份电子版是基于南京大学潘金贵教授等人翻译的第一版1,由cornucopia,

DailyByte.Lv,setter,starfish等人OCR并用呼比X排版而成。在校对排版的过程中，

我们修改了原来翻译版中的一些明显错误，重新组织了一些翻译得不通顺的语句，并

对照英文版的第二版，对一些内容进行了适当的删减和增补。

此电子版仅供各位算法爱好者学习参考使用，请勿用于任何商业用途。如果您真

的喜欢这本书，建议您去书店买一本英文版，此书第二版的英文影印版已由高等教育

出版社于2002年5月出版。

Starfish

2003年5月24日

1书名为《现代计算机常用数据结构和算法》，南京大学出版社出版，现已绝版

目录

关于本书ii

第一部分基础知识1

第一章算法概念3

1.1算法.............................................................3

1.1.1插入排序...................................................4

1.1.2伪代码的使用约定...........................................5

1.2算法分析.........................................................7

1.2.1插入排序算法的分析.........................................7

1.2.2最坏情况和平均情况分析....................................10

1.2.3增长的量级................................................10

1.3算法设计........................................................11

1.3.1分治法.....................................................12

1.3.2分治算法的分析.............................................14

1.3.3合并排序算法的分析........................................14

1.4小结............................................................15

思考题................................................................16

第二章函数的增长19

2.1渐近记号........................................................19

2.1.10-记号...................................................19

2.1.2O-记号...................................................22

2.1,3。一记号...................................................23

iv目录

2.1.4方程中的渐近记号..........................................23

2.1.5o-记号...................................................25

2.1.6a-记号...................................................25

2.1.7不同函数间的比较..........................................26

2.2标准记号体系和通用函数..........................................27

2.2.1单调性.....................................................27

2.2.2底（Floor）和顶（Ceiling）...............................................28

2.2.3多项式.....................................................28

2.2.4指数式.....................................................28

2.2.5对数式.....................................................29

2.2.6阶乘......................................................31

2.2.7多重对数函数...............................................31

2.2.8斐波那契数（Fibonaccinumbers）.....................................32

思考题...............................................................33

第三章求和运算37

3.1求和公式和性质...................................................37

3.1.1线性性质................................................38

3.1.2算术级数..................................................38

3.1.3儿何级数..................................................38

3.1.4调和级数..................................................39

3.1.5积分级数与微分级数........................................39

3.1.6套迭级数..................................................39

3.1.7积........................................................40

3.2和式的界........................................................40

3.2.1数学归纳法................................................41

3.2.2对项的限界................................................42

3.2.3分解和式..................................................43

3.2.4积分近似公式...............................................45

思考题46

第一部分

基础知识

2

在学习本篇的内容时，我们建议读者不必一次将这些数学内容全部消化。先浏览

一下这部分的各章，看看它们包含哪些内容，然后直接去读集中谈算法的章节。在阅

读这些章节时，如果需要对算法分析中所用到的数学工具有个更好的理解的话，再回

过头来看这部分。当然，读者也可顺序地学习这儿章，以便很好地掌握有关的数学技

巧。

本篇各章的内容安排如下：

•第一章介绍本书将用到的算法分析和设计的框架。

•第二章精确定义了儿种渐近记号，其目的是使读者采用的记号与本书中的一致，

而不在于向读者介绍新的数学概念。

•第三章给出了对和式求值和限界的方法，这在算法分析中是常常会遇到的。

•第四章将给出求解递归式的儿种方法。我们已在第一章中用这些方法分析了合并

排序，后面还将多次用到它们。一种有效的技术是“主方法”，它可被用来解决

分治算法中出现的递归式。第四章的大部分内容花在证明主方法的正确性，读者

若不感兴趣可以略过。

•第五章包含了有关集合、关系、函数、图和树的基本定义和记号。这一章还给出

了这些数学对象的一些基本性质。如果读者已学过离散数学课程，则可以略过这

部分内容。

•第六章首先介绍计数的基本原则，即排列和组合等内容。这一章的其余部分包含

基本概率的定义和性质。

第一章算法概念

本章是介绍书中将要用到的算法分析和设计的框架。这部分内容基本上是自含

的，但同时也会引用到将在后面介绍的一些内容。

首先，我们要讨论儿个一般的计算问题及用到的算法，并以排序问题作为主要的

例子来叙述。为了描述算法，下面引进一种一般程序员都应该熟悉的“伪代码”。作

为第一个例子，我们将考察插入排序，分析它的执行时间，并引进种能反映出被排

序项数目与运行时间关系的表示法。接着，我们介绍算法设计中的分治方法，并用它

来设计合并排序算法。最后，我们对两种排序算法进行了比较。

§1.1算法

算法可以形式化地定义为任意一个良定义的计算过程，它以一个或多个值作为输

入，并产生出一个或多个值作为输出。因而，一个算法也就是一系列将输入转换为输

出的计算步骤。

一个算法还可以被看作是用来解决一个良定义计算问题的工具。对问题的描述是

用一般的语言来规定输入和输出之间的关系，而对应的算法则给出一个可以获得该输

入输出关系的计算过程。

为了开始研究算法，我们来看这样一个问题：将一系列数排成非降序。这个问题

在实践中很常见，从中可以看出许多标准的算法设计技术和分析工具是如何应用的。

下面是对排序问题的定义：

输入：一系列数（仰,&2,…，％）；

输出：对输入序列的一个变换（重排列）…,或）,

其中a；SS…S*。

对一个具体的输入序列（41,51,69,36,51,68）,由排序算法返回的结果序列为

（36,41,51,51,68,69）。这样的一个输入序列被称为是该排序问题的一个实例。一般地，

4算法概念

一个问题的实例是由所有满足问题陈述中所给出的限制，并能计算出该问题的一个结

果的所有输入所构成的。

在计算机科学中，排序是一个很基本的操作（许多程序把它作为一个中间步

骤），因而人们设计出了大量的排序算法。对于一个具体应用，选择哪一个算法最合

适，要取决于待排序的元素个数及其已被排序的程度、所使用的存储设备（主存，磁

盘或磁带），等等。

若对每一个输入实例，一个算法都能停止并给出正确的答案，则说这个算法是正

确的，并且说这个正确的算法解决了给定的计算问题。一个不正确的算法对某些输入

实例可能不会停止，或者能够停止但给出的不是所需的答案。与一般人所认为的恰恰

相反，不正确的算法在其错误率可以被控制的情况下可能是很有用的。这一点我们将

在第三十三章讨论寻找大的质数的算法时看到。但一般来说我们还是考虑正确的算

法。

一个算法可以用自然语言或一段计算机程序或一种硬件设计来说明，唯一的要求

就是该说明必须给出一个对计算过程的精确描述。

在本书中，我们将以伪代码写成的程序来表示算法，此处伪代码与C,Pascal或

Algol很接近。如果读者熟悉这几种语言中的任何一种，则在读算法时不应该有任何问

题。伪代码与真代码的区别在于，前者可以引用任何具有表达力的方法来最清晰、最

简洁地表达算法。此外，伪代码不大考虑软件工程中的一些问题。例如，为了更简明

地表达某个算法的实质，在伪代码中常常忽略数据抽象、模块性、出错处理等问题。

插入排序

我们首先看一看插入排序。这种算法对少量元素的排序较为有效。插入排序与人

们在打牌时整理手上的牌的方式有点相似。在开始打牌时，我们的左手是空的，所有

的牌都面朝下放在桌上。然后，一次一张地从桌上拿牌并插入左手中正确的位置。为

了找到这个正确位置，自左向右地将这张牌与手中已有的每一张牌比较。

插入排序的伪代码用过程INSERTION-SORT来表示，其参数为包含n个待排序数

的数组41.何。（在下面的代码段中，4中元素个数"用Ze%抗国表示。）输入数

据在月中进行重排，任何时候只有固定数目的几个元素要暂存在数组之外。当过程

INSERTION-SORT结束时，数组力中就是已排好序的输出数序列。

1.1算法5

3

3

3

3

123456

图1.1:插入排序算法的工作过程

INSERTION-SORT（A）

1forj<—2tolength[A\

2dokey<—A[j]

3△将A[j]插入到排好序的序列川1.J—1]中

4j-1

5whilei>0andA[i]>key

6doA[i+1]A[z]

7i^i-1

8A\i+1]<—key

图1.1显示了在A=（5,2,4,6J,3）时算法的工作过程。下标，指示被插到手中去

的“当前牌”。下标）的位置用一个圆圈指示。数组元素1]构成了手中已排好

序的牌，1..句对应于在桌上的牌。下标）♦自左向右地在数组中移动。在每一轮外

循环（foi•语句）中，A[j]由数组中被挑出（第2行）。然后，从位置1开始，每个

元素都相继地向右移动一格，直至找到A团的正确位置（第4-7行），再将其插入。

伪代码的使用约定

在伪代码的使用中有以下一些约定：

1.书写上的“缩进”表示程序中的子结构。例如，从第1行开始的for循环的循环

体包括第2-8行。从第5行开始的while循环的循环体包括第6-7行。这种缩进风格

6算法概念

也适用于ifthen-else语句。缩进取代传统的begin和end语句来表示程序的块结

构，可大大提高代码的清晰性。

2.while,for,repeat等循环结构和if-then-else条件结构与Pascal中相同。

3.符号表示后面部分是个注释。

4.多重赋值t7-e是将表达式e的值赋给变量i和，，这种表示与/—e和

i—j等价。

5.变量（如?力和key）局部于特定过程。不能不加显式说明就使用全局变量。

6.数组元素的存取直接由数组名后跟“[下标]”表示。例如，川力指示数组4的

第，个元素。符号用来指示数组中值的范围，例如，川1.J]表示包含元素

A[l],A[2],...,A[j]的子数组。

7.复合数据用对象（object）来表示，对象由属性（attribute）和域（field）构成。域

的存取接是由域名后接由方括号括住的对象名表示。例如，数组可以被看作是一

个对象，其属性有Zeng机，表示其中的元素个数，如/eng班园表示数组4中的

元素个数。在表示数组元素和对象属性时都要用到方括号，一般来说从上下文就

可以看出其含义。用于表示一个数组或对象的变量被看作是指向表示数组或对象

的数据的一个指针。对于某个对象c的所有域/赋值沙一工就使得f[y]=/㈤。

更进一步，若有/同—3,则不仅有/同=3,同时有/期=3。换言之，在赋值

y一C后，立和沙指向同一个对象。有时，一个指针不指向任何对象，这时，我

们赋给它NILo

8.参数用按值传递方式传给一个过程：被调过程接收参数的一份副本，若它对某个

参数赋值，则这种变化对调用过程是不可见的。当传递一个对象时，只是拷贝指

向该对象的指针、而不拷贝其各个域。例如，设了是一个被调过程中的参数，则

赋值c-对调用过程是不可见的，但赋值f[x]_3是可见的。

习题

1.1.1以图L1作为一个模型，说明INSERTIONSORT作用于数组4=（31,41,59,26,41,58）

上的过程。

1.2算法分析7

1.1.2改写INSERTIONSORT过程，使排序的输出序列呈降序。

1.1.3考虑下面的查找问题：

输入：一列数A-（ai,a2）…，a»）和一个值v

输出：下标3使得川竹=%或当。不在4中出现时为NIL。

写出针对这个问题的线性查找的伪代码。

1.1.4有两个各存放在数组4和8中的72位二进整数，考虑它们的相加问题。两个整

数的和以二进形式放在具有n+1个元素的数组。中。请给出这个问题的形式化描述并

写出伪代码。

§1.2算法分析

算法分析即指对一个算法所需的资源进行预测。一般来说，资源是指计算时间，

有时也指存储器、通信带宽或逻辑门等。给定一个问题后，通过分析儿个候选算法，

可以从中选出一个最有效的算法。

在分析一个算法前，要建立有关实现技术的模型。包括描述所用资源及代价的模

型，本书主要采用一种单处理器一随机存取器（RAM）来作为计算模型，算法即可用

计算机程序来奉达。在RAM模型中，指令一条接一条地执行，没有并发操作。在后面

儿章中，我们将讨论有关并行计算机的模型。

算法分析有一定的困难，即便是分析一个很简单的算法也是这样。所用到的数学

工具包括离散数学、组合论、初等概率论等等。•个算法在不同输入时其行为可能不

一样，因而我们需要用一些简单、易懂的公式来总结其行为。

即使我们只选一种机器模型来分析算法，在表达所做的分析时还会面临不少选

择。我们的目标之一是所选表示方式要易于书写、操纵，要能显示出算法的资源要求

的特性，同时避免不必要的细节。

插入排序算法的分析

INSERTION-SORT过程的运行时间与输入有关：排序1000个数的时间比排序三个

数的时间要长。还有，即使对两个长度相同的输入序列，算法的运行时间的也可能不

同，这取决于它们已排序的程度。一般地，算法所需时间是与输入规模同步增长的，

8算法概念

因而常常将一个程序的运行时间表示为其输入的函数。这就要求对术语“运行时间”

和“输入规模”更仔细地加以定义。

输入规模的概念与具体问题有关。对许多问题来说（如排序或计算离散傅利叶变

换），最自然的量度标准是输入中的元素个数；例如，待排序的数组大小n。对另一

些问题（例如两个整数相乘），其输入规模的最佳量度是输入数在二进制表示下的位

数。有时，用二个数（而非一个）来表示输入可能更合适。例如，某一算法的输入是

个图，则输入规模可由图中顶点数和边数来表示。在下面讨论的每一个问题中，我们

都将指明所用的量度标准。

一个算法的运行时间是指在特定输入时所执行的基本操作的数目（或步数）。可

以很方便地定义独立于具体机器的“步骤”概念。目前我们先来用以下观点，每执行

一行伪代码都要花费一定量的时间。虽然每一行所花的时间可能不同，我们假定每次

执行第，行所花的时间都是常量这种观点与RAM模型是一致的，同时也反映出了

伪代码在真实计算机上是如何实现的。

下面的讨沦中，我们由繁到简地给出INSERTION-SORT运行时间的表达式。简单的

表达式使得我们更容易从众多的算法中选择出最为有效的一个。

我们先给出INSERTION-SORT过程中每一条指令的执行时间及执行的次数。对

j=2,3....,n,n—length[A],设^为第5行中whiic循环所做的测试次数。另外，还

假定注释部分是不可执行的。因而不占运行时间。

INSERTION-SORT⑷COSTTIMES

1forj_2tolength[A\Cl

1

--X

2dokey<-A[j]C2-

3△将A[j]插入到排好序的序列用1.J一1]中0-

1

;X

E—j-1C4

4f

5whilei>0andA\i]>keyC52

2

•2

6doA\i+1]<—A\i]=

?

7i~i—\T=2

I

-X

8A\i+1]<—key出

该算法总的运行时间是每一条语句执行时间之和，若执行一条语句要4步，总共

要执行几次这条语句，则该语句在整个算法中的总运行时间为3n。为计算算法的总运

1.2算法分析9

行时间下⑺)，我们对每一对cost与times之积求和，得：

nn

T[n)—C\n+C2(n—1)+—1)+C5):tj+CQ)-1)

j=2j=2

n

+。7与-1)+C8(n-1)

)=2

即便是对给定规模的输入，一个算法的运行时间还与该规模下哪一种输入

有关。例如在INSERTION-SORT中，当输入序列已排好序时出现最佳情况。对于

7=2,3,…中的每一个值，在第5行中有力因W左冲，。的初值是，一1,因而对于每

一个j=2,3,...,n,tj=1,最佳运行时间为

T(n)—c1n+C2(n-1)+c4fn—1)+c^(n—1)+c^(n—1)

=(C1+。2+。4+。5+c8)n~(c2+。4+C5+c8)

这个式子还可表达成an+b,其中常数a和b依赖于G；即该式是n的一个线性函数。

如果输入数组正好呈完全反序(即递降序)，则出现最坏情况。这时，要将每个

与已排序的子数组4LJ—。中的每一个作比较，于是就有&=',法=2,3,…，九。注意

到

7=22

以及

3=2

就可以将INSERTION-SORT在最坏情况下的运行时间表示成

T(n)=cm+C2(n-1)+c4m-1)+二一1)

,n(n-1)..n(n-1).,”、

+C6(9)+C7(、')+C(n-1)

8

—(得+整+-T)72,2+(C1+°2+。4+——怖—停+。8)九一(。2+。4+。5+。8)

N乙乙乙乙乙

此式也可写成an2+历z+c,常量a,b和c依赖于G，即这是八的一个二次函数。

10算法概念

最坏情况和平均情况分析

在分析插入排序时，我们讨论了最佳和最坏情况下的算法性态。在本书后面的章

节中，我们主要是考察最坏情况下的运行时间，即在规模n下的任何输入中的最长运

行时间。做出这种选择的原因如下：

•算法的最坏情况运行时间是在任何输入下的运行时间的上界，这就保证算法的运

行时间不会比它更长。

•对某些算法来说，最坏情况是经常发生的。例如，在搜索一个数据库时，若待搜

索的数据项不在其中，则搜索算法的最坏情况就会发生。

•“平均情况”的时间性态常常与最坏情况下的大致一样。例如，可以随机取

n个数进行插入排序。要找到元素A[j]在子数组A[l..j-1]中的位置要花多少

时间？平均来说，川中的一半元素小于川力，而另一半大于4团，于

是，。=〃2。据此算出平均情况运行时间，其表达式是输入规模的二次函数，与

最坏情况下一致。

在某些特殊情况下，我们感兴趣的是一个算法的平均情况(或期望的)运行时

间。这时存在的问题是，对一个给定的问题，可能不太容易看出来到底什么样的输入

才是一个“平均情况下的输入”。通常，我们假定一个特定规模下的所有输入的“平

均性”都是一样的。在实际中有可能要违反这个假定，但采用随机算法就可以强制这

点成立。

增长的量级

为了简化对INSERTION-SORT过程的分析，我们做了某些简化抽象。首先，我们忽

略了每条语句的真实代价，而用常量G来表示。其次，还可以更加简单，最坏情况运

行时间是a/+配+c，a,匕和c是依赖于q的常量。这样，我们就不仅忽略了真实代

价，也忽略了抽象代价

现在再做进一步的简化抽象，即只考虑运行时间的增长率(rateofgrowth),或称

增长量级(orderofgrowth)。这样，我们就只考虑公式中的最高次项(例如，an2),

因为当冗很大时低阶项相对来说不太重要。另外，还忽略最高次项的常数系数，因为

在考虑较大规模输入下的计算效率时，相对于增长率来说，系数是次要的。例如，插

1.3算法设计11

入排序的最坏情况时间代价的阶为。（宗）。本章中我们先非正式地用这种。表示，在

下一章中要给出它的准确定义。

如果一个算法的最坏情况运行时间的阶要比另外一个算法的低，我们就常常认为

它更为有效。在输入的规模较小时，这种看法有时可能不对，但对足够大规模的输入

来说，一个具有阶e（n2）的算法在最坏情况下比阶为e（n3）的算法运行得更快。

习题

1.2.1考虑对数组月中的n个数的排序，开始时先找出4中的最小元素并放在另一个

数组B的第一个位置上。然后找出月中次最小元素并放在B的第二个位置上。对4中

余下来的元素继续这个过程，这个算法称为选择排序，请写出其伪代码，并以。形式

写出其最佳和最坏情况下的运行时间。

L2.2考虑线性查找问题。假设要查找的元素可能落在数组中，则平均要查找多少个元

素？最坏情况下呢？以。形式表示又怎样？

1.2.3考虑判断一个任意序列（叫声2,...4附中是否存在重复元素的问题。请证明这可

以在e）（Mgrz）时间内完成。

1.2.4考虑在某个点上对一个多项式求值的问题。给定几个系数的,电,...，.吁1和实数

的要求请给出解决这个问题且具有6（足）时间代价的算法。另外请给出

,个使用以下Horner方案的具有0（n）时间代价的算法：

n—1

Q也，=（...（an-iX+。九一？）/+•••++Qo

i=0

1.2.5用e形式表示函数沱3/1000-100n2-lOOn+3。

1.2.6怎样修改任给的一个算法才能使其具有好的最佳情况运行时间？

§1.3算法设计

算法设计有很多方法。插入排序使用的是增量（incremental）方法：在排好子数组

川后,将元素4团插入,形成排好序的子数组川1.J］。

12算法概念

在本节中，我们要介绍另一种设计策略，叫做"分治法"（divideandconquer）。

下面要用分治法来设计一个排序算法，使其性能比插入排序好得多。学了第四章就可

知道，分治算法的优点之一是可以利用在第四章中介绍的技术容易地确定其运行时

间。

分治法

有很多算法在结构上是递归的：为了解决一个给定问题，算法要一次或多次地调

用其自身来解决相关的子问题。这些算法通常采用分治策略：将原问题分解为n个规

模较小而结构与原问题相似的子问题；递归地解这些子问题，然后合并其结果就得到

原问题的解。

分治模式在每一层递归上都有三个步骤：

分解将原问题分解成一系列子问题；

解决递归地解各子问题。若子问题足够小，则直接求解；

合并将子问题的解合并成原问题的解；

合并排序算法完全依照了上述模式：

分解将n个元素分成各含八/2个元素的子序列；

解决用合并排序法对两个子序列递归地排序；

合并合并两个已排序的子序列以得到排序结果。

在对子序列排序时，当其长度为1时递归结束。单个元素被视为是已排好序的。

合并排序的关键步骤在于合并步骤中的合并两个己排序子序列。为做合并，引入

一个辅助过程MERGE（A,p,q,r）,其中4是个数组，和7,是下标，满足pSqSr。

该过程假设子数组A\p..q］和A［q+l..r］都已排好序，并将它们合并成一个排好序的子

数组力日习。

我们把该算法的伪代码留作习题（习题132）。容易想像出MERGE过程的时间

代价为。⑺），其中n=r-p+l是待排序的元素个数。这个过程如果用玩扑克牌来比

喻，就可以看作桌上有两堆牌，每堆都是排好序的，最小的牌在最上面。我们希望把

这两堆牌合并成排好序的一堆加以输出；基本步骤包括选取面朝上的两堆牌的顶上两

张中较小的一张，将它取出面朝下地放到输出堆中。重复这个步骤，直到某一输入堆

1.3算法设计13

图1.2:插入排序算法的工作过程

为空。这时把另一输入堆中余下的牌面朝下放入输出堆中即可。从计算的角度来看，

每一个基本步骤所花时间是个常量，因为我们只是查看并比较顶上的两张牌。又因为

至多进行几次比较，所以合并排序的时间为€(5)。

现在就可以把MERGE过程作为合并排序中的一个子程序来用了。下面的过程

MERGE-SORT(A.p,r)对子数组A[p..r]进行排序。若p2r,该子数组中至多具有一个

元素，当然就是已排序的。否则，分解步骤就计算出一个下标q,将川p..r]分成4p..q]

和A[q+l..r],各含\n/i\和\n/2\个元素。

MERGE-SORT(4.p,r)

1ifp<r

2thenq—(p+r)/2

3MERGE-SORT(A,p,q)

4MERGE-SORT(A,<7+l,r)

5MERGE(4,P,g.r)

为了对整个序列A=(A[l],A\2],...,A[n])进行排序，需要调用MERGE-SORT

(A,l,length[A]),其中Zeng历园=n。假设沱是2的基，如果我们自底向上来看这个过

程的操作，算法将两个长度为1的序列合并成排好序的长度为2的序列，继而合并成长

14算法概念

度为4的序列，一直进行到将两个长度为n/2的序列合并成最终排好序的长度为n的序

列。图1.2说明了对数组4=(5,2,4；6,1,3,2,6)进行合并排序的过程，不难看出，随

着算法自底向上地执行，被合并的排序序列的长度逐渐增加。

分治算法的分析

当一个算法中含有对其自身的递归调用时，其运行时间可用一个递归方程(或递

归式)来表述，该方程通过描述子问题与原问题的关系来给出总的运行时间。我们可

以利用数学工具来解决递归式并给出算法运行时间的上界。

分治算法中的递归式是基于基本模式中的三个步骤的。设了⑺)为该算法对于规模

为n的输入的运行时间。如果八足够小，例如有nSc,c•为常量，则直接得到T(R的

解，也是一个常量，写作9(1)。假设我们把原问题分成。个子问题，每个子问题的大

小是原问题的1/6。若分解该问题和合并解的时间各为。⑺)和。⑺)，则得递归式

T()=[。⑴若nSc

3,一[aT(n/b)+D(n)+C(n)否则

在第四章中，将介绍如何消除这类递归。

合并排序算法的分析

虽然MERGE-SORT的伪代码在元素为奇数个时也能够正确地工作，但此处我们为

了简化对基于递归的算法的分析，就假定原问题的规模是2的幕次，这样每一次分解所

产生的子序列的长度恰为n/2。在第四章中，我们会看到这个假设不影响递归式解的

阶。

以下给出递归形式的丁⑺)，即最坏情况下对n个数进行合并排序所需的运行时

间。合并排序一个元素的时间是个常量。当m>1时，将运行时间如下分解：

分解这一步仅仅是计算出子数组的中间位置，需要常量时间，因而。(刈=。(1)；

解决递归地解两个规模为"/2的子问题，时间为2T5/2)；

合并已知MERGE过程在一个含有n个元素的子数组上的运行时间为。缶)，则

C(n)=0(n)o

函数。⑻和。⑻的阶为e(m和。⑴，它们的和是几的线性函数,即阶为9(九)。

1.4小结15

将它与“解决”步骤中所得的项2TS/2)相加，即得了⑺)的递归表示：

⑴若"1

、[2T(n/2)+@H若n>1

在第四章中,我们将证明丁⑹的阶是0(711g此处1gh代表10g2(M。当输入规

模足够大时，合并排序(运行时间为egign))要比最坏情况下的插入排序(运行时

间为0(n2))好。

习题

1.3.1以图1.2为模型,说明合并排序在输入数组力=(3,41,52,26,38.57,9,49)上的执

行过程。

1.3.2请写出MERGE(A,p,q,r)的伪代码。

1.3.3插入排序可以改写成如下的递归过程。为排序力[1.同，先递归排序川1..72-1],

然后将川可插入已排好序的/l[l..n-l]o写出表示该递归过程运行时间的递归式。

1.3.4回顾习题1.1.3中的查找问题，注意到如果月是已排序的，则我们可以把。与中

点进行比较。从而可以不必对输入数中的一半作进一步的考虑。重复下去就构成了二

分查找，写出其伪代码，并请证明其最坏情况运行时间为。(Ign)。

1.3.5在INSERTIONSORT中，第5-7行的while循环中使用了线性查找法来搜索已排

序的子数组-1]0能否通过使用二分查找将该算法的最坏情况运行时间改善至

1.3.6请给出一个运行时间为O(nlgn)的算法，使之能在给定一个由n个实数构成的

集合S和另一个实数4时，判断出S中是否存在两个数的和等于X。

§1.4小结

为解决同一个问题而设计的各种算法在效率上会有很大差异。这些差异可能比个

人微型计算机与巨型计算机之间的差异还要大。例如，让一台巨型机做插入排序，让

另一台微型机做合并排序，它们的输入都是一个长度为100万的数组。假设巨型机每秒

执行I亿条指令，微型机每秒仅执行100万条指令。为了使差别更明显，假设世界上最

16算法概念

优秀的程序员用机器代码在巨型机上实现插入排序，编出的程序需要执行2n2条巨型机

指令来排序八个数。另一方面，让一个一般的程序员在微型机上用高级语言写合并排

序，产生的代码要花50"lg/z条微型机指令。为排序100万个数，巨型机需费时间：

2X(明2条指令

=20000秒«5.56小时

108条指令/秒

微型机需费时间:

50x(106)x馆1。6条指令

=1000秒、16.67分钟

106条指令/秒

由此可以看出，由于采用了更低阶的算法，即使是用低效的编译器，微型机还是

要比巨型机快20倍！

这个例子说明了算法设计像设计计算机硬件一样也是一种技术。整个系统的性能

的提高既要依赖于快速的硬件，也要依赖于高效的算法。目前，正如其他计算机技术

一样，算法的研究也在不断地取得进展。

习题

1.4.1假设我们在同一台机器上来比较插入排序与合并排序的实现。若输入规模为必

前者要做8/步，后者要做647Hg72步。对哪些72值来说插入排序优于合并排序？在输

入的规摸较小时，如何重写合并排序的伪代码使之运行得较快？

1.4.2设有两个在同一台机器上实现的算法，运行时间分别为100/和2”，使前者优

于后者，最小可能的门值是多少？

思考题

1.1运行时间的比较

对于下表中的每个函数/(»)和时间t,设解决一个问题的算法需要执行/⑺)微

秒，请确定在时间方内所能解决的问题的最大规模仅

1.4小结17

1秒1分钟1小时1天1个月1年1世纪

1gn

y/n

n

nlgn

n2

n3

2n

n\

1.2合并排序中插入排序在短数组上的应用

虽然合并排序的最坏情况运行时间为9缶国切，插入排序的为。（公），但在71较小

时，后者更快。因而，在合并排序中，当子问题已足够小时，可以应用插入排序。考

虑对合并排序做一个修改，71〃个长度为人的子表用插入排序来排，然后应用标准的合

并机制。k值待定。

a证明在最坏情况下，泞"个子表（每个长度为卜）用插入排序来排的时间为。⑺切；

b证明在最坏情况下各子表可以在egigg/k））内合并；

c设修改后的合并算法的时间阶为。⑺k+"场⑺〃））。请给出最大的渐近值k（以。

记号表示，k是n的函数），使得修改后的算法有和标准合并算法一样的渐近运行时

间。

dk值在实际中如何确定？

1.3逆序对

设川1..句中的元素各不相同。若，•且川句＞4团，则艮力称为4的一个逆序

对。

a列出数组（2,3,8,6,1）的五个逆序对；

b从集合｛1,2,.../｝中选出一些元素来构成数组，则什么样的数组中的逆序对最

多？共有多少？

c对插入排序来说，其运行时间与输入数组中的逆序对数的关系如何？证明你所得的

结论。

d设计这样一个算法，使之能够在©（nign）的最坏情况时间内确定n个元素的任意一

18算法概念

个排列中的逆序对数。

第二章函数的增长

第一章中定义的算法运行时间的阶较简明地刻画了i个算法的效率，并提出了对

不同的算法进行比较的手段。例如，当输入的规模"足够大时，具有最坏情况运行时

间0（nlgn）的合并排序要优于运行时间为0（n2）的插入排序。虽然我们有时能够很精

确地算出算法的运行时间，但没必要花那么大的力气去算出额外的精确度。对足够大

的输入来说，精确表示的运行时间中的常系数和低阶项是由输入规模决定的。

当输入规摸大到使只和运行时间的增长量级有关时，我们就是在研究算法的渐近

效率了。也就是说，我们只关心从极限的角度来看，运行时间是如何随着输入规模的

无限增长而增长的。通常，从渐近意义上来说更有效的算法对较大规模的输入来说是

最佳的。

本章将介绍儿种标准方法来简化对算法的渐近分析。下一节介绍儿种渐近记号，

其中的。记号我们已经见过了。

§2.1渐近记号

用来表示算法的渐进运行时间的记号是用域为自然数集N={1,2,.一，}的函数来

定义的。这些记号可以很方便地表示最坏情况运行时间丁⑺），因为7（用一•般仅定义于

整数输入规模上。有时将这些记号的使用范围变化一下也是很有益的。例如，这些记

号的应用领域可以很容易地扩充至实数域或缩小到一个受限的自然数集上。但要注意

搞清楚这些表示法的准确含义，方能做到“活用”而不误用。本节介绍几种基本的渐

近记号和一些常见的扩充用法。

0-记号

在第一章中，我们知道插入排序的运行时间为T（/i）=eg2）。现对这种表示的含

20函数的增长

图2.1：e,o和。记号的图例。在每一个子图里，劭是最小可能的值。(a)e(记号

将一个函数限于常数因子内。如果存在正常数成和C1,C2,使得在劭右边，f⑺

之值总是落在qg(?i)与C2g(n)之间,则写作f(n)=9(g(n))；(b)。记号给出了一

个函数在一个常数因子内的上界。如果存在正常数和c,使得在的右边，/(«)

之值总是落在cg(n)之下，则写作/(n)=O(g("))；(c)Q记号给出了一•个函数在一

个常数因子内的下界。如果存在正常数成和c,使得在碗右边，/⑺)之值总是落

在cg(n)之上，则写作f(n)=C(g(n))；

义加以定义。对一个给定的函数g(n),用。(g("))来指示函数集合:

®(g(n))={/⑺:存在正常数4。2,的>0,使得对于每一个?2之八o，

有0WCig(n')<f(n)<c2g(n)}

对于任一个函数/(n),若存在正常数3,。2，使当正充分大时，/⑺)能被夹在

qg(?2)和c2g(㈤之间,则/⑺)属于集合。(g(n))。虽然9(g(n))是个集合,我们仍写

/S)=®(g(n))来表示/⑺)是。(g(n))的元素，这种等式的“活用”，初看起来有点

令人迷惑，但在下面就能看到它具有一些优越性。

图2.1(a)给出了函数/⑺)和g(m的直观图示。其中/(n)=9(gm))。对所有位于

为右边的n值，/(n)值落在cig(")和c2g(")之间。换言之，对所有n2的，/(")在一

个常因子内与g(n)相等。我们说g(n)是/(n)的一个渐近确界。

e)(g(n))的定义要求其每个元素渐近非负，即当n充分大时/⑺)非负。这就要求

函数g(n)本身是渐近非负的。否则，集合e(gS))就是空的。因此，我们假定。记号

中用到的每个函数都是渐近非负的。这个假设对本章中定义的其他渐近记号也成立。

在第一章中，我们引进了非形式的。记号，其效果相当于舍弃了低阶项和最高阶

项的系数。为了说明这一点，下面我们利用形式定义来证明//2-3沱=9(4)。首先

2.1渐近记号21

要确定常数Ci,C2和的，使得对所有的冗2处，有:

用n2除不等式得：

ci’<1----3-<c

2n2

右边的不等式在n21,321/2时成立。同样，左边的不等式在泞之7,ci二1/14时成

立。这样，通过选择q=1/14,。2=1/2及的=7,就能证明？^/2-3九=。（公）。当

然，还存在其它的一些常数选择，这些常数依赖于函数//2-3%对于集合。（必）中

的每一个不同的函数有不同的常数ci,02,刖。

我们还可以利用形式定义来证明6疗3#。缶2）。为引出矛盾，设存在常数C2和加，

使对所有的n之冗0有6n：3Sc2n2,这样就有冗SC2/6，这在"足够大时并不成立，因

为C2是个常数。

从直觉上看，一个渐近正函数中的低阶项在决定渐近确界时可被略去。因为当冷

很大时，它们就相对地不重要了。最高阶项很小的一部分就足以支配所有的低阶项。

因而，若将C+1置成略小于最高阶项系数的值，而将C2置成略大于的值，就可满

足。记号定义式中的不等式。同样，最高阶项的系数也可忽略，因为它只是将q和。2

改变了（等于该系数的）常因子倍。

例如，考虑二次函数/⑺）=丽2+版+c,其中和c为常数，且a>。。

舍