作者：李清勇
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
算法设计与问题求解——编程实践试读：
前言
2006年3月，美国卡内基-梅隆大学计算机科学系主任周以真（Jeannette M.Wing）教授在美国计算机权威期刊《Communications of the ACM》上首先提出了计算思维（Computational Thinking）的概念。周教授认为：计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。计算思维是每个人的基本技能，不仅仅属于计算机科学家。我们应当使每个学生在培养解析能力时不仅掌握阅读、写作和算术（Reading，wRiting and aRithmetic，3R），还要学会计算思维。正如印刷出版促进了3R的普及，计算和计算机也以类似的正反馈促进了计算思维的传播，计算机逐渐成为了当今问题求解的最重要工具。
1.计算机与问题求解
在20世纪40年代，为了求解军事领域复杂的炮弹弹道计算问题，科学家发明了第一台电子计算机“埃尼阿克”（Electronic Numerical Integrator And Computer，ENIAC）。随着计算机计算能力的增强，计算机被广泛应用到了社会生活的各个领域。大到宇宙探测、基因图谱绘制，小到日常工作、生活娱乐，无不需要计算机的支持。
作为“问题求解的一个有力工具”，计算机尽管没有思维，只能机械地执行指令，但它运算速度快、存储容量大、计算精度高。如果能够设计有效的算法和程序，充分利用这些优点，计算机就能成为问题求解的一个利器。
运算速度快是计算机最重要的特点之一。很多问题尽管比较复杂，但仍然存在求解的方法，只是这些方法往往计算量比较大，计算过程较为烦琐，人们难以在可以接受的时间内手工求解。【例】用1，2，3，4，5，6，7，8，9这9个数字拼成一个9位数，每个数字使用一次且仅用一次，要求得到的9位数的前3位、中间3位和最后3位构成的3位数的比值为1∶2∶3。例如192∶384∶576就是一个符合该要求的数，因为192∶384∶576=123。
对于这样的问题，很容易想到的一个求解方案是：列举所有可能的9位数123456789，…，987654321，并逐个验证是否符合比值要求。理论上，这是一个可行的办法，可是几乎没有人愿意这样做。因为这样的9位数总共有9！=362880个，即使每秒验证一个数（对于人工验证，这已经是很快的速度了），也需要100多个小时。
但是，计算机实现同样的“笨方法”效果就大不一样。考虑用一个数组d保存9位数的各位数字，x，y，z分别代表前3位数、中间3位数和最后3位数，用STL中的函数next_permu-tation计算9个数字的下一个排列。当某个排列（即一个9位数）满足比例要求x∶y∶z=123时，则输出该9位数。下面是解决此问题的C++代码，在普通的PC上运行该程序，需要的时间还不到0.1秒。
存储容量大是计算机的另一个重要特点。人们很容易记住10以内的两个数的乘积，也就是小学数学中的“九九乘法表”。但如果要求人们记住100以内的任意两个数的乘积，普通人可能会觉得“记忆”不够。但对于计算机来说，这真是“小菜一碟”，一个100×100的二维数组就可以把“百百乘法表”保存下来。
人们常说的内存、硬盘、光盘、U盘等都是存储器，可以通俗地理解为计算机的记忆部件。容量的基本单位是字节（Byte），记为B。其他单位有KB（1KB=1024B）、MB（1MB=1024KB）、GB（1GB=1024MB）等。容量越大，可以存储的数据就越多，其“记忆力”就越强。“百百乘法表”如果用一个100×100的二维int型整数（假设一个int型整数占2字节）数组保存，它仅仅需要占用20 000字节（少于20KB）的空间。相比现在计算机动辄数GB的内存容量来说，“百百乘法表”的存储开销微不足道。
需要特别指出的是，运算速度快、存储容量大仅仅是计算机硬件系统的两个突出特点。在实际问题求解过程中，只有硬件平台还远远不够，人们需要针对问题设计不同的算法，并把算法转化为计算机可以运行的程序。
2.计算机问题求解的知识体系
计算机问题求解的本质是把特定领域中特定问题的求解过程转换为计算机可以执行的程序。在这个转换过程中，除了必要的专业知识外，问题求解者还需要掌握计算机算法设计方面的知识，主要包括高级程序设计语言、数据结构和算法。这些知识构成了计算机问题求解的核心知识体系。
在计算机教学体系中，高级程序设计语言、数据结构、算法是相互承接的课程系列。从计算机问题求解的角度看，这三门课程的知识相互交叉、相互支撑。高级程序设计语言和数据结构是算法设计的基础，高效的算法和数据结构需要用某种高级程序设计语言来实现；一个好程序不仅需要“编程小技巧”，更需要合理的数据结构和高效的算法。
程序设计语言是问题求解的基本工具。随着计算机技术的发展，程序设计语言经历了一个从低级程序设计语言到高级程序设计语言的发展历程。机器语言和汇编语言等面向特定的体系结构和指令系统，在计算机发展的早期应用较多。随着形式语言理论、编译技术的发展，与目标机器无关的高级程序设计语言（如C/C++，Java等）逐渐成为程序设计的主流。本书约定的程序设计语言是C/C++。需要注意的是，程序设计语言并不等于程序设计，程序设计的目的是表达程序设计者的思想，按照计算机所能理解的方式描述需要让计算机完成的工作，而程序设计语言只是表达这种思想的工具。程序设计的关键之处在于明确数据在计算机中的表达形式，以及确定如何将输入转化为输出的一系列计算步骤，而这些都需要数据结构和算法理论的指导。
数据结构是问题求解的基础要素。数据是信息的载体，无论是待求解问题的输入/输出，还是问题求解过程中产生的中间量；无论是简单的量，比如单个数值，还是复杂的对象，它们在计算机中都以数据的形式进行存储。在问题求解时，为满足数据存储的结构化要求并提高程序执行效率，人们首先面临的问题是怎样合理地组织、存储和加工这些数据。常用的数据结构有线性表、栈、队列、树、二叉树、图、哈希表（散列表）等。数据结构的设计和应用不是一个教条化的生搬硬套过程，同一个问题也许可以运用不同的数据结构求解，而且它们求解的效率往往不尽相同。另外，有些问题可能没有现成的数据结构直接套用，需要人们综合运用基本数据结构组合成新的数据结构。无论是已有数据结构的选择还是新数据结构的设计，人们都需要应用算法设计与分析方面的知识。
算法设计是问题求解的关键要素。简单地说，算法可以理解为把将问题输入转化为问题答案的一系列计算步骤。算法必须满足正确性与复杂性要求。首先，算法执行结果必须正确，它能正确无误地把每一个问题实例的正确答案求解出来。其次，算法的复杂度要适中。计算机系统的资源（包括运行时间和存储空间）是有限的，因此算法必须在有限的资源条件下正确地求解问题。同样的问题，某些算法执行结果可能不正确，某些算法执行结果则正确无误。即使执行结果都正确的不同算法，它们的执行效率可能也不尽相同，如有些算法需要几个小时，甚至几天，有些算法却仅仅需要几秒钟或几分钟。算法设计是一个灵活的、创造性的过程，甚至可以认为是一个艺术创造过程。有些算法是现实生活中人们解决问题时所用办法的升华和抽象；有些算法是数学理论和数学模型的体现和具体化。人们需要掌握经典的算法思想及其应用技巧，也要学会怎样针对特定问题设计和创造新算法。
3.本书的内容和结构
本书是一本讲述怎样综合运用算法设计理论和技术进行问题求解的实践教材，主要讲述算法设计原理和方法，对运用算法求解问题时涉及的C/C++程序设计细节，尤其是影响算法准确性和复杂性的编程要点和技巧也进行了详细阐述。数据结构往往是算法设计和实现的基础，特别是一些高级数据结构，其本身就体现了很强的算法思维，因此本书不仅仅单独设立一章讲述数据结构，在讨论具体算法时也会交叉讨论相应的数据结构知识。本书包括7章，组织如下：
第1章介绍问题求解和算法的基本概念，然后着重阐述了算法复杂度分析的基本理论和方法。
第2章介绍程序设计和数据结构相关内容，程序设计和数据结构是算法设计的重要支撑，本章重点介绍了程序设计的三个盲点，以及常用的基本数据结构及其用法。
第3章介绍枚举算法。“大道至简”，枚举算法是一种最朴素最简单的算法思想，但在具有卓越运算速度的计算机系统中，它却是常常被忽视的问题求解利器。本章重点阐述了怎样直接和间接运用枚举算法求解问题。
第4章介绍递归和分治算法。“凡治众如治寡，分数是也”，分治策略是分析和解决复杂问题最常用的策略之一。本章根据分治算法的求解步骤，将分治策略归纳为三类，并结合具体实例阐述每类策略的设计思想、适用范围及实现要点。
第5章介绍动态规划算法。动态规划算法是最具有创造性的一种算法，归约、分治等思维方法都在动态规划算法框架中得到了很好的体现。本章重点讨论基于“划分”和“约简”策略的动态规划算法原理和运用技巧。
第6章介绍贪心算法。这种类似于“瞎子爬山”的策略，如果运用适当，能够快速地产生最优解。本章给出了一些典型的贪心算法问题，并探讨了贪心算法的适用范围。
第7章介绍搜索算法。搜索是求解一些难解问题的常用策略，它把问题求解转换为状态空间图中的路径探索过程，究其本质，搜索是一种枚举和优化策略的综合算法。“运用之妙，存乎一心”，本章以典型问题为例阐述5种经典搜索策略的原理、适用范围以及实现要点。
为便于教学和读者自学，本教材提供有适用于理论教学的课件以及实践学习的配套平台——“北京交通大学在线程序评测系统”（http：//acm.bjtu.edu.cn/OnlineJudge，简称BOJ）。BOJ是一个公益性质的计算机问题求解实践平台，也是本书的配套网站。本书的例题和习题都以专题的形式加入BOJ题库中，读者在学习本书时，可登录该系统进行编程求解和自我评测。
第1章 计算机问题求解概述
学习要点
● 理解问题和问题实例的概念
● 了解问题求解的基本步骤
● 了解算法空间复杂性分析的方法
● 掌握算法时间复杂性分析的方法
从第一台电子计算机“埃尼阿克”诞生，计算机就成为了复杂问题求解的最重要工具。但是计算机没有思维，不能自主解决问题，而只能机械地执行程序。程序是算法用某种程序设计语言的实现结果，怎样设计正确和高效的算法是计算机问题求解的核心。计算机问题求解周期包括哪些重要的步骤?如果给定的问题存在多个算法，我们怎样评价这些算法的性能?另外，IT公司的工程师们日常讨论算法性能的语言或者“行话”是什么?
1.1 问题与问题实例
问题是需要人们回答的一般性提问，通常含有若干参数，由问题描述、输入条件以及输出要求等要素组成。
问题实例定义为确定问题描述参数后的一个对象。
一个问题的问题描述和输入条件通常包含若干参数，当给定这些参数的一组赋值后，则可以得到一个问题实例。一个问题可以包含若干个问题实例，问题和问题实例的关系类似于面向对象程序设计语言中类和对象的关系。【例1-1】 正整数求和问题。
问题描述： 计算正整数a与b的和c。
输入： 正整数a，b（1≤a，b≤10000）。
输出： 和c。
在正整数求和问题中，指定a=1，b=1，则构成了一个问题实例1+1；如果令a=1000，b=1000，则构成了另外一个问题实例1000+1000。
虽然对于正整数求和问题，两个问题实例之间的差别不大，但是，对于有些问题，不同问题实例无论是其描述还是求解的复杂性差别都非常大。【例1-2】 迷宫问题。
问题描述： 在一个N×N的棋盘迷宫中，有些格子能通行（用1表示），有些格子不能通行（用0表示），假定棋盘位置（1，1）为入口，（N，N）为出口，且在棋盘中只能横向或者竖向移动。任意给定一棋盘，试问是否存在从入口到出口的路径。
输入： 正整数N表示棋盘的大小，以及N×N的0-1矩阵表示每个棋盘格子的状态。
输出： 1，表示存在路径；0，表示不存在。
在迷宫问题中，当N=2，棋盘布局如图1-1（a）所示（黑色格子表示0，白色格子表示1）时，得到一个问题实例（a）。当N=10000，棋盘布局如图1-1（b）所示时，得到另外一个问题实例（b）。显然，求解问题实例（b）比求解问题实例（a）更加复杂。在棋盘大小（如N=10000）相同而布局不同的情况下，求解的复杂性也可能不一样。比如在图1-1中的实例（b），（c），（d）中，采用从入口到出口的广度优先搜索算法（搜索技术参阅第7章），实例（b）所需要的时间会比实例（c）要多，实例（d）所需要的时间也会比实例（c）要多。如果采用从出口到入口的广度优先搜索算法，实例（d）所需要的时间比实例（b）和实例（c）要少得多。图1-1 迷宫问题的不同问题实例
值得注意的是，在问题求解时，一个算法能正确而有效地求解某一个问题，严格意义上是指该算法对于该问题的所有问题实例都能正确而有效地得到答案，而不是指该算法能正确而有效地求解某一个或者某几个问题实例。
1.2 计算机问题求解周期
在具体讨论问题求解之前，先看看数学家G·波利亚在1944年提出的“怎样解题表”：
……
你以前见过它吗?你是否见过相同的问题而形式稍有不同?
你是否知道与此有关的问题?你是否知道一个可能用得上的定理?
看看未知数！试想出一个具有相同未知数的或相似未知数的熟悉的问题。
这里有一个与你现在的问题有关，且早已解决的问题。
你能不能利用它?你能利用它的结果吗?你能利用它的方法吗?为了能利用它，你是否应该引入某些辅助元素?
你能不能重新叙述这个问题?你能不能用不同的方法重新叙述它?
回到定义去。
如果你不能解决所提出的问题，可先解决一个与此有关的问题。你能不能想出一个更容易着手的有关问题?一个更普遍的问题?一个更特殊的问题?一个类比的问题?你能否解决这个问题的一部分?……如果需要的话，你能不能改变未知数或数据，或者二者都改变，以使新未知数和新数据彼此更接近?
……
尽管这张表是为解决数学问题而设计的，但是它对计算机问题求解具有深刻的启迪意义，在问题求解时离不开类似的分析问题的思维方法。
在设计算法求解特定问题时，算法的准确性和复杂性往往是人们关注的重点。首先，算法执行的结果必须正确。算法正确是指对于问题界定的所有问题实例，算法执行后都能得到正确的结果。其次，算法的复杂性要适中。计算机的资源（包括时间和内存）是有限的，所以，算法必须在有限的资源条件下正确地求解问题，更多有关算法复杂性分析的讨论见1.4节。可见，用计算机算法求解问题不是一个很容易的过程。
实际上，从一个问题的提出，到计算机可执行的、满足准确性和复杂性要求的程序实现，可以看作是计算机问题求解的一个周期。问题求解周期包括问题简化、模型构建、算法设计、程序设计与调试等过程。
问题简化：大多数实际问题涉及的因素很多，在求解之前必须经过简化，得到问题的原型（Prototype）。这个原型应当是没有歧义的，可以用1.1节介绍的“问题描述–输入–输出”标准方法加以定义（本书所讨论的问题都以原型的形式出现）。
模型构建：问题的原型简洁地叙述了问题的条件、限制和求解目标，但是没有表明问题的本质。很多表面上看起来完全不同的问题具有相同的本质。模型构建是一个非常灵活的过程，同一个问题可以构建不同的模型，模型求解的难度也有差异。
得到数学模型以后，只要不是简单到可以直接求解或者套用经典模型的程度，一般都需要进行模型分析，得到初步结论。很多经典模型前人已经做过详细而透彻的研究，学习算法时应当尽量多地积累这样的经典模型及其求解算法。另一方面，如果模型是新的，需要继续进行算法设计，这一步往往比构建模型更有挑战性。
算法设计：由于问题答案最终需要由计算机执行得到，因此，在模型构建和分析后要进行算法设计。这是本书探讨的重点，也是计算机问题求解的核心要素。
程序设计与调试：这是用特定程序设计语言实现算法的过程，属于程序设计的范畴。
例1-3展示了一个实际问题的求解过程。【例1-3】补丁与Bug问题。
Bug就是人们所说的错误。用户在使用软件时总是希望其错误越少越好，最好没有错误。但是推出一个没有错误的软件几乎不可能，所以很多软件公司都在不断地发布补丁（有时这种补丁甚至是收费的）。T公司就是其中之一。上个月，T公司推出了一个新的字处理软件，随后发布了一批补丁。最近T公司发现其发布的补丁有致命的问题，那就是一个补丁在排除某些错误的同时，往往会加入另一些错误。此字处理软件中只可能出现n个特定的错误，这n个错误是由软件本身决定的。T公司目前共发布了m个补丁，对于每一个补丁，都有特定的适用环境，某个补丁只有在当前软件中包含某些错误而同时又不包含另一些错误时才可以使用，如果它被使用，它将修复某些错误而同时加入其他错误。另外，使用每个补丁都要耗费一定的时间（即补丁程序的运行时间）。
现在T公司的问题很简单，其字处理软件的初始版本不幸地包含了全部n个错误，有没有可能通过使用这m个补丁（任意顺序地使用，一个补丁可使用多次），使此字处理软件成为一个没有错误的软件。如果可能，希望找到总耗时最少的方案。
显然，这是一个比较复杂的实际问题，在求解之前，需要我们对该问题进行适当的简化和较为形式化的定义，得到如下问题原型。
问题描述： 将T公司的字处理软件中可能出现的n个错误记为集合B={b，b，…，b}，发布的m个补丁记为集合P={p，p，…，p}。12n12m对于每一个补丁p，假设存在错误集合B和B-。当软件包含了B中ii+ii+的所有错误，而没有包含B-中的任何错误时，补丁p才可以被使用，ii否则不能使用，显然B和B-的交集为空。补丁p将修复某些错误而同i+ii时加入某些错误，设错误集合为F和F-，使用过补丁p之后，F-中的i+iii任何错误都不会在软件中出现，而软件将包含F中的所有错误，同i+样F和F-的交集为空。另外，使用每个补丁都要耗费一定的时间T。i+ii
现在T公司的字处理软件的初始版本不幸地包含了全部n个错误，试编写程序判断有没有可能通过使用这m个补丁（任意顺序地使用，一个补丁可使用多次），使此字处理软件成为一个没有错误的软件。如果可能，希望找到总耗时最少的方案。
输入格式： 第一行有两个正整数n和m，n表示Bug总数，m表示补丁总数，1≤n≤15，1≤m≤100。接下来m行给出了m个补丁的信息。每行包括一个正整数T（表示此补丁程序p的运行耗时）和两个长度ii为n的字符串，中间用一个空格符隔开。
第一个字符串，如果第k个字符为“+”，则表示b属于B；若字ki+符为“-”，则表示b属于B；若字符为“0”，则b既不属于B也不属ki-ki+于B，即软件中是否包含b不影响补丁p是否可用。i-ki
第二个字符串，如果第k个字符为“+”，则表示b属于F；若字ki+符为“-”，则表示b属于F；若字符为“0”，则b既不属于F也不属ki-ki+于F，即软件中是否包含b不会因使用补丁p而改变。i-ki
输出格式： 输出一个整数，如果问题有解，输出总耗时，否则输出0。
经过上述的问题简化得到问题原型后，下一步就是对该问题进行分析，构建相应的模型。客观世界是纷繁复杂的，当人们面对一个新问题时，通常的想法是通过分析、变形和转换，得到本质相同且熟悉的问题，这就是归化思想。如果把初始的问题或对象称为原型，则把归化后的相对定型的模拟化或理想化的对象称为模型。模型化的方向主要有图论模型、数学模型和规划（动态规划）模型。
因为补丁与Bug问题涉及耗时“最少”的要求，自然可以联想到图论中的最短路径问题。如果把n个Bug的状态（存在和不存在）的组合用一个0-1字符串表示（称为模式串），显然，所有n个Bug构成n的模式串的数目最多是2个，同时，运行一个补丁就会导致从一个模式串转换到另外一个模式串。如果把模式串组成一个图模型的顶点，那么特定的补丁就构成该图的有向边，该补丁运行的时间则是该边的权重，如图1-2所示。当构建完补丁与Bug问题的图模型后，原问题的解就对应了从起点模式串（11111）到终点模式串（00000）的一条最短路径。图1-2 补丁与Bug问题的图模型示例
其中每个顶点都表示软件的状态，0-1字符串中的1表示对应Bug存在，0表示对应Bug不存在，每一条边表示一个补丁，边的权重表示执行补丁所需要的时间，虚线所示的路径则是该示例的最优解。
接下来就是针对补丁与Bug的图模型设计求解算法。对于学过图论的读者应该很容易想到，此问题可以直接应用Dijkstra最短路径算法求解。鉴于Dijkstra最短路径算法的典型性，Dijkstra算法的程序设计和调试的过程请读者自己完成。
另外，补丁和Bug问题也可以应用有限状态自动机模型，但是基于该模型的求解过程会复杂些，学有余力的读者可以自己设计和实现。
1.3 算法与程序
算法（Algorithm）是计算机问题求解的核心和关键。虽然人们对算法一词非常熟悉，但到目前为止，对于算法尚没有统一而精确的定义。有人说：算法就是一组有穷的规则，它们规定了解决某一特定问题的一系列运算。而Thomas H.Cormen等人在《Introduction to Algorithms》一书中将算法描述为：算法是任何定义好了的计算程式，它取某些值或值的集合作为输入，并产生某些值或值的集合作为输出。因此，算法是将输入转化为输出的一系列计算步骤。概括起来，算法有以下5个特性：（1）确定性。算法的每一种运算（包括判断）必须有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的。（2）可实现性。算法中有待实现的运算都是相当基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成。（3）具有数据输入。一个算法有零个或多个数据输入，它们是在算法开始之前对算法最初赋予的量，这些输入取自特定的对象集合。（4）具有数据输出。一个算法产生一个或多个输出，它们是同输入有某种特定关系的量。（5）有穷性。一个算法必须在执行了有穷步之后终止。
程序（Program）是算法用某种程序设计语言的实现结果。程序可以不满足算法的第5个特性。例如操作系统，它是一个无限循环中执行的程序，因而不是一个算法。当然，如果把操作系统按照任务分解成一些独立的问题，每一个问题则由操作系统中的一个子程序通过特定的算法来实现。
1.4 算法复杂性分析
算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法复杂性的高低体现了运行该算法所需要的计算机资源的多少。算法执行所需的资源越多，则它的复杂性越高；反之，算法所需的资源越低，则其复杂性越低。时间和空间（即内存）是计算机最重要的两种资源，因而算法的复杂性分为时间复杂性和空间复杂性。
不言而喻，对于任意给定的问题，复杂性尽可能低的算法是问题求解时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是选用算法时应遵循的一个重要准则。总之，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
1.4.1 空间复杂性
算法的空间复杂性是指计算机执行一个算法所需要占用的存储空间，它是算法优劣的重要度量指标。一般地，空间复杂性越小，算法越好。算法执行需要的空间包括指令空间，数据空间和系统栈空间三大类。
指令空间用来存储经过编译之后的程序指令。程序所需的指令空间的大小取决于如下因素：① 把程序编译成机器代码的编译器；② 编译时实际采用的编译器选项；③ 目标计算机。程序编译时使用的编译器不同，产生的机器代码的长度就会有差异。另外，有些编译器带有选项，如优化模式、覆盖模式等，如果设置的编译选项不同，产生机器代码也会不同。当然，目标计算机的配置也会影响代码的规模。例如，如果计算机具有浮点处理的硬件部件，那么每个浮点操作可以转化为一条机器指令；否则，必须生成仿真的浮点计算代码，使整个机器代码加长。一般情况下，指令空间对于所解决的特定问题不够敏感，以至于可以忽略不计。
数据空间用来存储所有常量和变量的值，分成两部分：① 存储常量和简单变量；② 存储复合变量。前者所需的空间取决于所使用的计算机和编译器，以及变量与常量的数目。因为人们往往是计算所需内存的字节数，而每字节所占的数位依赖于具体的机器环境（16位字长计算机中C/C++各数据类型所需内存参阅表2-1）。后者包括数据结构所需的空间及动态分配的空间。结构变量所占空间等于各个成员所占空间的累加；数组变量所占空间等于数组大小乘以单个数组元素所占的空间。
系统栈空间保存函数调用返回时恢复运行所需要的信息。当一个函数被调用时，下面数据将被保存在系统栈中：① 返回地址；② 所有局部变量的值、递归函数的传值形式参数的值；③ 所有引用参数以及常量引用参数的定义。对于递归程序调用，系统栈空间大小还依赖于递归调用的深度，而且，往往这是决定系统栈空间大小的主要因素。
程序1-1 数组求和程序
在程序1-1中，程序sum1采用循环累加的办法，而程序sum2采用递归的办法。在sum1中，int型变量i，iSum，iLen各自需要分配4字节（在16位字长计算机为2字节）内存空间，指针型参数iArray需要分配4字节内存空间。在sum2中，递归栈空间包括参数iArray，iLen所需的8字节，以及保存返回地址所需的2字节（假定是near指针）。每次调用sum2就需要10字节空间，假定某一个实例的递归深度是n，则总共需要10×（n+1）的内存空间。
随着半导体技术的飞跃式发展，存储器资源的成本越来越低，人们对于算法空间复杂性的关注度也越来越低。因此，本书后续章节分析算法的复杂性时，也忽略了空间复杂性分析。
1.4.2 时间复杂性
1.4.2.1 时间复杂性的表示算法的时间复杂性是指算法运行所需要的时间资源的量，从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模（N）、算法的输入（I）和算法本身（A）的函数。比如，在例1-2的迷宫问题中，棋盘的大小N反映了迷宫问题的求解规模，某一个特定的棋盘布局则表示了迷宫问题的输入。显然，用某一个特定算法A求解该问题时，求解图1-1（a）所示问题实例和图1-1（b）所示问题实例所需的时间不一样。一般地，问题规模N越大，所需要的时间就越多。即使在问题规模N相同的情况下，求解不同输入所对应的问题实例所需要的时间也不一样，比如，应用普通广度优先搜索算法求解图1-1（b）和图1-1（c）的问题实例所需要的时间也不尽相同。
不失一般性，如果分别用N，I和A来表示算法要解问题的规模、算法的输入和算法本身，用T表示算法的时间复杂性，那么应有
式中，T（N，I，A）是N，I和A的一个确定的三元函数。通常，人们让A隐含在复杂性函数名当中，于是公式（1-1）可以简写为
运行于特定计算机的算法程序由该计算机系统的若干操作和运算指令组成，显然，运行算法所需要的时间等价于执行这些指令所需要的时间之和。因为不同的计算机其指令以及执行指令所需要的时间不一定相同。不失一般性，假定算法运行在一台抽象的计算机上，此抽象的计算机提供k种元运算，分别记为O，O，…，O；再设这些元12k运算每执行一次所需要的时间分别为t，t，…，t。给定算法A，设12k经过统计，用到元运算O的次数为e，i=1，2，…，k，显然对于每一ii个i，1≤i≤k，e是N和I的函数，即e=e（N，I）。那么得到算法执行时iii间的表达式：
式中，t，t，…，t是跟N和I无关的常量。12k
对于任何一个问题，对应于特定规模N的问题实例通常都比较多，甚至大得无法计量。比如，迷宫问题的规模N=1000时，其对应的问1000×1000题实例则有2个。显然，不可能对规模N的每一种合法输入I都统计e（N，I），i=1，2，…，k。因此T（N，I）的表达式还得进一i步简化，或者说，只在规模为N的某些或某类有代表性的合法输入中统计相应的e（N，I），i=1，2，…，k，评价其时间复杂性。i
下面只考虑三种情况的时间复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为T（N），T（N）和maxminT（N）。在数学上有avg*
式中，D是规模为N的合法输入的集合；I是D中一个使T（N，NN*I）达到T（N）的合法输入，I～是D中一个使T（N，I～）达到maxNT（N）的合法输入；而P（I）是在规模为N的问题实例集合中出min现输入I的概率。
以上三种情况下的时间复杂性各从某一个角度来反映算法的效率，各有各的用处，也各有各的局限性。但实践表明可操作性最好的、最有实际价值的是最坏情况下的时间复杂性。最好情况和平均情况下的时间复杂性分析一般应用于理论研究。本书对算法时间复杂性的分析主要放在最坏情形上。1.4.2.2 渐近时间复杂性及其阶
虽然式（1-4）严格定义了算法在最坏情况下的时间复杂性，但是，在问题求解过程中按照式（1-4）去分析和计算算法的时间复杂性是不可行的。首先，随着社会的进步和科学研究的深入，要求用计算机解决的问题越来越复杂，规模越来越大，导致严格定义的最坏情况的时间复杂性T（N）形式会非常复杂；其次，问题的复杂性导max致算法和程序结构的复杂性，如果把算法中所有的运算都考虑进去，那么式（1-4）的求解可能会比原问题的求解更困难。本质上，时间复杂性并不是表示一个程序解决某个问题需要花多少时间，而是当问题规模扩大后，程序需要的时间量增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定问题实例的效率不能衡量一个程序的好坏，而应该看当这个问题的规模变大到若干倍后，程序运行时间是否还是一样，或者也跟着慢了若干倍，或者变慢了更多倍。因此，对于规模充分大，结构又十分复杂的问题的求解算法，其复杂性分析需要进行合理的简化。
首先，引入复杂性渐近性态的概念。设T（N）是前面定义的关于算法A的复杂性函数。一般来说，当N单调增加且趋于∞时，T（N）也将单调增加趋于∞。对于T（N），如果存在T′（N），使得当N→∞时有
那么，就说T′（N）是T（N）当N→∞时的渐近性态，或叫T′（N）为算法A当N→∞的渐近复杂性。在数学上，T′（N）是T（N）当N→∞时的渐近表达式。T′（N）是T（N）中略去低阶项所留下的主项。2所以它无疑比T（N）来得简单。比如当T（N）=5N+6NlogN+3N2++2时，T′（N）的一个答案是5N，因为这时有22
显然5N比5N+6NlogN+3N++2简单得多。
由于当N→∞时T′（N）渐近于T（N），我们有理由用T′（N）来替代T（N）作为算法A在N→∞时复杂性的度量。而且由于T′（N）比T（N）简单，这种替代明显地是对复杂性分析的一种简化。
进一步，考虑到分析算法的复杂性的目的在于比较求解同一问题的两个不同算法的效率，而当要比较的两个算法的渐近复杂性的阶不相同时，只要能确定出各自的阶，就可以判定哪一个算法的效率高。换句话说，这时的复杂性分析只要关心T′（N）的阶就够了，不必关心包含在T′（N）中的常数因子。所以，人们常常又对T′（N）的分析进一步简化，把计算机中的所有元运算做无差别处理，即假设算法中用到的所有不同的元运算各执行一次，所需要的时间都是一个单位时间。而且，在实际进行算法复杂性分析时，并不是每一个元运算的执行次数都需要统计，往往只需要计算算法中的“主要运算”，忽略了所选择主运算之外其他运算的开销。这样公式（1-4）可以简化为*
式中，e是算法的“主要运算”，I是输入实例集合中一个使p*T（N，I）达到T（N）的合法输入。max
通过上面的两个步骤，算法复杂性分析得到了极大的简化。实际上，算法复杂性分析只要考察当问题的规模充分大时，算法复杂性在渐近意义下的阶。与此简化的复杂性分析相配套，需要引入以下渐近意义下的记号：O，Ω，Θ。
以下设f（N）和g（N）是定义在正数集上的正函数。
渐近符号O的定义：如果存在正的常数C和自然数N，使得当N≥0N时有f（N）≤Cg（N），则称函数f（N）当N充分大时上有界，且0g（N）是它的一个上界，记为f（N）=O（g（N）），这时还说f（N）的阶不高于g（N）的阶。
例子：（1）存在C=5，N=1，对所有的N≥N有4N≤CN，则有004N=O（N）；（2）存在C=14，N=1，对所有的N≥N有2N+12≤CN，则有2N00+12=O（N）；22（3）存在C=17，N=20，对所有的N≥N有16N+19N+5≤CN，0022则有16N+19N+5=O（N）；23（4）存在C=4，N=5，对所有的N≥N有16N+19N+5≤CN，则0023有16N+19N+5=O（N）；32（5）作为一个反例N≠O（N）。假设等号成立，则存在正的常32数C和自然数N，使得当N≥N时有N≤CN，即N≤C。显然当取0032N=max{N，C+1}时这个不等式不成立，所以N≠O（N）。0
除了根据符号O的定义来计算一个函数的O表达式，大O比率定理提供了另外一种判定规则。
大O比率定理：对于函数f（N）和g（N），如果极限存在，则f（N）=O（g（N））当且仅当存在正的常数C，使得（f（N）/g（N））≤C。
证明： 略。
例子：（1）因为=3，所以3n+2=O（n）；2（2）因为=10，所以10n+4n2+2=O（n）；n2n（3）因为=6，所以6×2+n=O（2）；162n（4）因为=0，所以n+3×n=O（2）。
符号O是为了简化算法复杂度分析而采用的一种记号，有两点需要特别注意：
① 符号O定义的是一个算法当其问题规模充分大时算法复杂度的一个上界。根据符号O的定义不难推导，这个上界并不是唯一的。比232如，在例子（3）和例子（4）中，N和N都是16N+19N+5符合O定义的上界。显然，这个上界的阶越低则越接近算法复杂度的真实值，评估就越精确，结果就越有价值。
② f（N）=O（g（N））不一定能推导出g（N）=O（f（N）），因为两者并不等价。实际上，这里的等号并不是通常相等的含义。
按照符号O的定义，容易证明它有如下运算规则：（1）O（f）+O（g）=O（f+g）；（2）O（f）+O（g）=O（max（f，g））；（3）O（f）O（g）=O（f×g）。
下面按照符号O的定义，证明规则（1）。
设F（N）=O（f），根据符号O的定义，存在正常数C和自然数1N，使得对所有的N≥N，有F（N）≤Cf（N）。111
类似地，设G（N）=O（g），则存在正的常数C和自然数N使22得对所有的N≥N有G（N）≤Cg（N）。22
令C=max（C，C），N=max（N，N），对于任意自然数N≥312312N有3
其余规则的证明类似，请读者自行证明。
渐近符号Ω的定义： 如果存在正的常数C和自然数N，使得当N≥0N时有f（N）≥Cg（N），则称函数f（N）当N充分大时下有界，且0g（N）是它的一个下界，记为f（N）=Ω（g（N）），这时还说f（N）的阶不低于g（N）的阶。
类似于符号O，也存在符号Ω的如下判定规则。
大Ω比率定理：对于函数f（N）和g（N），如果极限（g（N）/f（N））存在，则f（N）=Ω（g（N））当且仅当存在正的常数C，使得（g（N）/f（N））≤C。
证明：略。
同样要指出，用Ω评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界的阶越高，则评估就越精确，结果就越有价值。这里的Ω只对问题的一个算法而言。如果它是对一个问题的所有算法或某类算法而言，即对于一个问题和任意给定的充分大的规模N，下界在该问题的所有算法或某类算法的复杂性中取，那么它将更有意义。这时得到的相应下界，我们称之为问题的下界或某类算法的下界。它常常与O配合以证明某问题的一个特定算法是该问题的最优算法，或者该问题在某算法类中的最优算法。
渐近符号Θ的定义： f（N）=Θ（g（N））当且仅当f（N）=Ο（g（N））且f（N）=Ω（g（N））。这时称f（N）与g（N）同阶。
同时，f（N）=Θ（g（N））等价于存在正的常数c，c和N，120使得对于所有的N≥N，有c（g（N））≤f（N）≤c（g（N））。即函012数f介于函数g的c和c倍之间，当N充分大时，g既是f的下界，又是f12的上界。同样，符号Θ也存在如下判定定理。
大Θ比率定理：对于函数f（N）和g（N），如果极限（g（N）/f（N））与（f（N）/g（N））都存在，则f（N）=Θ（g（N））当且仅当存在正的常数c，c，使得（g（N）/12f（N））≤c，（f（N）/g（N））≤c。12
比较大O比率定理和大Ω比率定理可知，大Θ比率定理实际是这两种情况的综合。对于多项式情形的复杂性函数，其阶函数可取该多项式的最高项，即有如下定理。mm-1
定理1： 对于多项式函数 f（N）=aN+aN+…+aN+a，mm-110如果a>0，则有mmmm
f（N）=O（N），f（N）=Ω（N），f（N）=Θ（N）1.4.2.3 时间复杂性渐近阶的意义
计算机的设计和制造技术在突飞猛进，一代又一代的计算机的计算速度和存储容量在直线增长。有人因此认为没有必要再去苦苦地追求高效率的算法，从而不必再去无谓地进行复杂性的分析。他们以为低效的算法可以由高速的计算机来弥补，以为在可接受的时间内用低效的算法完不成的任务，只要移植到高速的计算机上就能完成。这是一种错觉，造成这种错觉的原因是他们没看到：随着经济的发展、社会的进步、科学研究的深入，计算机求解的问题越来越复杂、数据规模越来越大。对低效算法来说，问题复杂程度和规模的线性增长导致的时耗的增长和空间的增长都会是超线性的。下面对效率上有代表性的几个档次的算法做些简单的分析对比。
假设求解某一个问题有5个不同算法，其时间复杂性阶分别为23NNN，N，N，2，3，让这5个算法在同一台计算机上运行，并且求解不同规模的问题实例（假定运行实例都是在该问题规模下需要时间最多的问题实例）。这5个不同阶算法在该台计算机上求解不同规模问题实例所需时间如表1-1所示。从表1-1 可以看出，对于复杂性阶为N的算法，当问题实例规模扩大6倍时，它所需时间也只增长了6倍，N是一个线性增长的过程；但是对于复杂性阶为3的算法，当问题实例规模扩大6倍时，其所需时间的增长速度是一个指数增长过程，它13所需的时间高达1.3×10世纪，这是一个几乎不可能完成的计算任务。总之，对于低效的算法（比如指数级复杂性算法），虽然它能求解规模比较小的问题实例，但是当求解的问题实例规模扩大若干倍时，它求解该问题实例所需的时间会爆炸式地增长，在现实意义上其求解过程变得不可能。表1-1 不同阶时间复杂性的算法求解不同规模问题实例所需时间
同样，假设求解某一个问题有5个不同算法，其时间复杂性阶分23NN别为N，N，N，2，3，让这5个算法在不同运算性能的计算机上运行。这5个不同阶时间复杂性的算法在不同运行速度的计算机上能求解的问题实例规模如表1-2所示。从表1-2可以看出，对于复杂度阶为N的算法，在1倍速计算机上能求解最大规模为N的问题实例，在1运行速度提高1000倍的计算机上，它能求解的问题实例最大规模为N1000N，是一个线性增长的过程；但是对于复杂度阶为3的算法，1在1倍速计算机上能求解最大规模为N的问题实例，在运行速度提高51000倍的计算机上，它能求解的问题实例最大规模并没有增长1000倍，相反，它能求解的问题实例最大规模仅仅增加了6.29。总之，对于低效的算法（比如指数级复杂度算法），计算机的计算速度成倍乃至数千倍地增长基本上不带来求解规模的较大增益。因此对于低效算法，问题求解规模的增大不能寄希望于移植算法到高速的计算机上，而应该把着眼点放在算法的改进上。表1-2 不同阶时间复杂性的算法在不同运行速度的计算机上能求解的问题实例规模
从表1-1和表1-2可以看出，限制求解问题规模的关键因素是算法渐近复杂性的阶。对于表中的前三种算法，其渐近的时间复杂性与规模N的幂同阶。相应地，求解问题规模的线性增大带来的是所需时间的线性增长，增长幅度随着幂次的提高而增大。另一方面，计算机的计算速度的线性增长带来的是求解问题规模的线性增长，只是随着幂次的提高，规模增长的倍数在降低。人们把渐近复杂性与规模N的幂同阶的这类算法称为多项式算法。对于表中的后两种算法，其渐近的时间复杂性与规模N的一个指数函数同阶。相应地，求解问题规模的线性增大带来的是所需时间的爆炸式增长；计算机的计算速度的线性增长只带来求解问题规模的加法增长。人们把渐近复杂性与规模N的指数同阶的这类算法称为指数型算法。多项式算法和指数型算法是在效率上有质的区别的两类算法。多项式算法是有效的算法，绝大多数的问题都存在有多项式算法。但也有一些问题还未找到多项式算法，只找到指数型算法。这两类算法的区别本质上是算法渐近复杂性的阶的区别。可见，算法渐近复杂性的阶对于算法的效率有着决定性的意义，所以在讨论算法的复杂性时人们基本上都只关心它的渐近阶。
在讨论算法复杂性的渐近阶的重要性的同时，有两条要记住：（1）“复杂性渐近阶比较低的算法比复杂性渐近阶比较高的算法有效”这个结论，只是在问题的求解规模充分大时才成立。比如复100N100N杂度阶分别为N和2的两种算法，前者比后者有效只是在N<2，100N即N≥C时才成立，其中C是方程N=2的解。当N<C时，后者反而比前者有效。所以对于规模小的问题，不要盲目地选用复杂性阶比较低的算法。其原因包括两个方面：首先，复杂性阶比较低的算法在规模小时不一定比复杂性阶比较高的算法更有效；另外，在规模小时，决定工作效率的可能不是算法的复杂度而是代码的效率，哪一种算法
试读结束[说明：试读内容隐藏了图片]