1.1 算法

本节从算法的基本概念展开，阐述算法的基本特征、基本要素、设计方法以及设计准则，进而详细讲解算法的时间复杂度和空间复杂度。

1.1.1 什么是算法

1 算法的定义

学习提示

【熟记】 算法的定义及2个基本要素

【理解】 算法的4个基本特征和6种基本设计方法

有的学者认为，算法是程序的灵魂。实际上，对于算法的研究已经有数千年的历史了。计算机的出现，使得用机器自动解题的梦想成为现实，人们可以将算法编写成程序交给计算机执行，使许多原来认为不可能完成的算法变得实际可行。

值得注意的是，算法不等于数学上的计算方法，也不等于程序。在用计算机解决实际问题时，往往先设计算法，用某种表达方式（如流程图）描述，然后，再用具体的程序设计语言描述此算法（即编程）。在编程时由于要受到计算机系统运行环境的限制，因此，程序的编制通常不可能优于算法的设计。

2 算法的基本特征

（1）可行性

算法在特定的执行环境中执行应当能够得出满意的结果，即必须有一个或多个输出。一个算法，即使在数学理论上是正确的，但如果在实际的计算工具上不能执行，则该算法也是不具有可行性的。

例如，在进行数值计算时，如果某计算工具具有7 位有效数字（如程序设计语言中的单精度运算），则在计算下列3个量的和时：

A=1012，B=1，C=-1012

如果采用不同的运算顺序，就会得到不同的结果，例如：

A+B+C=1012 +1+（-1012）=0

A+C+B=1012+（-1012）+1=1

而在数学上，A+B+C与A+C+B是完全等价的。因此，算法与计算公式是有差别的。在设计一个算法时，必须考虑它的可行性。

（2）确定性

算法的确定性表现在对算法中每一步的描述都是明确的，没有多义性，只要输入相同，初始状态相同，则无论执行多少遍，所得的结果都应该相同。如果算法的某个步骤有多义性，则该算法将无法执行。

例如，在进行汉字读音辨认时，汉字“解”在“解放”中读作 jiě，但它作为姓氏时却读作xiè，这就是多义性，如果算法中存在多义性，计算机将无法正确地执行。

（3）有穷性

算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。这包括合理的执行时间的含义，如果一个算法执行时耗费的时间太长，即使最终得出了正确结果，也是没有意义的。

例如，数学中的无穷级数，当n趋向于无穷大时，求2n×n！。显然，这是无终止的计算，这样的算法是没有意义的。

（4）拥有足够的情报

一般来说，算法在拥有足够的输入信息和初始化信息时，才是有效的；当提供的情报不够时，算法可能无效。

例如，A=3，B=5，求A+B+C的值。显然，由于对 C没有进行初始化，无法计算出正确的答案。所以，算法在拥有足够的输入信息和初始化信息时，才是有效的。

在特殊情况下，算法也可以没有输入。因此，一个算法有0个或多个输入。

总之，算法是一个动态的概念，是指一组严谨地定义运算顺序或操作步骤的规则，并且，每一个规则都是有效的、明确的，此顺序将在有限的次数内终止。

3 算法的基本要素

算法的功能取决于两方面因素：选用的操作和各个操作之间的顺序。因此，一个算法通常由两种基本要素组成：

●对数据对象的运算和操作；

●算法的控制结构，即运算或操作间的顺序。

（1）算法中对数据对象的运算和操作

前面介绍了算法的一般定义和基本特征。实际上本书讨论的算法，主要是指计算机算法。在计算机上，可以直接执行的基本操作通常都是用指令来描述的，每个指令代表一种或几种操作。

指令系统是软件与硬件分界的一个主要标志，是软件与硬件之间相互沟通的桥梁。指令系统在计算机系统中的地位如图1-1所示。

算法就是按解题要求从指令系统中选择合适的指令组成的指令序列。因此，计算机算法就是计算机能执行的操作所组成的指令序列。不同的计算机系统，指令系统是有差异的，但一般的计算机系统中，都包括以下4类基本的运算和操作，如表1-1所示。

（2）算法的控制结构

算法的控制结构是算法中各个操作之间的执行顺序。

算法一般是由顺序、选择（又称分支）和循环（又称重复）3 种基本结构组合而成。

描述算法的工具有传统的流程图、N-S结构化流程图和算法描述语言等。

图1-2所示为以流程图方式表示的选择结构的两种类型。

在图1-2（a）中，算法的执行步骤如下。

X赋值为2。

判断 X的值是否小于3，条件成立。

X的值减少2。

输出X的值，最后结果为0。

在图1-2（b）中，算法的执行步骤如下。

X赋值为2。

X的值增加2。

判断X的值是否小于3，条件不成立。

输出X的值，最后结果为4。

图1-2（a）执行的是先判断X的值是否小于3，如果条件成立则X的值减2，最终结果为0，而图1-2（b）先将X的值增加2，然后再判断 X的值是否小于3，最终结果为4。

从中可以看出，选用的基本操作虽然相同，但由于存在执行顺序的差异，得到的结果完全不同。

4 算法基本设计方法

虽然设计算法是一件非常困难的工作，但是算法设计也不是无章可循的，人们经过实践，总结和积累了许多行之有效的方法。常用的算法设计方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法6种。

1.1.2 算法复杂度

学习提示

【熟记】 算法的时间复杂度和空间复杂度的概念及度量

一个算法复杂度的高低体现在运行该算法所需要的计算机资源的多少，所需的资源越多，就说明该算法的复杂度越高；反之，所需的资源越少，则该算法的复杂度越低。计算机的资源，最重要的是时间和空间（即存储器）资源。

因此，算法复杂度包括算法的时间复杂度和算法的空间复杂度。

1 算法的时间复杂度

值得注意的是：算法程序执行的具体时间和算法的时间复杂度并不是一致的。算法程序执行的具体时间受到所使用的计算机、程序设计语言以及算法实现过程中的许多细节的影响。而算法的时间复杂度与这些因素无关。

算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法所执行的基本运算次数是问题规模（通常用整数n表示）的函数，即

算法的工作量=f（n）

其中n为问题规模。

所谓问题规模就是问题的计算量的大小。如1+2，这是规模比较小的问题，但1+2+3+…+10000，这就是规模比较大的问题。

例如，在下列3个程序段中：

①｛x+ +；S=0｝

②for（i=1；i﹤=n；i+ +）

｛x+ +；S+ =x；｝ /＊ 一个简单的for循环，循环体内的操作执行了n次＊ /

③for（i=1；i﹤=n；i+ +）

for（j=1；j﹤=n；j+ +）

｛x+ +；S+ =x；｝ /＊ 嵌套的双层for循环，循环体内的操作执行了n2 次＊ /

程序段①中，基本运算“x++”只执行一次。重复执行次数分别为1；

程序段②中，由于有一个循环，所以基本运算“x++”执行了n次；

程序段③中，嵌套的双层循环，所以基本运算“x++”执行了n2 次。

则这3个程序段的时间复杂度分别为O（1）、O（n）和O（n2）。

在具体分析一个算法的工作量时，在同一个问题规模下，算法所执行的基本运算次数还可能与特定的输入有关。即输入不同时，算法所执行的基本运算次数不同。例如，使用简单插入排序算法（见本书1.8节），对输入序列进行从小到大排序。输入序列为：

我们不难看出，序列a所需的计算工作量最少，因为它已经是非递减顺序排列，而序列c将耗费的基本运算次数最多，因为它完全是递减顺序排列的。

在这种情况下，可以用以下两种方法来分析算法的工作量：

●平均性态；

●最坏情况复杂性。

2 算法的空间复杂度

算法执行期间所需的存储空间包括3个部分：

●输入数据所占的存储空间；

●程序本身所占的存储空间；

●算法执行过程中所需要的额外空间。

其中，额外空间包括算法程序执行过程中的工作单元，以及某种数据结构所需要的附加存储空间。

如果额外空间量相对于问题规模（即输入数据所占的存储空间）来说是常数，即额外空间量不随问题规模的变化而变化，则称该算法是原地（in place）工作的。

为了降低算法的空间复杂度，主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术。

真题演练

【例1】 下列叙述中正确的是（ ）。

（A）算法就是程序

（B）设计算法时只需要考虑数据结构的设计

（C）设计算法时只需要考虑结果的可靠性

（D）以上3种说法都不对

【解析】 本题考查的是对算法定义的理解。算法是指对解题方案准确而完整的描述，算法不等于程序，也不等于计算方法，所以A选项错误。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构，所以B、C选项错误。

【答案】 D

【例2】 算法的有穷性是指（ ）。

（A）算法程序的运行时间是有限的

（B）算法程序所处理的数据量是有限的

（C）算法程序的长度是有限的

（D）算法只能被有限的用户使用

【解析】 本题考查的是对算法有穷性的理解。算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。有穷性是指算法程序的运行时间是有限的，即这里的有穷指的是运行时间，而不是算法处理的数据量和算法长度，也不是算法的用户，所以B、C、D选项错误。

【答案】 A

【例3】 下列叙述中错误的是（ ）。

（A）算法的时间复杂度与算法所处理数据的存储结构有直接关系

（B）算法的空间复杂度与算法所处理数据的存储结构有直接关系

（C）算法的时间复杂度与空间复杂度有直接关系

（D）算法的时间复杂度与算法程序执行的具体时间是不一致的

【解析】 本题考查的是对算法的时间复杂度和空间复杂度的理解。算法的时间复杂度是指执行算法所需要的计算工作量。数据的存储结构直接决定数据的输入，而这会影响算法所执行的基本运算次数，A选项叙述正确。算法的空间复杂度是指执行这个算法所需要的内存空间，其中包括输入数据所占的存储空间，B选项叙述正确。而算法的时间复杂度与空间复杂度没有直接关系，故选择C选项。算法程序执行的具体时间受到所使用的计算机、程序设计语言以及算法实现过程中的许多细节的影响，而算法的时间复杂度与这些因素无关，所以是不一致的，D选项叙述正确。

【答案】 C