预测算法所有可能的输入，包括合法的输入和非法的输入。事实上，无法保证一个算法（或程序）永远不会遇到一个错误的输入，一个对大部分输入都运行正确而只有一个输入不行的算法，就像一颗等待爆炸的炸弹。这决不是危然耸听，有大量这种引起灾难性后果的案例。例如许多年以前，整个AT&T的长途电话网崩溃，造成了几十亿美元的直接损失。原因只是一段程序的设计者认为他的代码能一直传送正确的参数值，可是有一天，一个不应该有的值作为参数传递了，导致了整个北美电话系统的崩溃。
如果养成习惯——首先考虑问题和它的数据，然后列举出算法必须处理的所有特殊情况，那么可以更快速地成功构造算法。 3. 在精确解和近似解间做选择
计算机科学的研究目标是用计算机来求解人类所面临的各种问题。但是，有些问题无法求得精确解，例如求平方根、解非线性方程、求定积分等，有些问题由于其固有的复杂性，求精确解需要花费太长的时间，其中最著名的要算旅行商问题（即TSP问题，是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短），此时，只能求出近似解。
有时需要根据问题以及问题所受的资源限制在精确解和近似解间做选择。 4. 确定适当的数据结构
在结构化的程序设计时代，著名的计算机学者沃思（Wirth）提出了“算法+数据结构=程序”，断言了算法和数据结构是构成计算机程序设计的重要基础。在面向对象的程序设计时代，数据结构对于算法设计和分析仍然是至关重要的。本书所讨论的很多算法设计技术都是基于精心设计的数据结构。
确定数据结构通常包括对问题实例的数据进行组织和重构，以及为完成算法所设计的辅助数据结构。在很多情况下，数据结构的设计直接影响基于该结构之上设计的算法的时间性能。
概念回顾 数据结构是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据结构从逻辑上分为4类：集合、线性结构、树结 构和图结构，常用的存储结构有两种：顺序存储结构和链接存储结构。
5．算法设计技术
现在，设计算法的必要条件都已经具备了，如何设计一个算法来解决一个特定的问题呢？这正是本书讨论的主题。
算法设计技术（Algorithm Design Technique,也称算法设计策略）是设计算法的一般性方法，可用于解决不同计算领域的多种问题。本书讨论的算法设计技术是已经被证明是对算法设计非常有用的通用技术，包括蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法、近似算法等，这些算法设计技术构成了一
6
组强有力的工具，在为新问题（即没有令人满意的已知算法可以解决的问题）设计算法时，可以运用这些技术设计出新的算法。算法设计技术作为问题求解的一般性策略，在解决计算机领域以外的问题时，也能发挥相当大的作用，读者在日后的学习和工作中将会发现学会他们的好处。 6．描述算法
在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来，即描述算法。常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等，其中伪代码是比较合适的描述算法的方法。因为C++语言的功能强，而且大多数读者都比较熟悉，所以，本书对于算法的描述采用符合C++语法的伪代码，使得算法的描述简明清晰，既不拘泥于C++语言的实现细节，又容易转换为C++程序。 7．跟踪算法
逻辑错误无法由计算机检测出来，因为计算机只会执行程序，而不会理解动机。经验和研究都表明，发现算法（或程序）中的逻辑错误的重要方法就是系统地跟踪算法。跟踪必须要用“心和手”来进行，跟踪者要像计算机一样，用一组输入值来执行该算法，并且这组输入值要最大可能地暴露算法中的错误。即使有几十年经验的高级软件工程师，也经常利用此方法查找算法中的逻辑错误。 8．分析算法的效率
算法有两种效率：时间效率和空间效率，时间效率显示了算法运行得有多快，空间效率则显示了算法需要多少额外的存储空间，相比而言，我们更关注算法的时间效率。事实上，计算机的所有应用问题，包括计算机自身的发展，都是围绕着“时间——速度”这样一个中心进行的。一般来说，一个好的算法首先应该是比同类算法的时间效率高，算法的时间效率用时间复杂性来度量。 9．根据算法编写代码
现代计算机技术还不能将伪代码形式的算法直接“输入”进计算机中，而需要把算法转变为特定程序设计语言编写的程序，算法中的一条指令可能对应实际程序中的多条指令。在把算法转变为程序的过程中，虽然现代编译器提供了代码优化功能，但仍需要一些标准的技巧，比如，在循环之外计算循环中的不变式、合并公共子表达式、用开销低的操作代替开销高的操作等等。一般来说，这样的优化对算法速度的影响是一个常数因子，可能会使程序提高10％～50％的速度。
算法设计的一般过程如图1.3所示。需要强调的是，一个好算法是反复努力和重新修正的结果，所以，即使足够幸运地得到了一个貌似完美的算法，也应该尝试着改进它。那么，什么时候应该停止这种改进呢？设计算法是一种工程行为，需要在资源有限的情况下，在互斥的目标之间做权衡。设计者的时间显然也是一种资源，在实际应用中，常常是项目进度表迫使我们停止改进算法。
7
理解问题 预测所有可能的输入 确定： ? 精确解还是近似解 ? 确定数据结构 ? 算法设计技术
设计并描述算法 跟踪算法 分析算法的效率 根据算法编写代码 图1.3 算法设计的一般过程
1.1.5 重要的问题类型
就像生物学把自然界的所有生物作为自己的研究对象，计算机科学把问题作为自己的研究对象，研究如何用计算机来解决人类所面临的各种问题。在计算领域的无数问题中，或者由于问题本身具有一些重要特征，或者由于问题具有实用上的重要性，有一些领域的问题是算法研究人员特殊关注的。经验证明，无论对于学习算法还是应用算法，对这些问题的研究都是极其重要的。在本书中，我们将围绕下述问题展开对算法设计技术的讨论。 1. 查找问题
查找是在一个数据集合中查找满足给定条件的记录。对于查找问题来说，没有一种算法对于任何情况都是合适的。有的算法查找速度比其他算法快，但却需要较多的存储空间（例如Hash查找），有的算法查找速度非常快，但仅适用于有序数组（例如折半查找），如此等等。此外，如果在查找的过程中数据集合可能频繁地发生变化，除了考虑查找操作，还必须考虑在数据集合中执行插入和删除等操作，这种情况下，就必须仔细地设计数据结构和算法，以便在各种操作的需求之间达到一个平衡。而且，组织用于高效查找的特大型数据集合对实际应用具有非常重要的意义。 2. 排序问题
简单地说，排序就是将一个记录的无序序列调整成为一个有序序列的过程。在对
8
记录进行排序时，需要选定一个信息作为排序的依据，例如，可以按学生姓名对学生记录进行排序，这个特别选定的信息称为关键码。
排序的主要目的是为了进行快速查找，这就是为什么字典、电话簿和班级名册都是排好序的。出于同样的考虑，在其他领域的很多重要算法中，排序也被作为一个辅助步骤，例如，搜索引擎将搜索到的结果按相关程度排序后显示给用户。
迄今为止，已经发明的排序算法不下几十种，没有一种排序算法在任何情况下都是最好的解决方案，有些排序算法比较简单，但速度相对较慢；有些排序算法速度较快，但却很复杂；有些排序算法适合随机排列的输入；有些排序算法更适合基本有序的初始排列；有些排序算法仅适合存储在内存中的序列，有些排序算法可以用来对存储在磁盘上的大型文件排序，等等。 3. 图问题
算法中最古老也最令人感兴趣的领域是图问题，很多纷乱复杂的现实问题抽象出的模型都是图结构，例如，可以利用图研究化学领域的分子结构、解决高校排课问题、解决任务分配问题和车间调度问题等等。
概念回顾 图（Graph）通常表示为G=(V，E)，其中，G表示一个图，V是图G中顶点的集合， E是图G中顶点之间边的集合。若顶点vi和vj之间的边没有方向，则称这条边为无向边，用无序偶对(vi，vj)来表示；若从顶点vi到vj的边有方向，则称这条边为 有向边（也称为弧），用有序偶对
组合问题一般都是最优化问题，即寻找一个组合对象，比如一个排列、一个组合或一个子集，这个对象能够满足特定的约束条件并使得某个目标函数取得极值：价值最大或成本最小。
无论从理论的观点还是实践的观点，组合问题都是计算领域中最难的问题，其原因是：⑴ 随着问题规模的增大，组合对象的数量增长极快，即使是中等大小的实例，其组合对象的数量也会达到不可思议的数量级，产生组合爆炸；⑵ 还没有一种已知算法能在可接受的时间内，精确地求解绝大多数这类问题。 5. 几何问题
几何问题处理类似于点、线、面、体等几何对象。几何问题与其他问题的不同之处在于，哪怕最简单、最初等的几何问题也难以用数字去处理。尽管人类对几何问题
9
的研究从古代起便没有中断过，但是具体到借助计算机来解决几何问题的研究，还只是停留在一个初级阶段。随着计算机图形图像处理、机器人和断层X摄像技术等方面应用的深入，人们对几何算法产生了强烈的兴趣。本书只讨论两个经典的计算几何问题：最近对问题和凸包问题。最近对问题是在给定平面上的n个点中，求距离最近的两个点，凸包问题要求找出一个能把给定集合中的所有点都包含在里面的最小凸边形。
1.2 算法分析
算法分析（Algorithm Analysis）指的是对算法所需要的两种计算机资源——时间和空间进行估算，所需要的资源越多，该算法的复杂性就越高。不言而喻，对于任何给定的问题，设计出复杂性尽可能低的算法是设计算法时追求的一个重要目标；另一方面，当给定的问题有多种解法时，选择其中复杂性最低者，是选用算法时遵循的一个重要准则。随着计算机硬件性能的提高，一般情况下，算法所需要的额外空间已不是我们需要关注的重点了，但是对算法时间效率的要求仍然是计算机科学不变的主题。本书重点讨论算法时间复杂性（Time Complexity）的分析，对空间复杂性（Space Complexity）的分析是类似的。
1.2.1 渐进符号
算法的复杂性是运行算法所需要的计算机资源的量，这个量应该集中反映算法的效率，而从运行该算法的实际计算机中抽取出来。撇开与计算机软、硬件有关的因素，影响算法时间代价的最主要因素是问题规模。问题规模（Problem Scope）是指输入量的多少，一般来说，它可以从问题描述中得到。例如，对一个具有n个整数的数组进行排序，问题规模是n；对一个m行n列的矩阵进行转置，则问题规模是m和n。一个显而易见的事实是：几乎所有的算法，对于规模更大的输入都需要运行更长的时间。例如，需要更多时间来对更大的数组排序，更大的矩阵转置需要更长的时间。所以运行算法所需要的时间T是问题规模n的函数，记作T(n)。
要精确地表示算法的运行时间函数常常是很困难的，即使能够给出，也可能是个相当复杂的函数，函数的求解本身也是相当复杂的。考虑到算法分析的主要目的在于比较求解同一个问题的不同算法的效率，为了客观地反映一个算法的运行时间，可以用算法中基本语句的执行次数来度量算法的工作量。基本语句（Basic Statement）是执行次数与整个算法的执行次数成正比的语句，基本语句对算法运行时间的贡献最大，是算法中最重要的操作。这种衡量效率的方法得出的不是时间量，而是一种增长趋势的度量。换言之，只考察当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，通常使用大O、大Ω和Θ等三种渐进符号表示。 1. 大O符号
定义1.1 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，
10
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法设计与分析(2)在线全文阅读。
相关推荐：