第1章 算法的基本概念

1.1 算法的基本概念

首先，要明白软件 = 程序+文档 = 数据结构+算法+文档（图1-1），算法 = 数据对象运算和操作 + 控制结构。算法(Algorithm)的概念在计算机科学领域中几乎无处不在，在各种计算机系统的实现中，算法的设计往往处于核心的位置。计算机的问世是20世纪算法是计算机科学的重要基础，就像算盘一样，人们需要为计算机编制各种各样的“口诀”即算法，才能使其工作。

1-1计算机软件和算法的关系

1.1.1 算法的特征

虽然每天都在和算法打交道，但是能严格地指出什么是算法却不是一件容易的事。算法即在有限步骤内解一个数学问题的过程步骤中常常包括某一操作的重复。更广义地说，一个算法就是解一个问题或实现某一目村的逐步过程。一个算法，就是一个有穷规则的集合，规定了一个解决某特定类型问题的运算序列，此外还应具有如下 5 个重要特性。

1.输入性

一个算法要具有0个或多个外部量作为算法的输入，这些外部量通常体现为算法中的组变量，有些输入量需要在算法执行过程中输入。从表面上看，有些算法好像没有输入量实际上是输入量已被嵌入算法之中。

2.输出性

一个算法必须具有一个或多个输出，以反映算法对输入数据加工后的结果，没有输出的算法是毫无意义的。

3.确定性

算法的每一个步骤必须具有确定的定义，即每一步要执行的动作是确定的，是无二义性的。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入得出的输出结果也是相同的。

4.有穷性

对于任何合法的输入值，算法必须在执行有限个步骤之后结束，并且每一步都可以在有限的时间内完成。

5.可行性

算法中描述的操作都可以通过已经实现的基本运算的有限次执行来实现，即算法的具体实现应该能够被计算机执行。

1.1.2 算法的4个标准

计算学科则把问题作为自己的研究对象，用计算机来解决问题。在计算机专家的头脑中，世界是一个个要解决的问题集合。假如如下分段函数，要求对用户输入的一个自变量 x 的值，给出相应的函数值。

实现分段函数求值功能的过程可以作以下描述。

Ø 输入自变量x的值。

Ø 依据自变量 x 的值进行判断:

如果x>0，执行 x+4=f(x)操作;

如果x<0，执行 x-4=f(x)操作;

如果x=0，执行 4=f(x)操作。

其中，A=>B 表示将表达式 A 的值赋给变量 B。

Ø 输出步骤@计算的结果。

显然，上述描述满足算法的 5 个重要特征，因此，该描述就是一个算法。在现实社会中,不同的人对于同一问题会有不同的看法或解决方法。同样，在计算机领域，对于同一问题可能存在多种算法也是很自然的事情。例如，对于一批数据的排序问题，就存在多种排序方法判断一个算法的好坏主要依据以下 4 个标准。

1.正确性

正确性是设计一个算法的首要条件，如果一个算法不正确，其他方面就无从谈起。一个正确的算法是指在合理的数据输入下，能在有限的时间内得出正确的结果。

2.可读性

算法主要是为了人的阅读与交流，其次才是让计算机执行，因此算法应该易于人的理解;另外，晦涩难读的算法易于隐藏较多错误而使实现该算法的程序的调试工作变得更加困难。

3.健壮性

算法应当具备检查错误和对错误进行适当处理的能力。一般而言，处理错误的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

4.效率

效率是指算法执行时所需计算机资源的多少，包括运行时间和存储空间两方面的要求。运行时间和存储空间都与问题的规模有关。存储空间指的是算法执行过程中所需的最大存储空间。

在设计一个算法时，要从上述 4 个方面综合考虑。同时还要考虑到算法的使用频率及所使用机器的软硬件环境等因素，这样才能设计出一个好的算法。

1.1.3 算法的描述形式

算法的描述形式多种多样，不同的算法描述形式对算法的质量有一定的影响。描述同一个算法可以采用自然语言，流程图，盒图，伪代码，序设计语言等，常用的描述算法方法有如下4种。

1.自然语言描述法

最简单的描述算法的方法是使用自然语言，用自然语言来描述算法的优点是简单且便于人们对算法的理解和阅读，缺点是不够严谨，易产生歧义，当算法比较复杂且包含很多转移分支时，用自然语言描述就不是那么直观清晰了。

2.算法框图法

使用程序流程图、盒图等算法描述工具来描述算法。其特点是简洁)(明了,(便于理解和

交流。

3.伪码语言描述法

用上述两种方法描述的算法并不能够直接在计算机上执行。为了解决理解与执行之间的矛盾，人们常常使用一种称为伪码语言的描述方法来对算法进行描述。伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言或算法框图更接近程序设计语言。

4.高级程序设计语言描述法

使用特定的可以直接在计算机上执行的程序描述算法。优点是不用转换直接可以编译执

行，缺点是需要对特定的程序设计语言比较理解。大部分的算法最终是需要通过能够向计算机发送一系列命令的程序来实现的。所谓“程序”是指对所要解决问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说“数据结构+算法-程序”

程序与算法不同。

程序可以不满足算法的第 4 个特性，例如，操作系统，它是在无限循环中执行的程序，因而不是算法。然而可以把操作系统的各种任务看作一些单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法实现，该子程序得到输出结果后便终止。

算法设计方法主要有分治策略、动态规划、贪心算法、回溯法、分支限界、概率算法等这些将在后面的章节中陆续介绍，并采用 C++ 语言来描述算法。C++ 语言的优点是类型丰富语句精练，具有面向对象和面向过程的双重优点，用 C++ 来描述算法可使整个算法结构紧凑，可读性强。

1.2 算法复杂性分析框架

算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性,需要空间资源的量称为空间复杂性，算法复杂性的度量主要是针对运行该算法所需要的计算机资源的多少。当算法所需要的资源越多，该算法的复杂性越高。反之，当算法所需要的资源越少，算法的复杂性越低。

算法的时间效率和空间效率都用输入规模的函数进行度量。对于所有的算法，规模更大的输入都需要运行更长的时间。经常使用一个输入规模参数为 n 的函数来研究算法的效率。选择输入规模的合适量度，要受到所讨论算法的操作细节影响。

1.2.1 时间复杂度

通常，对于一个算法的复杂性分析主要是对算法效率的分析，包括衡量其运行速度的时间效率，以及其运行时所需要店用的空间大小。对于算法的时间效率的计算，通常是抛开与计算机硬件、软件有关的因素，仅考虑实现该算法的高级语言程序。

一般而言，对程序执行的时间复杂度的分析是以分块进行的，先分析程序中的语句，再分析各程序段，最后分析整个程序的执行复杂度，通常以渐进式的 O 形式来表示算法的时间复杂度。

渐进式的 O 形式表示时间复杂度的主要运算规则有如下两种。

(1)求和规则

O(f(n))+ O(g(n))= O(max(f(n),g(n)))，其中，f(n)和 g(n)表示与n 有关的一个函数。

(2) 乘法规则

O(f(n))* O(g(n))= O(f(n)*g(n))，O(c*f(n))= O(f(n))，c 是一个正常数。

假设 T(n)是问题规模n(n 为整型数) 的函数，算法的时间复杂度可以定义为 O(f(n)),记作 T(n)=O(f(n))。由于随着问题规模n的增长,算法执行时间的增长增长率和f(n)的增长率相同。因此，T(n)也被称为算法的时间复杂度。

为了便于比较同一问题的还同算法的效率问题，通常的做法是从算法中选取一种对于所研究问题来说是基本运算的原子操作，以该基本操作重复执行的次数作为算法的时间度量单位。例如，对于如下的两个 NXN 矩阵相乘算法

for (i=0;i

{

for(j=0;j

{

c[i][j] = 0;

for(k=0;k

{

c[i]j]=c[i][j] + a[il[k] * b[k][j];

}

}

}

第1个i 作为循环变量的 for 语的循环体执行次数为n；第 2个j作为循环变量 for 语句的循环体执行次数为 n*n; 语c[i][j] = 0；的执行次数是

；第 3个 k 为循环变量的 for语句的循环体执行次数为

*n; 语c[i]j]=c[i][j] + a[il[k] * b[k][j]；的执行次数是

。除去 for循环自身的判断语句执行次数以外(计算算法时间复杂度时，可以忽略不计) ，该算法的循环体执行总次数为:

T(n)=n+n*n+

+

*n+

=2

+2

+n

如果根据渐进式O规则，则该算法的时间复杂度为 O(n3)。力

在某些情况下，算法所包含的基本操作重复执行的次数会随着问题的输入数据集不同而不同。例如，下面所示的冒泡排序算法的时间复杂度会随着变量 n 的取值不同而不同。

void bubble sort(int a[])

{ i=0;

do {

change=false;

for(j=0;j

{

if (a[j]> a[j+1] )

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

change=true;

}

}

i++;

} while (i< n && change);

}

一般情况下，当讨论时间复杂度时均指最坏情况下的时间复杂度，且时间复杂度考虑只是对于问题规模 n 的增长率，此时，只需计算出它关于 n 的增长率或阶即可。如上面所的冒泡排序算法时间复杂度为 T(n)=O(n(n-1)/2)=O(

)。

小规模输入在运行时间上的差别不足以将高效的算法和低效的算法区分开来，当输入规模增大时，算法的效率就体现出来。

对于给定算法的实现即程序的时间复杂度的分析主要考虑可执行语句的情况，下面是对于程序进行时间复杂度分析的一些基本规则。

Ø 对于简单的输入、输出及赋值语句，执行时间为 O(1)。

Ø 对于顺序结构，需要执行一系列语句所用时间可采用渐进式O的求和规则来进行计

算。

Ø 对于选择结构，它的时间复杂度主要体现在对条件判断后所执行的语句上。如判断语句 if(c) {sl;} else{s2;}，判断语句所需要的执行时间为O(1)，执行语句所需要的执行时间为

O(max(T(s1),T(s2)))

Ø 对于循环结构，它的时间复杂度主要体现在循环体语句和循环条件判断语句上，可以

利用渐进式O的乘积规则来进行计算。

Ø 对于复杂的算法，可以将它分割成几个容易估算的部分，然后利用渐进式 O 的求和规则与乘法规则计算整个算法的时间复杂度。

需要指出的是，顺序结构、选择结构和循环结构是算法的三种基本结构。在进行算法的时间复杂度分析时，重点是对这三种结构的语句进行分析。

1.2.2 空间复杂度

一般情况下，一个算法所占用的存储空间包括算法自身、算法的输入、算法的输出及实现算法的程序在运行时所占用空间的总和。

由于算法的输入和输出所占用的空间基本上是一个确定的值，它们不会随着算法的不同而不同。而算法自身所占用的空间与实现算法的语言和所使用的语句密切相关，如程序越短它所占用的空间就越少。一个算法在运行过程中所占用的空间，特别是算法临时开辟的存储空间单元则是由算法策略及该算法所处理的数据量决定的。因此，对于一个算法的空间复杂度的衡量主要考虑的是算法在运行过程中所需要的存储空间的大小。

假设 S(n)是问题规模 n(n 为整数)的函数，可以定义算法的空间复杂度为 O(f(n))，记作 S(n)=O(f(n))，与时间复杂度T(n)一样，S(n)也被称为算法的空间复杂度。如上述冒泡排序算法中，其空间复杂度为 S(n)=O(n)。除非特别说明，空间复杂度也是以最坏情况来分析的。