算法基础（第5版）——1.1　算法

本书讨论用计算机解决问题的方法。这里所说的“方法”并不是指一种程序设计风格或者一种程序设计语言，而是用于解决问题的方法或方法学。例如，假设Barney Beagle希望在电话簿中找到名字“Collie, Colleen”。一种方法是从第一个名字开始，依次查看每个名字，直到找出“Collie, Colleen”为止。但是，没有人会这样来找一个名字。电话簿中的名字都是有序的，所以Barney会利用这一事实，将电话簿翻到他认为C字头名字所在的位置。如果他翻过了，可以往回翻一些。他不停地前后翻动，直到找出“Collie, Colleen”所在的页面。你可能看出来了，第二种方法就是一种经过修改的二分查找，而第一种方法是一种顺序查找。1.2节会进一步讨论这两种查找方法。这里要说的是，这一问题有两种不同的解决方法，而这两种方法与程序设计语言或风格没有任何关系。计算机程序只不过是实现这些方法的一种途径。 第2章至第6章讨论各种解决问题的方法，并运用这些方法解决各种问题。将某一方法应用于某一问题，会得到解决该问题的一个逐步过程。这个逐步过程称为该问题的算法（algorithm）。研究这些方法及其应用的目的就是掌握许多方法，以便在遇到新问题时，可以从中找出解决该问题的方法。后面经常会看到，可以使用几种不同的方法来解决同一问题，但其中一种方法得出的算法要远快于其他方法得出的算法。在电话簿中查找姓名时，经过修改的二分查找法当然要快于顺序查找法。因此，我们不仅要判断某个问题能否用某一给定方法解决，还要分析所得到的算法在时间和存储方面的效率如何。当在计算机上实现算法时，时间是指CPU周期，存储是指内存。你可能会感到奇怪，计算机变得越来越快，内存变得越来越便宜，为什么还需要考虑效率。本章将讨论一些基本概念，它们是理解本书内容所必需的。在此过程中我会向你说明，为什么无论计算机变得多快、内存变得多便宜，还是要考虑效率。 1.1　算法 到目前为止，我们已经提到了“问题”“答案”和“算法”等词。我们大多数人都能很好地理解这些词语的含义。但为了打下一个坚实的基础，还是再具体定义一下这些术语。 计算机程序由完成特定任务（比如排序）的各个模块组成，计算机是可以理解这些模块的。本书关注的不是整个程序的设计，而是这些完成特定任务的各个模块的设计。这些特定的任务称为“问题”。明确地说，问题（problem）就是要为其寻求答案的疑问。下面给出问题的一些例子。 例1.1　将一个包含n个数字的列表S按非递减顺序排序。其答案就是这些数字排序后的结果。 这里所说的列表（list）是指一组按特定顺序排列的项目。例如， S = [10, 7, 11, 5, 13, 8] 是一个包含六个数字的列表，其中第一个数字为10，第二个为7，等等。例1.1中说到要按“非递减顺序”对这个列表排序，而不是按升序排列，这样就存在同一数字在列表中出现多次的可能性。 例1.2　判断数字x是否在一个包含n个数字的列表S中。如果x在S中，则答案为“是”，否则为“否”。 一个问题可能会在问题描述中包含一些未指定取值的变量。这些变量称为问题的参数（parameter）。例1.1中有两个参数：S（列表）和n（S中项目的个数）。例1.2中有三个参数：S、n和数字x。在这两个例子中，并不需要让n成为一个参数，因为它的值由S唯一确定。但是，让n成为参数有利于问题的描述。 因为问题中包含参数，所以它代表着一类问题，每对参数进行一次赋值，就得到其中一个问题。对参数的每次特定赋值就称为该问题的一个实例（instance）。一个问题实例的答案（solution）就是该实例中所提问题的回答。 例1.3　例1.1所提问题的一个实例为： S = [10, 7, 11, 5, 13, 8]，n = 6 这一实例的答案为[5, 7, 8, 10, 11, 13]。 例1.4　例1.2所提问题的一个实例为： S = [10, 7, 11, 5, 13, 8]，n = 6，x = 5 这一实例的答案为：“是，x在S中。” 对于例1.3中的实例，只需审视S，用一种无法具体描述的认知步骤在大脑中生成有序序列，就能给出该实例的答案。之所以能这样做，是因为S非常小，在人类的意识水平，大脑可以快速扫描S，几乎马上就可以给出答案（因此，我们无法描述大脑用于获得此答案的具体步骤）。但是，如果这个例子中的n值为1000，那人们就无法使用这一方法，当然也就不可能将这样一种数字排序方法转换为计算机程序。为了给出能够解答某一问题所有实例的计算机程序，我们必须给出一个通用的逐步过程，用于给出每个实例的答案。这一逐步过程称为算法。我们说算法解决了问题。 例1.5 例1.2所示问题的一种算法。从S中的第一项开始，依次将x与S中的每一项对比，直到找出x或S中的项目耗尽为止。如果找到了x，则答案为“是”；如果没有找到x，则答案为“否”。 任何算法都可以像例1.5中那样用日常语言来描述。但是，以这种方式来书写算法有两个缺点。第一，这样很难书写复杂算法，即使勉强写出，人们也很难理解。第二，根据算法的日常语言描述，无法清晰地知道如何生成对该算法的计算机语言描述。 因为C++是当前学生比较熟悉的一门语言，所以我们使用一种类似于C++的伪代码来书写算法。只要拥有类Algol命令式语言（比如C、Pascal或Java）的编程经验，应当不难看懂这种伪代码。 为演示该伪代码，我们以一种算法以例，该算法可以解决例1.2所示问题的一般形式。为简单起见，例1.1和例1.2的表述都是针对数字的。但是，一般来说，我们希望对来自任意有序集合中的项目进行查找和排序。通常，每一项都唯一地确定了一条记录，因此，这些项目通常称为键（key）。例如，一条记录可能由某个人的个人信息组成，以这个人的社会保障号作为键。为这些项目定义一种数据类型keytype，在编写查找和排序算法时就使用这一数据类型。这就是说，这些项目来自任意有序集合。 下面的算法用数组表示列表S，它返回的不只是“是”或“否”，如果x在S中，还会返回x在数组中的位置；如果不在，则返回0。这一查找算法并不要求这些项目来自有序集合，但我们仍然使用标准数据类型keytype。 算法1.1　顺序查找 问题：键x是否存在于拥有n个键的数组S中？ 输入（参数）：正整数n；键的数组S，其索引范围为1至n；键x。 输出：location，x在S中的位置（若x不在S中，则为0）。 void seqsearch (int n, const keytype S[ ], keytype x, index& location) { location = 1; while (location <= n && S[location] != x) location++; if (location > n) location = 0; } 这段伪代码与C++非常类似，但不完全等同。一个很明显的不同就是对数组的使用。C++中的数组索引只能是从0开始的整数。很多时候，使用以其他整数范围为索引的数组可以更清楚地解释算法；而有时，使用非整数索引可以将算法解释得最为清楚。因此，在伪代码中，允许数组的索引是任意集合。在指明算法的“输入”和“输出”时，总会规定索引的范围。例如，算法1.1中指明S的索引范围为1至n。人们在计算列表中的项目数时，习惯于从1开始，所以为列表使用这一索引范围是很不错的选择。当然，这个算法可以直接用C++实现，声明如下： keytype S[n + 1]; 跳过S[0]位置不用。下文不再讨论以任何程序设计语言实现算法。我们的目的只是清楚明了地给出算法，从而使其便于理解和分析。 关于伪代码中的数组，还有另外两点明显不同于C++的地方。第一，允许采用变长两维数组作为例程的参数，比如算法1.4。第二，我们声明了局部变长数组。例如，如果n是过程example的一个参数，而且需要一个索引范围为2到n的局部数组，可以声明如下： void example (int n) { keytype S[2..n];  } 符号S[2..n]表示以2到n为索引范围的数组，这完全是伪代码；也就是说，它不是C++语言的组成部分。 如果与使用实际的C++指令相比，使用数学表达式或日常语言可以更简洁、更清楚地描述算法步骤，我们就会这么做。例如，假定仅当变量x介于取值low和high之间时，某些指令才会执行。我们会写为： if (low ≤ x ≤ high) {  } 而不是： if (low <= x && x <= high){  } 假定我们希望变量x取变量y的值，y取x的值。我们将写为： 交换x和y； 而不是写为： temp = x; x = y; y = temp; 除了数据类型keytype之外，我们还经常使用以下数据类型，它们也不是预定义的C++数据类型。 数据类型 含　　义 index 用作索引的整数变量 number 一个可以定义为整数（int）或实数（float）的变量 bool 一个可以取“true”或“flase”的变量 有时数字可以取任意实数，有时只能取整数。如果这一点对算法来说并不重要，我们将使用数据类型number。 我们有时会使用下面的非标准控制结构： repeat ( n times) {  } 其含义是将代码重复n次。在C++中，需要另外引入一个控制变量，并编写for循环。只有当真正需要引用循环中的控制变量时，我们才会使用for循环。 当算法的名字看起来与其返回值很吻合时，我们就将算法写为函数（function）。否则，就将其写为进程（procedure，C++中的void函数），并使用引用参数（reference parameter，也就是按地址传递的参数）来返回值。如果参数不是数组，在声明它时，会在数据类型名的末尾添加一个&符号。它在这里的意思是：这个参数包含算法的一个返回值。因为数组在C++中是自动按引用传递的，而且在传递数组时，C++中也没有使用&符号，所以我们没有使用&来表示数组中包含算法的返回值。相反，由于C++中使用保留字const来防止对所传递数组进行修改，所以我们使用const表示数组中不包含算法的返回值。 一般情况下，我们尽量避免使用C++特有的功能，以便那些只了解其他高级语言的人也能读懂伪代码。但是，我们的确会编写一些类似于i++之类的指令，其含义是指将i递增1。 如果不了解C++，你可能会觉得逻辑运算符和某些关系运算符有些陌生。这些符号列出如下。 运算符 C++符号 比　　较 C++代码 and && x = y (x == y) or || x ≠ y (x != y) not ! (x ≤ y) (x <= y) x ≥ y (x >= y) 下面给出更多的示例算法。第一个例子演示函数的使用。过程的例程名之前带有关键字void，而函数的例程名之前带有函数返回的数据类型。这个值在函数中通过return语句返回。 算法1.2　数组成员求和 问题：将包含n个数字的数组S中的所有成员加在一起。 输入：正整数n；数字数组S，其索引范围为1至n。 输出：sum，S中的数字之和。 number sum (int n, const number S[ ]) { index i; number result; result = 0; for (i = 1; i <= n; i++) result = result + S[i]; return result; } 本书将讨论许多排序算法。下面是其中很简单的一个。 算法1.3　交换排序 问题：按非递减顺序对n个键排序。 输入：正整数n；键的数组S，其索引范围为1至n。 输出：数组S，其中的键按非递减顺序排列。 void exchangesort (int n; keytype S[]) { index i, j; for (i=1;i<=n;i++) for (j=i+1;j<=n;j++) if (S[j] < S[i]) 交换S[i]和S[j]; } 指令 交换S[i]和S[j]; 的含义是，S[i]将取S[j]的值，S[j]将取S[i]的值。这条命令一点都不像C++指令；如果不使用C++指令的细节可以将事情描述得更简单，我们就一定会这么做。“交换排序”是将第i个位置的数字与第i+1个位置到第n个位置的数字进行比较。只要发现给定位置的数字小于第i个位置的数字，就交换这两个数字。这样，在完成第一遍for-i循环后，最小的数字将放在第一位，在第二遍循环后，第二小的数字将放在第二位，以此类推。 下面的算法执行矩阵乘法。回想一下，如果有两个2×2矩阵： 和 则它们的乘积C = A × B为： 例如， 一般情况下，如果有两个n×n矩阵A和B，则其乘积C如下： （1≤i, j≤n） 由这一定义，可以直接得出矩阵乘法的以下算法。 算法1.4　矩阵乘法 问题：计算两个n×n矩阵的乘积。 输入：一个正整数n；两维数字数组A和B，每个数组的行和列都以1至n为索引范围。 输出：一个二维数字数组C，包含了A和B的乘积，它的行和列都以1至n为索引范围。 void matrixmult (int n, const number A[][], const number B[][], number C[][]) { index i, j, k; for (i = 1; i<=n; i++) for (j=1; j≤n; j++){ C[i][j] = 0; for (k=1; k<=n; k++) C[i][j] = C[i][j]+A[i][k]*B[k][j]; } }