算法设计与分析

第1章 绪 论

算法理论研究的是算法的设计技术和算法的分析技术，前者是指面对一个问题，如何设计一个有效的算法，后者则是对已设计的算法，如何评价或判断其优劣。二者是相互依存的，设计出的算法需要检验和评价，对算法的分析反过来又将改进算法的设计。

1.1 算法的基本概念

算法的概念在计算机科学领域几乎无处不在，在各种计算机软件系统的实现中，算法设计往往处于核心地位。例如，操作系统是现代计算机系统中不可缺少的系统软件，操作系统的各个任务都是一个单独的问题，每个问题由操作系统中的一个子程序根据特定的算法来实现。用什么方法来设计算法，如何判定一个算法的优劣，所设计的算法需要占用多少时间资源和空间资源，在实现一个软件系统时，都是必须予以解决的重要问题。

1.1.1 为什么要学习算法

用计算机求解任何问题都离不开程序设计，而程序设计的核心是算法设计。一般来说，对程序设计的研究可以分为四个层次：算法、方法学、语言和工具，其中算法研究位于最高层次。算法对程序设计的指导可以延续几年甚至几十年，它不依赖于方法学、语言和工具的发展与变化。例如，用于数据存储和检索的Hash算法产生于20世纪50年代，用于排序的快速排序算法发明于20世纪60年代，但他们至今仍被人们广为使用，可是程序设计方法已经从结构化发展到面向对象，程序设计语言也变化了几代，至于编程工具很难维持三年不变。所以，对于从事计算机专业的人士来说，学习算法是非常必要的。

学习算法还能够提高人们分析问题的能力。算法可以看作是解决问题的一类特殊方法——它不是问题的答案，而是经过精确定义的①、用来获得答案的求解过程。因此，无论是否涉及计算机，特定的算法设计技术都可以看作是问题求解的有效策略。著名的计算机科学家科努思（Donald·Knuth）是这样论述这个问题的：“受过良好训练的计算机科学家知道如何处理算法，如何构造算法、操作算法、理解算法以及分析算法，这些知识远不只是为了编写良好的计算机程序而准备的。算法是一种一般性的智能工具，一定有助于我们对其他学科的理解，不管是化学、语言学、音乐还是另外 ①

算法固有的精确性限制了它所能够解决的问题种类，比如说，我们无法找到一个使人生活快乐的算法，也不能找到一个使人富有和出名的算法。

1

的学科。为什么算法会有这种作用呢？我们可以这样理解：人们常说，一个人只有把知识教给别人，才能真正掌握它。实际上，一个人只有把知识教给计算机，才能真正掌握它，也就是说，将知识表述为一种算法??比起简单地按照常规去理解事物，用算法将其形式化会使我们获得更加深刻的理解。”

算法研究的核心问题是时间（速度）问题。人们可能有这样的疑问：既然计算机硬件技术的发展使得计算机的性能不断提高，算法的研究还有必要吗？

计算机的功能越强大，人们就越想去尝试更复杂的问题，而更复杂的问题需要更大的计算量。现代计算技术在计算能力和存储容量上的革命仅仅提供了计算更复杂问题的有效工具，无论硬件性能如何提高，算法研究始终是推动计算机技术发展的关键。下面看几个例子。

1. 检索技术

20世纪50 ~ 60年代，检索的对象是规模比较小的数据集合。例如，编译系统中的标识符表，表中的记录个数一般在几十至数百这样的数量级。

70 ~ 80年代，数据管理采用数据库技术，数据库的规模在K级或M 级，检索算法的研究在这个时期取得了巨大的进展。

90年代以来，Internet引起计算机应用的急速发展，海量数据的处理技术成为研究的热点，而且数据驻留的存储介质、数据的存储方法以及数据的传输技术也发生了许多变化，这些变化使得检索算法的研究更为复杂也更为重要了。

近年来，智能检索技术成为基于Web信息检索的研究热点。使用搜索引擎进行Web信息检索时，经常看到一些搜索引擎前50个搜索结果中几乎有一半来自同一个站点的不同页面，这是检索系统缺乏智能化的一种表现。另外，在传统的Web信息检索服务中，信息的传输是按“Pull”的模式进行的，即用户找信息。而采用“Push”的方式，是信息找用户，用户不必进行任何信息检索，就能方便地获得自己感兴趣的信息，这就是智能信息推送技术。这些新技术的每一项重要进步都与算法研究的突破有关。

2. 压缩与解压缩

随着多媒体技术的发展，计算机的处理对象由原来的字符发展到图像、图形、音频、视频等多媒体数字化信息，这些信息数字化后，其特点就是数据量非常庞大，同时，多媒体所需的高速传输速度也是计算机总线所不能承受的。因此，对多媒体数据的存储和传输都要求对数据进行压缩。声音文件的MP3压缩技术说明了压缩与解压缩算法研究的巨大成功，一个播放3～4分钟歌曲的MP3文件通常只需3MB左右的磁盘空间。

3. 信息安全与数据加密

在计算机应用迅猛发展的同时，也面临着各种各样的威胁。一位酒店经理曾经描述了这样一种可能性：“如果我能破坏网络的安全性，想想你在网络上预定酒店房间所提供的信息吧！我可以得到你的名字、地址、电话号码和信用卡号码，我知道你现在的位置，将要去哪儿，何时去，我也知道你支付了多少钱，我已经得到足够的信息

2

来盗用你的信用卡！”这的确是一个可怕的情景。所以，在电子商务中，信息安全是最关键的问题，保证信息安全的一个方法就是对需要保密的数据进行加密。在这个领域，数据加密算法的研究是绝对必须的，其必要性与计算机性能的提高无关。

1.1.2 算法及其重要特性

算法（Algorithm）被公认为是计算机科学的基石。通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列，此外，算法还必须满足下列五个重要特性：

⑴ 输入：一个算法有零个或多个输入。算法的输入来源于两种方式：一种是从外界获得数据，另一种是由算法自己产生被处理的数据。

⑵ 输出：一个算法有一个或多个输出。既然算法是为解决问题而设计的，那么算法实现的最终目的就是要获得问题的解。没有输出的算法是无意义的。

⑶ 有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。

⑷ 确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。

⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

问题

输出 输入 算法（确定性、有穷性、可行性）

图1.1 算法的概念

概念回顾 算法和程序不同。程序（Program）是对一个算法使用某种程序设计语言的具体实现， 原则上，算法可以用任何一种程序设计语言来实现。算法的有穷性意味着不是所有的计 算机程序都是算法。 1.1.3 算法的描述方法

算法设计者在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来，即描述算法。常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等。下面以欧几里德算法（用辗转相除法求两个自然数m和n的最大公约数）为例进行介绍。

3

⑴ 自然语言

用自然语言描述算法，最大的优点是容易理解，缺点是容易出现二义性，并且算法通常都很冗长。欧几里德算法用自然语言描述如下：

① 输入m和n；

② 求m除以n的余数r；

③ 若r等于0，则n为最大公约数，算法结束；否则执行第④步； ④ 将n的值放在m中，将r的值放在n中； ⑤ 重新执行第②步。 ⑵ 流程图

用流程图描述算法，优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言。欧几里德算法用流程图描述如图1.2所示。

在计算机应用早期，使用流程图描述算法占有统治地位，但实践证明，除了一些非常简单的算法以外，这种描述方法使用起来非常不方便。如今，只能在早期有关算法的教材中找到它的踪影了。 ⑶ 程序设计语言

用程序设计语言描述的算法能由计算机直接执行，而缺点是抽象性差，使算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。

开始 欧几里德算法用C++语言书写的程序如下：

#include

int CommonFactor(int m, int n) {

int r=m % n; while (r!=0) {

m=n; n=r;

r=m % n; }

return n; }

void main( ) {

cout<

伪代码（Pseudocode）是介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。至于算法中自然语言

4

输入m和n r=m % n Y N m=n n=r 输出n 结束 图1.2 用流程图描述算法

r=0