书名：计算机算法设计与分析研究pdf/doc/txt格式电子书下载

推荐语：

作者：柴宝杰著

出版社：新华出版社

出版时间：2015-07-01

书籍编号：30304362

ISBN：9787516619056

正文语种：中文

字数：125614

版次：1

所属分类：互联网+-产品/运营

版权信息

书名：计算机算法设计与分析研究

作者：柴宝杰

出版社：新华出版社

出版时间：2015-07-01

ISBN：9787516619056

免责声明：本站所有资源收集整理于网络，版权归原作者所有。
本站所有内容不得用于商业用途。本站发布的内容若侵犯到您的权益，请联系站长删除，我们将及时处理！

前言

计算机算法是计算机科学和计算机应用的核心。无论是计算机系统、系统软件的设计还是为解决计算机的各种应用课题做的设计都可归结为算法的设计。因此，学好计算机算法设计与分析，对从事计算机系统结构、系统软件及应用软件研究和开发人员来讲都是非常重要的和必不可少的。

目前对于计算机算法介绍的图书通常有两类：一类着重介绍的是数据结构本身的实现，即数据结构与算法；另一类着重介绍的是算法设计的原理，即算法设计与分析。作者撰写的这本《计算机算法设计与分析研究》则从算法实践的角度出发，着重介绍几种常用算法的基本思想、完整实现及其应用，使读者能用学过的理论知识解决具体、复杂的实际问题，从而达到应用型人才培养的目标。

本书以算法实践为知识单元，以期为读者提供坚实的计算机算法的应用知识。全书共分8章：第1章主要介绍了算法的基础知识；第2章主要介绍栈和队列的结构特性及基于这些结构的一些应用举例；第3章主要介绍树和图的结构特性及基于这些结构的常用算法；第4章主要介绍递归的概念和分治法的基本思想及基于递归或分治思想所解决的经典问题；第5章主要介绍贪心算法的思想及利用贪心算法解决实际问题；第6章主要介绍动态规划法的适用性和算法的设计要点及利用动态规划法所解决的经典问题；第7章对NP-完全问题与处理做了初步介绍；第8章主要介绍线性规划的概念及对二分图相关问题做了初步分析与研究。

本书在撰写过程中参考了大量优秀研究成果，得到广大专家学者及同仁的广泛帮助，在此，深表感谢！同时由于本人水平有限，研究还不够深入，书中若有不当之处，恳请广大专家读者批评指正。

作者

2015年4月

第1章　算法概述

1.1　算法与问题求解

1.1.1　算法的概念

算法（Algorithm）的概念在计算机科学与技术领域几乎无处不在，在各种计算机系统的实现中，算法的设计往往处于核心的位置。不过，计算机算法的研究受到人们如此的重视是在20世纪70年代以后。具体地说，D．E．Knuth以及A．V．Aho、J．E．Hopcroft、J．D．Ullman等人的著述对算法的研究起到了奠基的作用。其中，Stanford大学著名计算机科学家D．E．Knuth因他的这一著作，获得了计算机领域的最高奖——图灵奖。^[1]

虽然我们每天都在与算法打交道，但要严格地指出什么是算法却不是一件容易的事。通过对众多学者关于算法研究的认识得出：算法是指解决问题的一种方法或者一个过程。如果将问题看作函数，那么算法就是把输入转换为输出。一个问题可以用多种算法来解决，一种给定的算法解决一个特定的问题。本书涉及了许多问题，其中有些问题给出了几种算法。知道一个问题的多种解法的好处在于，对于问题的一个特例或问题的一类特殊输入，解法A可能比解法B有效，而对于另一特例或问题的另一类特殊输入，解法B可能又比解法A更有效。例如，有些排序算法适合于数目较少的序列，有些排序算法则适合于数目较多的序列，而另有一些算法则适合于变长字符串。

1.1.2　问题求解

就像生物学家把自然界的所有生物作为自己的研究对象一样，计算（Computation）学科或称计算机科学则把问题作为自己的研究对象，即用计算机来解决问题。在计算机专家的头脑中，世界是一个个要解决的问题的集合。进一步来说，每一个问题又都是该问题的所有实例（Instance）的集合。一般而言，一个问题的一个实例就是为计算该问题所需的一组输入。

例如：

（1）整数乘法问题。其全部可能输入集合：，其中Z表示整数集。整数乘法问题的一个实例：<2，4>，求2×4=？。

（2）旅行商问题。其实例集为：。旅行商问题的一个实例：n＝4。

旅行商问题的这个实例（n，W）就是求环游四个城市（1，2，3，4）的代价和最小的周游路线，其中权矩阵W给出了四个城市的距离（代价），Wi·j表示由城市i到城市j的距离（代价）。

（3）语言L（G，∑）的识别问题。

其中，G为文法，即语法规则集，∑为一个字符集。L（G）为∑上由G生成的语言，∑*表示由∑中的字符组成的所有字符串集合。

语言L的识别问题｛G，∑，ω|ω∈∑*｝的一个实例ω∈∑*，识别算法判断ω∈L（G）是否成立。

一般来讲，对于问题P，总有其相应的实例集I，那么，一个算法A是问题P的算法，意味着把P的任一实例input∈I作为A的输入，都能得到问题P的正确输出。一个问题可以有许多个不同的算法。

1.1.3　算法的特性

作为一个算法，应该具备如下5个特性。

（1）输入性

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

（2）输出性

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

（3）确定性

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

（4）有穷性

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

（5）可行性

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

假如现在有一个问题：依据如下分段函数，要求对用户输入的一个自变量x的值，给出相应的函数值。

实现分段函数求值功能的过程如下。

步骤1：输入自变量x的值。

步骤2：依据自变量x的值进行判断：

如果x>0，执行x+2→f（x）操作；

如果x<0，执行x-2→f（x）操作；

如果x＝0，执行2→f（x）操作。

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

步骤3：输出步骤2计算的结果。

显然，上述描述满足算法的5个重要特征，因此，该描述就是一个算法。

在现实社会中，不同的人对于同一问题会有不同的看法或解决方法。同样，在计算机领域，对于同一问题存在多种算法也是很自然的事情。例如对于一批数据的排序问题，就存在多种排序方法。判断一个算法的好坏主要依据如下4个标准。

（1）正确性

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

（2）可读性

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

（3）健壮性

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

（4）效率

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

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

1.2　算法的描述

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

1.2.1　自然语言描述法

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

1.2.2　算法框图法

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

1.2.3　伪码语言描述法

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

当然，大部分的算法最终是需要通过能够向计算机发送一系列命令的程序来实现的。所谓“程序”是指对所要解决问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说，数据结构＋算法＝程序。

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

1.3　算法分析

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

对于任意给定的一个问题，设计出复杂性尽可能低的算法是在设计算法时追求的重要目标之一；而当给定的问题存在多种算法时，选择其中复杂性最低的算法是选用算法时遵循的重要准则。因此，算法的复杂性分析对算法的设计或选用具有重要的指导意义和实用价值。

1.3.1　时间复杂度

通常，对于一个算法的复杂性分析主要是对算法效率的分析，包括衡量其运行速度的时间效率及衡量其运行时所需要占用空间大小的空间效率。

对于早期的计算机来说，时间与空间都是极其珍贵的资源。由于硬件技术的发展大大提高了计算机的存储容量，使得存储容量的局限性对于算法的影响大大降低。但是时间效率并没有得到相应程度的提高。因此，算法的时间效率或算法时间复杂度是算法分析中的关键所在。

对于算法的时间效率的计算，通常是抛开与计算机硬件、软件有关的因素，仅考虑实现该算法的高级语言程序。一般而言，对程序执行的时间复杂度的分析是分块进行的，先分析程序中的语句，再分析各程序段，最后分析整个程序的执行复杂度。通常以渐进式的大0（希腊字母Omicron，奥米克戎）形式来表示算法的时间复杂度。渐进式的大0形式表示时间复杂度。

1.3.2　空间复杂度

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

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

————————————————————

[1] 刘璟编著：《计算机算法引论：设计与分析技术》，科学出版社，2003，5。

[2] 徐保民，陈旭东，李春艳编著，《计算机算法与实践教程》，北京交通大学出版社，2007，3-5。

第2章　线性数据结构与算法

由于算法是作用在数据上的，因此数据的组织形式即数据结构在很大程度上影响着算法的设计和实现。本章着重介绍几种常见的线性数据结构，包括线性表、栈与队列，并同时给出若干常用的基于上述线性数据结构的算法实现。

2.1　线性表

线性表（Linear List）是最常用且比较简单的一种数据结构，其主要特点是数据元素有序地存放在一起。

2.1.1　线性表的概念及特点

线性表是由有限个数据元素组成的有序集合，每个数据元素由一个或多个数据项组成。例如构成26个英文字母的字母表（A，B，C，…，Z）是一个线性表，表中每个元素由单个字符组成数据项。

对于非空的线性表而言，它具有如下4个特点：

（1）表中有且仅有一个开始结点；

（2）表中有且仅有一个终端结点；

（3）除了开始结点和终端结点外，其他每个元素前面均有且仅有一个称为直接前趋的数据元素，它的后面均有且仅有一个称为直接后继的数据元素；

（4）虽然不同线性表的数据元素可以是各种各样的，但是同一线性表中的数据元素必须

....