作者：陈慧南
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
算法设计与分析：C++语言描述(第2版)试读：
前言
本书为普通高等教育“十一五”国家级规划教材。
算法设计与分析不仅是计算机科学与技术专业学生的必备知识，也是计算机应用工作者必不可少的基础知识。掌握扎实的算法设计与分析理论和方法有助于理工科学生进一步学习计算机技术，适应更广泛的职业挑战。
计算机学科教学计划2001（Computing Curricula 2001，简称CC2001）将计算机学科分成14个领域，每个领域分成若干个知识单元，每个知识单元又包括若干个主题。CC2001强调算法，重视算法设计与分析能力和程序设计能力。计算机算法的基本内容主要包含在算法与复杂性（Algorithm and Complexity，简称AL）和程序设计基础（Programming Fundamental，简称PF）等知识领域中。在CC2001建议的计算机科学与技术专业的280个核心学时中，程序设计与算法方面分配90个核心学时，约占总核心学时的32.1%。
算法领域涉及的内容广泛，通常包括迄今为止，算法学家们所设计的许多基本和经典算法，如排序、搜索、图算法、组合问题算法、字符串算法和大量的数值算法，算法问题求解、算法分析技术和常用的算法设计策略，可计算性理论和问题复杂性的研究，如计算模型、NP完全问题和问题复杂度下界理论。近年来，算法研究在随机算法、近似算法、密码算法、分布式算法和并行算法，以及其他算法方面也都有很多新成果。
作为“算法设计与分析”课程教材，根据我国在算法与数据结构方面课程开设的实际情况，本书不再重复属于我国传统“数据结构”课程中的基本数据结构和算法的内容，但选用快速排序等在“数据结构”课程中已学过的若干排序、搜索和图算法，它们被作为算法设计策略和算法分析的实例使用。这种做法不是内容的简单重复，而是必要的和有益的深化。以学生熟知的知识为基础，介绍新知识，可使学生更容易理解和接受新的算法知识。
算法知识理论性较强，涉及的范围又很广，给学习和理解造成困难。为了将本书写成条理清晰、内容翔实、逻辑严谨、深入浅出的“算法设计与分析”教材，作者做了以下努力。
首先，本书分3部分组织内容，力求做到结构清晰、内容取舍恰当。
其次，书中算法都有完整的C++程序，程序结构清楚，构思精巧，对程序代码都做了详细注释，所有程序都已在VC++环境下编译通过并能正确运行，它们既是学习算法设计的示例，也是很好的C++程序设计示例。
此外，本书通过大量实例和图示介绍算法，并有丰富的习题，便于自学。
这样做的目的是在保持算法科学性的同时，加强其技术性和实用性，也降低算法学习的难度，使复杂抽象的算法设计更容易为学习者理解和掌握。这也体现了计算机学科的科学性和工程性、理论性和实践性并重的学科特点。
全书包括3部分：算法和算法分析、算法设计策略及求解困难问题。
第1部分介绍算法概念、算法问题分类和问题求解方法，算法复杂度、递归技术，还介绍了两种新的数据结构：跳表和伸展树，以及它们特定的算法分析方法。
第2部分讨论常用的算法设计策略：基本搜索和遍历方法、分治法、贪心法、动态规划法、回溯法和分枝限界法。对于每种算法设计策略，通常先介绍一般方法，然后使用该策略解决若干经典的算法问题。
第3部分介绍NP完全问题、随机算法、近似算法，并对现代密码学和数论算法也做了简要论述。
本书作者在南京邮电大学讲授“算法设计与分析”和“数据结构”课程多年。本书是在作者编写出版的多本关于算法与数据结构领域教材的基础上，参考了近年来国内外多种算法设计与分析的优秀教材编写而成的。本书的编写得到了电子工业出版社的大力支持，并得到了南京邮电大学和计算机学院领导的推荐和关心，在此表示衷心感谢。
书中若有不妥之处，敬请读者批评指正。
作 者
第1部分 算法和算法分析
第1章 算法问题求解基础
算法是计算机学科的一个重要分支，它是计算机科学的基础，更是计算机程序的基石。算法是计算机求解问题的特殊方法。学习算法，一方面需要学习求解计算领域中典型问题的各种有效算法，还要学习设计新算法和分析算法性能的方法。本章给出算法的基本概念，介绍使用计算机求解问题的过程和方法，讨论递归算法及证明递归算法正确性的归纳法。
1.1 算法概述
1.1.1 什么是算法在学习一门计算机程序设计语言，如C/C++或Pascal之后，应该对算法一词不再陌生。编写一个程序，实际上是在实现使用计算机求解某个问题的方法。在计算机科学中，算法一词用于描述一个可用计算机实现的问题求解（problem-solving）方法。
什么是算法?笼统地说，算法（algorithm）是求解一类问题的任意一种特殊的方法。较严格的说法是，一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。此外，算法具有下列5个特征。（1）输入（input）：算法有零个或多个输入量；（2）输出（output）：算法至少产生一个输出量；（3）确定性（definiteness）：算法的每一条指令都有确切的定义，没有二义性；（4）能行性（effectiveness）：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；（5）有穷性（finiteness）：算法必须总能在执行有限步之后终止。
所有算法都必须具有以上5个特征。算法的输入是一个算法在开始前所需的最初的量，这些输入取自特定的值域。算法可以没有输入，但算法至少应产生一个输出，否则算法便失去了它存在的意义。算法是一个指令序列。一方面，每条指令的作用必须是明确、无歧义的。在算法中不允许出现诸如“计算5+3或计算7-3”这样的指令。另一方面，算法的每条指令必须是能行的。对一个计算机算法而言，能行性要求一条算法指令应当最终能够由执行有限条计算机指令来实现。例如，一般的整数算术运算是能行的，但如果1÷3的值需由无穷的十进制展开的实数表示，就不是能行的。因此，概括地说，算法是由一系列明确定义的基本指令序列所描述的，求解特定问题的过程。它能够对合法的输入，在有限时间内产生所要求的输出。如果取消有穷性限制，则只能称为计算过程（computational procedure）。
描述一个算法有多种方法，可以用自然语言、流程图、伪代码和程序设计语言来描述。当一个算法使用计算机程序设计语言描述时，就是程序（program）。算法必须可终止。计算机程序并没有这一限制，例如，一个操作系统是一个程序，却不是一个算法，一旦运行，只要计算机不关机，操作系统程序就不会终止运行。所以，操作系统程序是使用计算机语言描述的一个计算过程。
算法概念并不是计算机诞生以后才有的新概念。计算两个整数的最大公约数的辗转相除法是由古希腊欧几里得（约公元前330—275年）在他的《几何原本》（Euclid’s Elements）中提出的，它是算法研究最重要的早期成果。直到1950年左右，算法一词还经常与欧几里得算法（Euclid’s algorithm）联系在一起。中国的珠算口诀可视为典型的算法，它将复杂的计算（如除法）描述为一系列的算珠拨动操作。
欧几里得算法又称辗转相除法，用于计算两个整数m和n（0≤m＜n的最大公约数，记为gcd（m，n）。其计算过程是重复应用下列等式，直到n mod m=0。
式中，n mod m表示n除以m之后的余数。因为gcd（0，n）=n，n的最后取值也就是m和n的最大公约数。例如，gcd（24，60）=gcd（12，24）=gcd（0，12）=12。
欧几里得算法使用了递归，其C/C++语言描述见程序1-1。欧几里得算法的迭代形式描述见程序1-2。请注意数学上的运算符mod与[1]C/C++语言的“%”运算符的区别。【程序1-1】欧几里得递归算法【程序1-2】欧几里得迭代算法
上述程序必定会结束，因为每循环一次，m的新值就会变小，但绝对不会成为负数，当m=0时程序终止。
最大公约数问题还可以有其他算法。程序1-3的连续整数检测算法的依据直接来自最大公约数的定义：m和n的最大公约数是能够同时整除它们的最大正整数。显然，一个公约数不会大于两数中的较小者，因此，可以先令t=min{m，n}，然后检查t能否分别整除m和n，若能，则t就是最大公约数，否则令t减1后继续检测。程序1-3必定会终止。如果m和n的最大公约数是1，则当t=1时，程序终止。【程序1-3】Gcd的连续整数检测算法
从上面的讨论可知，一个问题可以设计不同的算法来求解，针对同一个问题的算法也许基于完全不同的解题思路。求两个整数的最大公约数可以采用欧几里得算法，也可以采用连续整数检测算法，两种算法的解题速度会有显著差异。此外，同一个算法可采用不同的形式来表示。例如，欧几里得算法可以写成递归形式，也可以写成迭代形式。1.1.2 为什么学习算法
算法是计算机科学的基础，更是程序的基石，只有具有良好的算法基础才能成为训练有素的软件人才。对于计算机专业的学生来说，学习算法的理由是非常充分的。因为你必须知道来自不同计算领域的重要算法，你也必须学会设计新的算法、确认其正确性并分析其效率。随着计算机应用的日益普及，各个应用领域的研究和技术人员都在使用计算机求解他们各自专业领域的问题，他们需要设计算法，编写程序，开发应用软件，所以学习算法对于越来越多的人来说变得十分必要。
著名的美国计算机科学家克努特（D.E.Knuth）说过：“一个受过良好的计算机科学知识训练的人知道如何处理算法，即构造算法、操纵算法、理解算法和分析算法。算法知识远不只是为了编写好的计算程序，它是一种具有一般意义的智能工具，必定有助于对其他学科的理解，不论化学、语言学或者音乐等。”
哈雷尔（David Harel）在他的《算法学——计算的灵魂》一书中说：“算法不仅是计算机学科的一个分支，它更是计算机科学的核心，而且可以毫不夸张地说，它和绝大多数科学、商业和技术都是相关的。”
1.2 问题求解方法
软件开发的过程是使用计算机求解问题的过程。使用计算机解题的核心任务是设计算法。算法并非就是问题的解，它是准确定义的，用来获得问题解的计算过程的描述。算法是问题的程序化解决方案。显然，算法能够求解的问题种类是有局限性的，它们不可能求解现实世界中的所有问题。本书讨论的问题都是指能用算法求解的问题。1.2.1 问题和问题求解
什么是问题（problem）?只要目前的情况与人们所希望的目标不一致，就会产生问题。例如，排序问题是：任意给定一组记录，排序的目的是使得该组记录按关键字值非减（或非增）次序排列。
问题求解（problem solving）是寻找一种方法来实现目标。问题求解是一种艺术，没有一种通用的方法能够求解所有问题。有时，人们不得不一次又一次地尝试可能的求解方法，直到找到一种正确的求解途径。一般说来，问题求解中存在着猜测和碰运气的成分。然而，当我们积累了问题求解的经验，这种对问题解法的猜测就不再是完全盲目的，而是形成某些问题求解的技术和策略。问题求解过程（problem solving process）是人们通过使用问题领域知识来理解和定义问题，并凭借自身的经验和知识去选择和使用适当的问题求解策略、技术和工具，将一个问题描述转换成问题解的过程。
现在，很多问题可以用计算机求解，计算机的应用已渗透到人类活动的方方面面。有些问题，如四色问题，如果没有计算机，至今恐怕难以求解。计算机求解问题的过程就是一个计算机软件的开发过程，被称为软件生命周期（software life cycle）。
计算机求解问题的关键之一是寻找一种问题求解策略（problem solving strategy），得到求解问题的算法，从而得到问题的解。例如，求解前面提到的排序问题是指设计一种排序算法，能够把任意给定的一组记录排成有序的记录序列。1.2.2 问题求解过程
匈牙利数学家乔治·波利亚（George Polya）在1957年出版的《How to solve it》一书中概括了如何求解数学问题的技术。这种问题求解的四步法对于大多数其他科学也是适用的，同样也可用于求解计算机应用问题。
问题求解的四步法简述如下。（1）理解问题（understand the problem）
毫无疑问，为了求解问题必须首先理解问题。如果不理解问题，当然就不可能求解它。此外，对问题的透彻理解有助于求解问题。这一步很重要，它看似简单，其实并不容易。在这一步，我们必须明确定义所要求解的问题，并用适当的方式表示问题。对于简单问题，不妨直接用自然语言描述问题，如排序问题。（2）设计方案（devise a plan）
求解问题时，首先考虑从何处着手，考虑以前有没有遇到类似的问题，是否解决过规模较小的同类问题。此外，还应选择该问题的一些特殊例子进行分析。在此基础上，考虑选择何种问题求解策略和技术进行求解，以得到求解问题的算法。（3）实现方案（carry out the plan）
实现求解问题的算法，并使用问题实例进行测试、验证。（4）回顾复查（look back）
检查该求解方法是否确实求解了问题或达到了目的。评估算法，考虑该解法是否可简化、改进和推广。
对于上一小节讨论的求最大公约数问题，理解起来并不困难，但为了求解问题，则需要相关的数学知识。最简单的求解方案可以直接从最大公约数的定义出发得到，这就是程序1-3的连续整数检测算法。欧几里得算法建立在已经证明式（1-1）成立的基础上。对于这两种求解算法，可以使用m和n的若干值进行测试，验证算法的正确性。通过比较，发现对于求最大公约数问题，连续整数检测算法和欧几里得算法的时间效率差别很大。递归的欧几里得算法又可改写成迭代形式，迭代算法的效率一般高于其对应的递归算法。1.2.3 系统生命周期
一个计算机程序的开发过程就是使用计算机求解问题的过程。软件工程（software engineering）将软件开发和维护过程分成若干阶段，称为系统生命周期（system life cycle）或软件生命周期。系统生命周期法要求每个阶段完成相对独立的任务；各阶段都有相应的方法和技术；每个阶段都有明确的目标，要有完整的文档资料。这种做法便于各种软件人员分工协作，从而降低软件开发和维护的困难程度，保证软件质量，提高开发大型软件的成功率和生产率。
通常把软件生命周期划分为分析（analysis）、设计（design）、编码（coding or programming）、测试（testing）和维护（maintenance）等5个阶段。前4个阶段属于开发期，最后一个阶段处于运行期。
软件开发过程的前两个阶段“分析”和“设计”非常重要。“分析”是弄清楚需要“做什么（what）”，而“设计”是解决“如何做（how）”。
在问题求解的分析阶段，我们试图理解问题，弄清楚为了求解它必须做什么，而不是怎样做。在分析阶段，必须理解问题的需求。需求常常被分为功能需求和非功能需求两类。功能需求描述求解问题的程序必须具有的功能和特性，非功能需求是软件必须满足的约束等。例如，对一个整数序列进行排序的问题，其功能需求是将一个任意整数序列排列成非减有序序列，而非功能需求也许是代码和数据使用的内存空间不能超过20MB，运行时间不超过5min等。这些需求应当被充分审查和讨论，并明确定义，形成需求规范（requirement specification）。问题定义必须明确，无二义性，且具有一致性。
设计阶段确定如何求解问题，包括选择何种问题求解策略和技术，如算法设计策略。在软件开发中，常采用逐步求精的方法，并用伪代码和流程图来设计和描述算法。
编码实现阶段的任务是编写程序，运行程序，并使用测试用例测试程序，验证程序的正确性。
1.3 算法设计与分析
1.3.1 算法问题求解过程算法问题的求解过程在本质上与一般问题的求解过程是一致的。具体求解步骤如图1-1所示。求解一个算法问题，需要先理解问题。通过仔细阅读对问题的描述，充分理解所求解的问题。为了完全理解问题，可以列举该问题的一些小例子，考虑某些特殊情况。图1-1 算法问题求解过程
算法一般分两类：精确算法和启发式算法。一个精确算法（exact algorithm）总能保证求得问题的解。而一个启发式算法（heuristic algorithm）通过使用某种规则、简化或智能猜测来减少问题求解时间。它们也许比精确算法更有效，但其求解问题所需的时间常常因实例而异。它们也不能保证求得的解必定是问题的最优解，甚至不一定是问题的可行解（feasible solution）。一般来讲，启发式算法往往缺少理论依据。对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为近似算法（approximation algorithm）。近似算法求得的应当是问题的可行解，但可能不是最优解。如果在算法中需做出某些随机选择，则称为随机算法（randomized algorithm）。随机算法执行的随机选择一般依赖于随机数发生器所产生的随机数。
在理解问题之后，算法设计者需要选择是否采取精确解法。有一些问题的确无法求得精确解，例如求平方根、求定积分和求解非线性方程。另一些问题虽然存在精确算法，但这些算法的求解时间慢得让人无法接受。例如，设计一个导致赢局的人机对弈程序并不困难，可以采用穷举算法。对于任何一种棋类，尽管其可能的棋局数目可谓天文数字，但总是有限的。我们总能设计一个算法对任意给定的一种棋局，判断这一棋局是否可能导致赢局，并由此决定下一步应走哪一着棋。采用这种以穷举方式逐一检查棋局的算法，每一步决策都将异常费时，即使在当代速度最快的计算机上运行也是不实际的。
启发式算法并不总能导致理想的解，但常常能在合理的时间内得到令人满意的结果。
此外，虽然有些算法并不要求精心组织输入数据，但另一些算法的确依赖于精心设计的数据结构。对问题实例的数据进行恰当组织和重构，有助于设计和实现高效的算法。数据结构对于算法的设计常常至关重要。对于具有一定“数据结构”知识的读者，应不难理解这一点。1.3.2 如何设计算法
使用计算机的问题求解策略主要指算法设计策略（algorithm design strategy）。一般来说，算法的设计是一项创造性活动，不可能完全自动化，但学习一些基本的算法设计策略是非常有用的。对于所求解的问题，只要符合某种算法设计策略的前提，便可以利用它设计出精致而有效的算法。算法设计技术（也称“策略”）是使用算法解题的一般性方法，可用于解决不同计算领域的多种问题。如果所求问题符合某种算法设计策略处理的问题特性，就可使用该算法设计策略设计算法、求解问题。例如，读者熟知的排序问题符合分治策略求解的问题特征，可以用分治法求解。然而，由于在使用分治策略解题时的思路不同，会得到不同的排序算法。在第4章中将看到，合并排序和快速排序都可视为由分治法产生的排序算法，但两者是不同的算法。1.3.3 如何表示算法
算法所表示的计算过程需要以某种方式描述出来。算法可以使用自然语言描述，但自然语言不够严谨。在计算机应用的早期，算法主要用流程图描述。实践证明，流程图通常只适于描述简单算法，对于复杂算法，流程图也会十分复杂，难以建图和理解。伪代码是自然语言和程序设计语言的混合结构。它所描述的算法通常比自然语言精确，又比实际程序设计语言简洁。但对于伪代码，并没有形成一致的语法规则，需要事先约定。使用一种实际的程序设计语言描述算法，虽然有时会多一些细节，但有助于算法的精确描述。此外，用C++语言描述的算法本身就是很好的C/C++程序范例，对学生掌握算法思想和进行程序设计都是有益的。
在本书中，我们使用 C/C++语言描述算法。C/C++语言类型丰富、语句精练，既能描述算法所处理的数据结构，又能描述算法过程。同时，用C/C++语言描述算法可使算法结构简洁明了，可读性好。1.3.4 如何确认算法
如果一个算法对于所有合法的输入，都能在有限时间内输出预期的结果，那么此算法是正确的。确认一个算法是否正确的活动称为算法确认（algorithm validation）。算法确认的目的在于确认一个算法能否正确无误地工作。使用数学方法证明算法的正确性，称为算法证明（algorithm proof）。对于有些算法，正确性证明十分简单，但对于另一些算法，却可能十分困难。
证明算法正确性常用的方法是数学归纳法。对于程序1-1的求最大公约数的递归算法RGcd，可用数学归纳法证明如下：
设m和n是整数，0≤m＜n。若m=0，则因为gcd（0，n）=n，故程序RGcd在m=0时返回n是正确的。归纳法假定，当0≤m＜n＜k时，函数RGcd（m，n）能在有限时间正确返回m和n的最大公约数，那么，当0＜m＜n=k时，考察函数RGcd（m，n），它将具有RGcd（n%m，m）的值。这是因为0≤n%m＜m且gcd（m，n）=gcd（n mod m，m）（数论定理），故该值正是m和n的最大公约数，证毕。
若要表明算法是不正确的，只需给出能够导致算法不能正确处理的输入实例即可。
到目前为止，算法的正确性证明仍是一项很有挑战性的工作。在大多数情况下，人们通过程序测试和调试来排错。程序测试（program testing）是指对程序模块或程序总体，输入事先准备好的样本数据（称为测试用例，test case），检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求的一项积极活动。测试的目的是为了“发现错误”，而不是“证明程序正确”。程序经过测试暴露了错误，需要进一步诊断错误的准确位置，分析错误的原因，纠正错误。调试（debugging）是诊断和纠正错误的过程。1.3.5 如何分析算法
算法的分析（algorithm analysis）活动是指对算法的执行时间和所需空间的估算。求解同一问题可以编写不同的算法，通过算法分析，可以比较两个算法效率的高低。对于算法所需的时间和空间的估算，一般不需要将算法写成程序在实际的计算机上运行。当然在算法写成程序后，便可使用样本数据，实际测量一个程序所消耗的时间和空间，这称为程序的性能测量（performance measurement）。
1.4 递归和归纳
递归是一个数学概念，也是一种有用的程序设计方法。在程序设计中，为了处理重复性计算，最常用的办法是组织迭代循环，除此之外还可以采用递归计算的办法。美国著名计算机科学家约翰·麦卡锡极力主张将递归引入Algol 60语言，该语言是后来的Pascal、PL/1和C语言的基础。他本人提出的表处理语言Lisp不仅允许函数递归，数据结构也是递归的。
递归和归纳关系紧密。归纳法证明是一种数学证明方法，可用于证明一个递归算法的正确性。在下一章中还将看到，归纳法在算法分析中也很有用。1.4.1 递归
1.递归定义
定义一个新事物、新概念或新方法，一般要求在定义中只包含已经明确定义或证明的事物、概念或方法。然而递归定义却不然，递归（recursive）定义是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分：基础情况（base case）和递归部分。基础情况以直接形式明确列举新事物的若干简单对象，递归部分给出由简单（或较简单）对象定义新对象的条件和方法。所以，只要简单或相对简单的对象已知，用它们构造的新对象是明确的，无二义性的。
例1-1 斐波那契数列
说明递归定义的一个典型例子是斐波那契（Fibonacci）数列，它的定义可递归表示成：
根据这一定义，可以得到一个无穷数列0，1，1，2，3，5，8，13，21，34，55，…，称为斐波那契数列。斐波那契数列产生于12世纪，但直到18世纪才由A.De.Moivre提出了它的非递归定义式。从12世纪到18世纪期间，人们只能采用斐波那契数列的递归定义来计算。斐波那契数列的直接计算公式为：
式中，…
2.递归算法
当一个算法采用递归方式定义时便成为递归算法。一个递归算法是指直接或间接调用自身的算法。递归本质上也是一种循环的算法结构，它把“较复杂”的计算逐次归结为“较简单”情形的计算，直至归结到“最简单”情形的计算，并最终得到计算结果为止。
使用递归来解决问题，与使用一本大词典查询一个单词的情形是类似的。在词典中查一个单词时，首先得到对该单词的解释，如果在该单词的解释中包含不认识的单词，还需要继续查这些不认识的单词的词义，直到所有相关单词都已有明确解释为止。如果其中至少有一个单词在词典中没有解释或出现循环定义，那么这一过程是循环不确定和错误的。
许多问题可以采用递归方法来编写算法。一般来说，递归算法结构简洁而清晰，可以用归纳法证明其正确性，并易于算法分析。
根据斐波那契数列的递归定义，可以很自然地写出计算F的递归n算法。为了便于在表达式中直接引用，可以把它设计成一个函数过程，见程序1-4。【程序1-4】求Fn
函数 Fib（n）中又调用了函数 Fib（n-1）和 Fib（n-2）。这种在函数体内调用自己的做法称为递归调用，包含递归调用的函数称为递归函数（recursive function）。从实现方法上讲，递归调用与调用其他函数没有什么两样。设有一个函数 P，它调用函数 Q（T x），P 被称为调用函数（calling function），而Q称为被调函数（called function）。在调用函数P中，使用Q（a）来引起被调函数Q的执行，这里a称为实在参数（actual parameter），x称为形式参数（formal parameter）。当被调函数是P本身时，P是递归函数。有时，递归调用还可以是间接的。对于间接递归调用，在这里不做进一步讨论。编译程序利用系统栈实现函数的递归调用，系统栈是实现函数嵌套调用的基础。图1-2 计算Fib（4）的递归树
可以用所谓的递归树（recursive tree）来描述程序1-4的函数Fib执行时的调用关系。假定在主函数main中调用Fib（4），让我们来看Fib（4）的执行过程。这一过程可以用图1-2所示的递归树描述。从图中可见，Fib（4）需要分别调用Fib（2）和Fib（3），Fib（2）又分别调用Fib（0）和Fib（1），……。其中，Fib（0）被调用了两次，Fib（1）被调用了三次，Fib（2）被调用了两次。可见，许多计算工作是重复的，当然这是费时的。
3.递归数据结构
在数据结构中，树、二叉树和列表常采用递归方式来定义。原则上，线性表、数组、字符串等也可以进行递归定义。但是习惯上，许多数据结构并不采用递归定义方式，而是直接定义。线性表、字符串和数组等数据结构的直接定义方式更自然、更直截了当。使用递归方式定义的数据结构称为递归数据结构（recursive data structure）。1.4.2 递归算法示例
设计递归算法需要使用一种新的思维方式。递归概念较难掌握，本节的例子可以加深对递归算法的理解。
例1-2 逆序输出正整数的各位数
设有正整数n=12345，现希望以各位数的逆序形式输出，即输出54321。设k位正整数为dd…d，为了以逆序形式输出各位数dd…12kkk-1d，可以分成两步：1（1）首先输出末位数d；k（2）然后输出由前k-1位组成的正整数dd…d的逆序形式。12k-1
上面的步骤很容易写成程序1-5的递归算法。【程序1-5】逆序输出正整数的各位数
例1-3 汉诺塔问题（tower of Hanoi）
假定有三个塔座：X，Y，Z，在塔座X上有n个直径大小各不相同，按圆盘大小从小到大编号为1，2，…，n的圆盘。现要求将X塔座上n个圆盘移到塔座Y上，并仍按同样顺序叠排，即初始状态如图1-3（a）所示，最终状态如图1-3（d）所示。圆盘移动时必须遵循下列规则：（1）每次只能移动一个圆盘；（2）圆盘可以加到塔座X，Y，Z中任意一个上；（3）任何时刻都不能将一个较大的圆盘放在较小的圆盘之上。
为了将圆盘全部从塔座X移到塔座Y，并且仍按原顺序叠排，一种朴素的想法是：如果能够将塔座X的上面n-1个圆盘移至空闲的塔座Z上，并且这n-1个圆盘要求以原顺序叠排。这样，塔座X上就只剩下一个最大的圆盘，如图1-3（b）所示。于是，便可以轻而易举地将最大圆盘放到塔座Y上，如图1-3（c）所示。余下的问题是如何将n-1个圆盘从塔座Z借助于空闲塔座X移到塔座Y上。相对于原始问题而言，现在要解决的问题的性质与原问题相同，但被移动的圆盘数目少了一个，是相对较小的问题。使用递归很容易写出求解此问题的算法。图1-3 汉诺塔问题
假定圆盘从小到大编号为1～n，移动圆盘的算法可以粗略描述如下：（1）以塔座Y为中介，将前n-1个圆盘从塔座X移到塔座Z上；（2）将第n个圆盘移到塔座Y上；（3）以塔座X为中介，将塔座Z上的n-1个圆盘移到塔座Y上。
注意，（1）和（3）求解的是移动n-1个圆盘的汉诺塔问题，在程序1-6求解汉诺塔问题的模拟程序中，它们分别表现为一次递归函数调用。【程序1-6】汉诺塔问题
例1-4 产生各种可能的排列
给定 n 个自然数{0，1，…，n-1}的集合，设计一个算法输出该集合所有可能的排列（permutation）。例如，集合{0，1，2}有6种可能的排列：（0，1，2），（0，2，1），（1，0，2），（1，2，0），（2，0，1），（2，1，0）。容易看到，n个自然数的集合有n！个不同的排列。下面以4个自然数的集合{0，1，2，3}为例，介绍一种求解此问题的简单递归算法。
由4个自然数组成的排列通过下列方式构造：（1）以0开头，紧随其后为{1，2，3}的各种排列；（2）以1开头，紧随其后为{0，2，3}的各种排列；（3）以2开头，紧随其后为{0，1，3}的各种排列；（4）以3开始，紧随其后为{0，1，2}的各种排列。
语句（1）中“紧随其后为{1，2，3}的各种排列”实质上是求解比原始问题少一个数的排列生成问题。相对原问题而言，这是一个同类子问题，但规模小一些。这也意味着可用递归算法求解这一问题。程序1-7描述这一算法，可用Perm（a，0，n）调用之。【程序1-7】排列产生算法1.4.3 归纳证明
证明一个定理不成立的最好方法是举一个反例。那么，如何证明一个程序是正确的?程序的正确性证明是一个非常困难的问题，一个完整的程序正确性证明过程常常比编写程序费时得多。两种最常见的证明方法是归纳法和反证法。下面我们采用非形式证明（informal proof）方式讨论算法的正确性问题。
先来看归纳法。对于无限对象集上的命题，归纳法往往是唯一可行的证明方法。递归数据结构的特性和递归算法问题常使用归纳法证明。在多数情况下，归纳法在自然数或正整数集合上进行，当归纳法应用于递归定义的数据结构（如树和表）时，称为结构归纳法（structural induction）。下面将看到，递归函数和归纳证明二者在结构上非常类似，这对于运用归纳法证明复杂的递归数据结构和算法命题是很有帮助的。
程序1-5和程序1-6分别是逆序打印正整数和汉诺塔问题的递归函数。对于给定的一些测试用例，它们都能正确工作，但并不意味着它们一定是正确的程序。程序正确性证明是非常有用的，只有证明是正确的程序才能确认该程序对所有输入都能得到正确的结果。
使用归纳法进行证明的过程由两部分组成。（1）基础情况（base case）确认被证明的结论在某种（某些）基础情况下是正确的。（2）归纳步骤（induction step）这一步又可分成两个子步：首先进行归纳假设，假定当问题实例的规模小于某个量k时，结论成立；然后使用这个假设证明对问题规模为k的实例，结论也成立。至此，结论得证。
定理1-1 对于n≥0，程序1-5是正确的。
证明：（归纳法证明）
首先，当n是1位数时，程序显然是正确的，因为它仅执行了语句cout< 假定函数PrintDigit对所有位数小于k（k＞1）的正整数都能正确运行，当n的位数为k位时，此时有 n≥10，算法必定先执行语句 cout＜＜n%10；然后执行语句 if（n＞=10）PrintDigit（n/10）；。由于[2]是n的前k-1位数字形成的数，归纳法假设函数调用PrintDigit（n/10）能够将它正确地（并在有限步内）按数字的逆序输出，那么，现在先执行语句输出个位数字（n%10），然后由于按逆序输出前k-1位数字的做法是能够正确按逆序输出全部k位数字的，所以程序1-5是正确的。本例中，归纳证明使用的量是十进制数的位数。 上述证明看起来非常类似于对一个递归算法的描述。这正是由于递归和归纳是密切相关的，它们有很多相似之处。二者都是由一个或多个基础情况来终止的。递归函数通过调用自身得到较小问题的解，并由较小问题的解来形成相对较大的问题的解。同样，归纳法证明依靠归纳法假设的事实来证明结论。因此，一个递归算法比较容易用归纳法证明其正确性。 同样地，不难运用归纳法证明程序1-6汉诺塔程序的正确性，我们将其留做练习。 在本书的算法证明和分析中，还常运用反证法。为了使用反证法证明一个结论，首先应假设这个结论是错误的，然后找出由这个假设导致的逻辑上的矛盾。如果引起矛盾的逻辑是正确的，则表明假设是错误的，所以原结论是正确的。下面举一个经典的例子说明反证法的运用。 定理1-2 存在无穷多个素数。 证明：（反证法证明） 反面假设：假设定理不成立，则存在最大素数，记为P。令P，1P，…，P，P是从小到大依次排列的所有素数。设N=PP…PP2k-112k-1+1，显然N＞P，根据假设N不是素数。但P，P，…，P，P都不12k-1能整除N，都有余数为1。这就产生矛盾，因为每一个整数，或者自己是素数，或者是素数的乘积。现在N不是任何素数的乘积，这也意味着不存在最大素数，定理得证。 本章小结
本章概述有关算法、问题、问题求解过程及算法问题求解方法等贯穿本书的一些重要概念和方法。算法可以看做求解问题的一类特殊的方法，它是精确定义的，能在有限时间内获得答案的一个求解过程。对算法的研究主要包括如何设计算法，如何表示算法，如何确认算法的正确性，如何分析一个算法的效率，以及如何测量程序的性能等方面。算法设计技术是问题求解的有效策略。算法的效率通过算法分析来确定。递归是强有力的算法结构。递归和归纳关联紧密。归纳法是证明递归算法正确性和进行算法分析的强有力工具。
习题1
1-1 什么是算法?它与计算过程和程序有什么区别?
1-2 程序证明和程序测试的目的各是什么?
1-3 用欧几里得算法求31 415和14 142的最大公约数。估算一下程序1-2的算法比程序1-3的算法快多少倍?
1-4 证明等式gcd（m，n）=gcd（n mod m，m），对每对正整数m和n，m＞0都成立。
1-5 解释名词：问题、问题求解、问题求解过程、软件生命周期。
1-6 简述匈牙利数学家乔治·波利亚在《如何求解》一书中提出的思想，如何体现在算法问题求解过程中。
1-7 算法研究主要有哪些方面?
1-8 请举出至少一个算法问题的例子，说明因为数据组织方式不同，导致解题效率有显著差异。
1-9 试给出n！的递归定义式，并设计一个递归函数计算n！。
1-10 使用归纳法，证明上题所设计的计算n！的递归函数正确性。
1-11 请使用归纳法证明汉诺塔函数的正确性。
1-12 试用归纳法证明程序1-7的排列产生器算法的正确性。
1-13 写一个递归算法和一个迭代算法计算二项式系数：
1-14 给定一个字符串s和一个字符x，编写递归算法实现下列功能：（1）检查x是否在s中；（2）计算x在s中出现的次数；（3）删除s中所有x。
1-15 写一个C++函数求解下列问题：给定正整数n，确定n是否是它所有因子之和。
1-16 S是有n个元素的集合，S的幂集是S所有可能的子集组成的集合。例如，S={a，b，c}，则S的幂集={（），（a），（b），（c），（a，b），（a，c），（b，c），（a，b，c）}。写一个C++递归函数，以S为输入，输出S的幂集。[1]：① 运算符mod是对模数求剩余。设M＞0，x mod M的值在[0，M-1]中。使用C/C++语言的“%”运算符实现mod运算的方法为：x=x%M；if（x＜0）x=M+x。[2]：① 符号表示不大于x的最大整数，符号表示不小于x的最小整数。
第2章 算法分析基础
一旦确信一个算法是正确的，下一个重要的步骤就是分析算法。算法分析是指对算法利用时间和空间这两种资源的效率进行研究。本章讨论衡量算法效率的时间复杂度和空间复杂度，算法的最好、平均和最坏情况时间复杂度，讨论用于算法分析的渐近表示法，介绍如何使用递推关系来分析递归算法的方法及分摊分析技术。
2.1 算法复杂度
同一个问题可以编写多个算法来求解，这些算法所消耗的计算机资源（计算时间和存储空间）多少不同。算法的复杂度是指运行一个算法所需的时间和空间资源的量。2.1.1 什么是好的算法
人们总是希望算法具有许多良好的特性。一个好的算法应具有以下4个重要特性。（1）正确性（correctness）：毫无疑问，算法的执行结果应当满足预先规定的功能和性能要求。（2）简明性（simplicity）：算法应思路清晰、层次分明、容易理解、利于编码和调试。（3）效率（efficiency）：算法应有效使用存储空间，并具有高的时间效率。（4）最优性（optimality）：算法的执行时间已达到求解该类问题所需时间的下界。
算法的正确性是指在合法的输入下，算法应实现预先规定的功能和计算精度要求。与算法正确性直接相关的是程序的正确性。对于大型程序，人们无法奢望它“完全正确”，而且这一点也往往无法证实，这就引出对程序健壮性（robustness）的要求。程序健壮性是指当输入不合法数据时，程序应能做适当处理而不至于引起严重后果。一个程序也许不能做到完全正确，但可以要求它是健壮的。其含义是：当程序万一遇到意外时，能按某种预定方式做出适当处理。正确性和健壮性是相互补充的。正确的程序并不一定是健壮的，而健壮的程序并不一定绝对正确。一个可靠的程序应当能在正常情况下正确地工作，而在异常情况下，亦能做出适当处理，这就是程序的可靠性（reliability）。
注意，本书假定算法的输入都是合法输入，而不进行输入检测，但在算法的实际应用中，应当对输入数据实施必要的检测来保证程序的健壮性。
算法的简明性要求算法的逻辑清晰，简单明了，并且是结构化的，从而使算法易于阅读和理解，并易于编码和调试。算法的简明性没有严格定义的尺度可以度量，在很大程度上取决于审视者的眼光。但简明性并不是可有可无的特性，它是算法设计者需努力争取的一个重要特性，因为简单的算法往往更容易理解和实现，相应的程序也会因此而减少错误（bug）。此外，一个简单明了的算法就像一篇优美的说明文，令阅读者赏心悦目。但遗憾的是，简单的算法并不一定是高效的。
算法的效率是指执行一个算法所需的计算时间和存储空间。当程序规模较大时，算法的效率问题是算法设计必须面对的一个关键问题。必须重视算法的效率分析。然而为了换取一定的效率，牺牲算法的可读性，在现代程序设计中并不是明智之举。因此，算法设计者往往需要在算法的简明性和效率之间做出谨慎的选择。折中和结论（tradeoffs and consequences）是计算机学科的重要概念之一。
算法的最优性与所求解的问题自身的复杂程度有关。例如，对于在n个元素的集合中寻找一个最大元素的问题，分析表明，任何通过元素之间比较的方式来求解此问题的正确算法，至少需要进行n-1次元素间的比较运算。如果某人编写一个算法，声称他的算法对任意一个有n个元素的集合，仅需执行n-2次元素比较便可求得集合中的最大元素，那么，可以肯定，该算法不可能是正确的。如果一个实际的正确算法，在最坏情况下的确只需n-1次元素比较便可求得最大元素，那么它可称为最优的。因为n-1次元素比较是求最大元问题所需时间的下界。本书将讨论排序和查找问题的时间下界。然而遗憾的是，许多看似简单的问题，至今仍无法知晓求解该问题所需的时间下界是多少，如：矩阵乘法。2.1.2 影响程序运行时间的因素
一个程序的运行时间是程序运行从开始到结束所需的时间。影响程序运行时间的因素主要有：（1）程序所依赖的算法；（2）问题规模和输入数据；（3）计算机系统性能。
首先，很容易想到，对于同一程序和相同的输入数据，如果在不同的计算机上运行该程序，所需的运行时间几乎可以肯定是不同的。这是因为计算机的硬件性能可能不同，特别是处理器（CPU）速度可能相差很多。程序设计语言及其编译器不同，生成的目标代码的效率也会各异。操作系统也是影响计算机系统性能的因素之一。这就是说，算法运行所需的时间依赖于计算机软、硬件系统。
如果排除计算机的因素，假定在完全相同的计算机环境下运行程序，情况又如何呢?
很显然，求解同一个问题的不同算法，其程序运行时间一般不同。一个好的算法运行时间较少。算法自身的好坏对运行时间的影响是根本的和起决定作用的。例如，使用不同的排序算法对同一组元素进行排序，程序运行的时间通常是不相同的。
程序的一次运行是针对所求解问题的某一特定实例（instance）而言的。例如，执行一个排序算法，需要输入一组待排序的元素，对该组特定元素的排序是排序问题的一个实例。待排序的元素个数是一个排序问题实例的重要特征（characteristics），它直接影响排序算法的执行时间和所需的存储空间。因此，分析算法性能需要考虑的一个基本特征是问题实例的规模（size）。使用同一个排序算法对100个整数进行排序与对10 000个整数进行排序所需的时间很显然是不同的。
问题的规模一般是指输入数据的量，必要时也考虑输出数据的量。对于两个 m×n 矩阵加法问题的规模，通常考虑输入矩阵的元素个数，它正比于m×n；但对于一个由计算机随机生成并打印一个矩阵的算法来说，其运行时间与所生成的矩阵元素的个数有关，即与输出数据的量有关。还有一种情况，例如，现代密码算法需要进行超过200位长度的十进制数运算，显然算法的运行时间与输入（输出）数据的数值大小有关，此时，问题的规模必须考虑数据的数值大小。设x是这样的数，可以考虑以x的二进制形式表示的比特数[1]来度量x的数据量。数据的总输入量可以用各个数的长度之和来计算。
如果在同一个计算机系统上运行同一个程序，问题实例的规模也相同，则运行时间是否就一定相同呢?一个熟悉的例子是使用冒泡排序算法分别对100个已从小到大有序的整数排序，以及对随机选择的100个整数进行排序，它们所需的排序时间通常是不同的。这就是说，问题的规模相同，输入数据的状态（如排列次序）不同，所需的时间开销也会不同。2.1.3 算法的时间复杂度
1.抽象机模型
从上面讨论可以看到，一个程序运行的时间与计算机系统的性能有关。为了消除计算机因素对算法分析的影响，现假定算法（程序）运行在一台抽象的计算机模型上，它不依赖于实际的计算机软、硬件系统。设抽象机提供由m个基本运算（也可称为语句）组成的运算集O={O，O，…，O}，每个运算都是基本的，它们的执行时间是有12m限常量。同时设执行第i个运算O所需的时间是α，1≤i≤m。因此，一ii个算法对于给定输入在抽象机上的一次执行过程，表现为执行一个基本运算的序列。
2.时间复杂度
一个算法的时间复杂度（time complexity）是指算法运行所需的时间。
设有一个在抽象机上运行的算法 A，I是某次运行时的输入数据，其规模为 n，则算法 A的运行时间T是n和I的函数，记做T（n，I）。又设在该次运算中抽象机的第i个基本运算O的执行次数为β，1≤iii≤m，β也是n和I的函数，记做β（n，I）。那么，算法A在输入为I时ii的运行时间是：
这就是算法的时间复杂度。式中，输入数据I代表问题的一个实例，n是问题的规模。
3.最好、最坏和平均时间复杂度
前面提到，对于许多算法，即使问题的规模相同，如果输入数据I不同，算法所需的时间开销也会不同。
例如，在一个有n个元素的数组中查找一个指定元素，某个搜索算法从第一个元素开始，一次检查一个数组元素。如果待查元素恰好是第一个元素，则所需的查找时间最短，这就是算法的最好情况（best case）。如果待查元素是最后一个元素，所需的查找时间最长，则是算法执行时间的最坏情况（worst case）。如果需要多次在数组中查找元素，并且假定以某种概率查找每个元素，最典型的是以相等概率查找每个元素，在这种情况下，就会发现算法需平均检索约n/2个元素，这是算法时间代价的平均情况（average case）。
本书使用B（n）、W（n）和A（n）分别表示算法的最好、最坏和平均情况时间复杂度。设I∈D，D是规模为n的所有合法输入的集nn合，并设I′和I*分别是D中使得算法运行有最好和最坏情况的实例n（输入数据），P（I）是实例I（I∈D）在具体应用中被使用的概率，n则算法的上述三种情况时间复杂度可分别定义如下：
这三种时间复杂度从不同角度反映算法的效率，各有用途，也各有局限性。其中，比较容易分析和计算，并且也最有实际价值的是最坏情况时间复杂度。在本书中，算法分析的重点也主要集中在对最坏情况时间复杂度的分析和计算上。
还有一种类型的时间效率称为分摊效率。它并不针对算法的单次运行，而是计算算法在同一数据结构上执行一系列运算的平均时间。也许单次运算的时间代价较高，但n次运算的总运行时间除以n的平均时间效率并不差，这就是分摊效率。关于分摊效率将在稍后做深入讨论。2.1.4 使用程序步分析算法
从上面讨论可知，程序运行时间不仅与算法的优劣和输入数据直接相关，还与运行程序的计算机软、硬件环境有关。为了分析算法的效率，总希望略去计算机系统因素，对算法自身的特性进行事前分析（priori analysis），即在算法实际运行前分析算法的效率。这种分析结果显然不可能是程序运行时间的具体值，而是运行时间的一种事前估计。算法的事后测试（posteriori testing）是通过运行程序，测试一个程序在所选择的输入数据下实际运行所需要的时间。
前面关于算法时间复杂度的概念是在抽象机模型上定义的。对于用程序设计语言书写的算法，应如何分析其时间复杂度呢?可以设想，如果我们将程序设计语言中的循环语句的执行过程，视为其循环体（其中不嵌套循环）的重复执行过程，并对每次函数调用单独计算它的时间。那么，就可将抽象机模型上定义的概念用于分析由具体程序设计语言描述的算法。对于用C/C++语言描述的算法，可将每种可执行语句（除循环语句外）看成一种基本运算；对于循环语句，需计算其循环体的执行次数。这就可以通过一个算法在给定输入下所执行的总的语句条数来计算算法的时间复杂度。下面定义的程序步概念可进一步简化算法分析。它并不直接计算总的语句执行条数，而是将若干条语句合并成一个程序步来计算。
一个程序步（program step）是指在语法上或语义上有意义的程序段，该程序段的执行时间必须与问题实例的规模无关。
现以程序2-1求数组元素之和为例来说明如何计算一个算法的程序步数。设n个元素存放在一维数组list中，count是全局变量，用来计算总的程序步数。在程序中，语句count++；与数组求和的算法无关，只是为了计算程序步数而添加的。忽略所有count++；语句，便是一个数组求和程序。可以看到，这里被计算的每一程序步的执行时间，均与问题实例的规模n（数组元素的个数）无关。该程序的总程序步数为2n+3。【程序2-1】求数组元素累加之和的迭代程序
程序2-2是求数组元素之和的递归程序。为了确定这一递归程序的程序步，首先考虑当n=0时的情况。很明显，当n=0时，程序只执行if条件判定和第二个return语句，所需的程序步数为2。当n＞0时，程序在执行if条件判定后，将执行第一个return语句。此return语句不是简单返回，而是在调用函数RSum（list，n-1）后，再执行一次加法运算后返回。读者同样可以移去程序RSum中所有count++；语句，得到一般的数组求和递归程序。
设RSum（list，n）的程序步为T（n），RSum（list，n-1）的程序步为T（n-1），那么，当n＞0时，T（n）=T（n-1）+2。于是有：
这是一个递推关系式，它可以通过转换成如下和式来计算：
虽然从表面看来，程序RSum所需的程序步为2n+2，少于程序Sum的程序步2n+3，但这并不意味着前者比后者快，这是因为两者使用的程序步是不同的。递归调用引起的循环计算和使用for 语句的循环计算所需的开销是不同的，递归需要耗费更多的时间和空间资源。有关递归算法及其分析方法将在本章稍后及以后章节中做进一步讨论。【程序2-2】求数组元素累加之和的递归程序2.1.5 算法的空间复杂度
试读结束[说明：试读内容隐藏了图片]