常用算法分析及应用实例---毕业论文

本 科 毕 业 论 文 常用算法分析及应用实例Representative Algorithm Analysis and Application姓 名：学 号：学院：软件学院系：软件工程专 业：软件工程年 级：指导教师： 年 月摘要众所周知，在现代计算机科学和软件工程中都会面临许多各种各样复杂的问题。不同的计算机编程语言，各种各样的组件控件，还有花样繁多的新技术不断涌现。这都是计算机科学发展的必然，没有最好的只有更好的。面对这么多不断变幻的选择，只有牢固的掌握了算法设计和分析的能力，才能以不变应万变。所有的技术都是在数据结构和算法的基础上建立的，牢固掌握算法的分析方法和编程的能力就成为相当重要的一个部分。算法是解题的步骤，可以把算法定义为解决特定问题而规定的一系列操作。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法的设计与分析有很多常用的策略和分析方法。本论文研究几种常用的算法分析策略和设计思想并进行具体问题实例分析。如：递归与分治策略， 动态规划算法， 贪心算法。研究每个算法分析策略的设计过程，实现一个迷宫探险算法的程序实例。关键词：递归与分治；动态规划；贪心算法 .Abstract As we all know, in the modern computer science and software engineering will Face a wide range of complex issues. Different computer programming languages,wide range of control components, as well as diverse new technologies are emerging.This is the inevitable development of computer science, there is no best, only better.Constantly changing the face of so many choices, only a solid grasp of algorithm design and analysis capabilities, to maintaining the status quo. All the technologies are in the data structure and algorithm based on the established and firmly grasp the analysis of algorithms and programming ability to become a very important part. Algorithm is problem-solving steps, the algorithm can solve the specific problem is defined as a series of operations required. In computer science, the algorithm to use language to describe the computer algorithm, algorithm on behalf of a class of computer problem solution accurate and effective method. Algorithm design and analysis of many commonly used strategies and analysis. This paper studies algorithms for some commonly-used analysis of strategies and design concepts and examples of analysis of specific issues. Such as: governance strategy and sub-recursive, dynamic programming algorithm, greedy algorithm. Analysis of research strategy for each algorithm design process, the realization of a maze exploration algorithm instance. Keywords: Recursion and Divided; Dynamic programming; Greedy algorithm.目录第一章 引言11.1为什么选择算法11.2算法概述21.3算法的正确性和效率4第二章 递归与分治策略82.1递归的概念82.2分治法的基本思想82.3 Hanoi塔问题92.3.1算法分析92.3.2结论122.3.4具体的实验代码132.4快速排序算法142.4.1快速排序算法的分析142.4.2各排序算法的实现与比较17第三章 动态规划193.1动态规划的基本思想193.2最长公共子序列问题LCS193.2.1算法分析193.2.2算法的改进233.2.3程序实现和实验结果233.3最大子段和243.3.1算法分析243.3.2三种算法的实验结果28第四章 贪心算法304.1贪心算法定义304.2装箱问题304.2.1算法分析304.2.2算法的实现314.3单源最短路径324.3.1算法基本思想334.3.2算法的实现33第五章 迷宫探险程序应用实例345.1程序简介345.2程序的设计思路345.3程序的基本结构描述345.4程序代码主体程序365.5程序运行结果39第六章 总结40致谢43参考文献42附录43ContentsChapter 1 Introduction.11.1 Why Choose Algorithm11.2 Algorithm21.3 Algorithm Coorectness and Efficiency4Chapter 2 Recursive82.1 The Concept of Recursive82.2 Divided82.3 Hanoi Tower Problem92.3.1 Algorithm Analysis92.3.2 Conclusion122.3.4 Experimental Specific Code132.4 Quick Sort Algorithm142.4.1 Analysis of Quicksort 142.4.2 Sorting Algorithm Compare17Chapter 3 Dynamic Programming193.1 The Basic Idea of Dynamic Programming193.2 Longest Sequence of Public Lcs193.2.1 Algorithm Analysis193.2.2 Algorithm233.2.3 Experimental Result233.3 The Largest Sub-Paragraph243.3.1 Algorithm Analysis243.3.2 Experimental Results of Three Algorithms28Chapter 4 Greedy Algorithm304.1 The Definition of Greedy Algorithm304.2Bin Packing Problem304.2.1 Algorithm Analysis304.2.2 Algorithm314.3 Single-Source Shortest Path324.3.1 The Basic Idea of Algorithm334.3.2 Algorithm33Chapter 5 Application Maze Explorer345.1 Introduction345.2 Design Procedures345.3 Structure of The Procedures345.4 The Main Code365.5 Code and The Results of Experiments39Chapter 6 Conclusion40Acknowledgements41References42Appendix43厦门大学软件学院毕业论文 常用算法分析及应用实例第一章 引言1.1为什么选择算法计算机既是数学的创造物，又是数学的创造者”， 而算法既是计算机理论和实践的核心，也是数学的最基本内容之一.。甚至有人说， 数学学习的主要作用是形成“算法思维”。算法有着悠久的发展历史，中国古代数学曾经以算法为特色， 取得了举世瞩目的辉煌成就。 在已经逐步进入信息化社会的今天，算法的基本知识、方法、思想日益融入人们社会生活的方方面面，已经也应该成为现代人所应具备的一种基本素质。我学习算法有以下几个方面的意义：算法学习有助于我们全面的理解运算能力。 很多时候,人们对运算存在一些误解，认为运算就是按照各种运算法则进行加、减、乘、除，从而学习运算就是背诵书本中给出的计算法则， 形成一些基本的计算技巧，也就是说，能够根据熟记的法则，迅速的计算给定式子的正确答案。实际上，按照算法规则进行逻辑推理而获得正确结果仅仅是计算的很小的一个方面，更重要的是，在运算中构造、设计、选择一个合理的算法，理解相应的算理。 在算法学习中，我找出一个问题的不同算法，并比较这些算法的优劣，并作出选择，从而提高效率，而这个过程才是一个真正的运算过程，因此算法学习使得我们拥有更加全面的理解运算能力。算法学习能够培养在积极的逻辑思维能力。 我们常常说数学是思维的体操，能够训练学生的思维能力。算法作为数学的一个基本内容，在培养逻辑思维能力上能够发挥重要的作用。 算法是解题方法的精确描述。 算法一方面具有具体化、程序化、机械化的特点, 同时又有高度抽象性、概括性和精确性。 因此，将解决具体问题的方法整理成算法的过程是一个条理化，精确化和逻辑化的过程，有助于培养逻辑思维能力。1.2算法概述什么叫算法?算法（Algorithm）是解题的步骤，可以把算法定义为解决特定问题而规定的一系列操作。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题。这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。 算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。制定一个算法，一般要经过设计、确认、分析、编码、测试、调试、计时等阶段。 对算法的学习包括五个方面的内容： 设计算法。算法设计工作是不可能完全自动化的，应学习了解已经被实践证明是有用的一些基本的算法设计方法，这些基本的设计方法不仅适用于计算机科学，而且适用于电气工程、运筹学等领域； 表示算法。描述算法的方法有多种形式，例如自然语言和算法语言，各自有适用的环境和特点； 确认算法。算法确认的目的是使人们确信这一算法能够正确无误地工作，即该算法具有可计算性。正确的算法用计算机算法语言描述，构成计算机程序，计算机程序在计算机上运行，得到算法运算的结果； 分析算法。算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较； 验证算法。用计算机语言描述的算法是否可计算、有效合理，须对程序进行测试，测试程序的工作由调试和作时空分布图组成。 算法的特性算法的特性包括： 确定性。算法的每一种运算必须有确定的意义，该种运算应执行何种动作应无二义性，目的明确； 能行性。要求算法中有待实现的运算都是基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成； 输入。一个算法有0个或多个输入，在算法运算开始之前给出算法所需数据的初值，这些输入取自特定的对象集合； 输出。作为算法运算的结果，一个算法产生一个或多个输出，输出是同输入有某种特定关系的量； 有穷性。一个算法总是在执行了有穷步的运算后终止，即该算法是可达的。满足前四个特性的一组规则不能称为算法，只能称为计算过程，操作系统是计算过程的一个例子，操作系统用来管理计算机资源，控制作业的运行，没有作业运行时，计算过程并不停止，而是处于等待状态。算法的描述算法的描述方法可以归纳为以下几种： (1) 自然语言； (2) 图形，如NS图、流程图，图的描述与算法语言的描述对应； (3) 算法语言，即计算机语言、程序设计语言、伪代码； (4) 形式语言，用数学的方法，可以避免自然语言的二义性； 用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。 人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法，例如人们到商店购买物品，会首先确定购买哪些物品，准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线，若物品的质量好如何处理，对物品不满意又怎样处理，购买物品后做什么等。以上购物的算法是用自然语言描述的，也可以用其他描述方法描述该算法。 算法的复杂性 算法的复杂性是算法效率的度量，在评价算法性能时，复杂性是一个重要的依据。算法的复杂性的程度与运行该算法所需要的计算机资源的多少有关，所需要的资源越多，表明该算法的复杂性越高；所需要的资源越少，表明该算法的复杂性越低。 计算机的资源，最重要的是运算所需的时间和存储程序和数据所需的空间资源，算法的复杂性有时间复杂性和空间复杂性之分。 算法在计算机上执行运算，需要一定的存储空间存放描述算法的程序和算法所需的数据，计算机完成运算任务需要一定的时间。根据不同的算法写出的程序放在计算机上运算时，所需要的时间和空间是不同的，算法的复杂性是对算法运算所需时间和空间的一种度量。不同的计算机其运算速度相差很大，在衡量一个算法的复杂性要注意到这一点。 对于任意给定的问题，设计出复杂性尽可能低的算法是在设计算法时考虑的一个重要目标。另外，当给定的问题已有多种算法时，选择其中复杂性最低者，是在选用算法时应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 在讨论算法的复杂性时，有两个问题要弄清楚： (1) 一个算法的复杂性用怎样的一个量来表达； (2) 怎样计算一个给定算法的复杂性。 找到求解一个问题的算法后，接着就是该算法的实现，至于是否可以找到实现的方法，取决于算法的可计算性和计算的复杂性，该问题是否存在求解算法，能否提供算法所需要的时间资源和空间资源。1.3算法的正确性和效率 算法的正确性判定:研究计算机算法的目的是为了有效地求出问题的解，用计算机语言描述的算法要在计算机上运行，这引出了对算法效率的分析和讨论。例如在象棋比赛中，对任意给出的一种棋局，可以设计一种算法判断这一棋局的输赢，算法需要从开局起对所有棋子可能进行的移动、移动前后的每一对策作检查，做出应走的棋步。计算步骤是有穷的，但在计算机上运算这一算法需要很长的时间。这就说明计算机只能运行有穷步内终止的算法。 设计出算法后，应证明该算法对所有可能的合法输入都能计算出正确的结果，这一工作称为算法确认。算法确认与描述实现这一算法的手段无关，例如可以用不同计算机语言来实现这一算法。用算法语言描述构成的程序在计算机上运行，也应证明该程序是正确的，这一工作称为程序证明。 对程序的测试包括调试和作时空分布图。调试程序是在抽象数据集上执行程序，确定是否会产生错误的结果，如果出现错误，进行修改，再做测试。调试只能指出程序有错误，而不能指出程序不存在错误。程序的正确性证明是计算机科学一个重要的研究领域。作时空分布图是用各种给定的测试数据，去调试已经证明是正确的程序，测定一个算法得出运算结果所用去的时间和空间，给出时空分布图，验证对算法所作的分析是否正确，找出算法最优化的有效逻辑位置，优化算法的效率。 算法的最优性求解一个问题，如果规定了算法所允许的运算类型，则所有可能的算法构成了解决这个问题的一个算法类，判断一个算法是否最优的依据，是该算法的平均性态分析。若在选择的算法类中，如果一个算法比所有的算法执行的基本运算少，此算法应该是最优的。 判断一个算法是否最优，并不需要对算法类中的每一个算法逐个进行分析，可以根据这个算法类的特性，确定所需运算次数的下界，在算法类中所有运算次数等于这个下界的算法是最优的，这也说明最优算法不是惟一的。需要做两件工作确定解决一个问题至少需要多少次运算： 设计一个有效率的算法A，分析A并找到一个函数F，使对尺度为n的输入，A最多做F(n)次基本运算； 对某一函数G，证明一个定理，表明对所考虑的算法类中的任何一个算法，存在一个尺度为n的输入，使算法至少要做G(n)次基本运算。 若函数F与G相等，则算法A是最优的；若不相等，则可能存在一个更好的算法或更好的下界。 分析算法1.分析算法的两个主要内容 要分析一个算法首先要确定使用哪些算法以及执行这些算法所用的时间。运算可以分为两类，一类是基本运算，包括加、减、乘、除四种基本的整数算术运算以及浮点算术、比较、对变量赋值和过程调用等。这些运算所用的时间不同，但都是花费一个固定量的时间。另一类运算由一些基本运算的任意长序列组成，以两个字符串的比较运算为例，可以看做是一系列字符比较指令运算，而字符比较指令可以使用移位和位比较指令。比较两个字符的运算时间是固定的，是某一个常数值，而比较两个字符串的运算时间值则与字符串的长度相关。 其次是确定能反映出算法在各种情况下工作的测试数据集，设计和编制出能够产生最优、最差运算结果的输入数据配置，这些数据配置能够代表可能出现的典型情况。数据配置的设计是创造性的工作，应能最大限度地适应算法，反映算法运行的环境和功能要求。 2.分析算法的两个阶段 对一个算法作出分析分为两个阶段，即事前分析和事后测试。 事前分析（priori analysis），求出该算法的一个时间界限函数，用于对计算时间的渐进表示，假定某一算法的计算时间是f(n)，其中变量n表示输入或输出量，它可以是两者之和，也可以是它们之一的一种测度，例如数组的维数、图的边数等，f(n)与机器和语言有关。g(n)是在事前分析中确定的某个形式很简单的函数，是独立于机器和语言的函数，例如nm、logN、2n、n!等。给出定义： 若存在两个正常数c和n0，对于所有的nn0，下式成立 f(n) c g(n)记作 f(n)= O(g(n) 因此，当讲一个算法具有O(g(n)的计算时间时，指的是若该算法用n值不变的同一类数据在某台机器上运行时，所用的时间是小于 g(n)|的一个常数倍，所以g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)，在确定f(n)的数量级时总是试图求出最小的g(n)，使得f(n)= O(g(n)。 事后测试（posteriori testing），收集该算法的执行时间和实际占用空间的统计资料，是在对算法进行设计、确认、事前分析、编码和调试后要做的工作，即作时空性能分布图，事后测试的结果与所用机器相关。要确定算法的精确计算时间，必须了解时钟的精确度以及计算机所用操作系统的工作方式。为避免因所用机器不同而出现误差，有两种可以选用的方法：一种方法是增加输入规模，直到得到算法所需的可靠的时间总量；第二种方法是取足够大的算法重复因子r，将该算法执行r次，然后用总的时间去除以r。 例如，对于事前分析为O(g(n)时间的算法，选择按输入不断增大其规模的数据集，用这些数据集在计算机上运行算法程序，得出算法所使用的时间，画出这一数量级的时间曲线，并与事前分析所得出的曲线比较。第二章 递归与分治策略2.1递归的概念递归作为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重复现象。程序调用自身的编程技巧称为递归（ recursion）。 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 注意： (1) 递归就是在过程或函数里调用自身; (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。(Fibonacci函数)(2)问题解法按递归算法实现。(回溯)(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)递归的缺点：递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。2.2分治法的基本思想分治法在求解一个输入规模为n，而n的取值又很大的问题时，直接求解往往非常困难。这时，可以先分析问题本身所具有的某些特性，然后从这些特性出发，选择某些适当的设计策略来求解。这种方法，就是所谓的分治法。采用分治法解决的问题一般具有的特征如下：1. 问题的规模缩小到一定的规模就可以较容易地解决。2. 问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质。3. 合并问题分解出的子问题的解可以得到问题的解。4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题。分治法的设计步骤:1. 划分步：把输入的问题划分为k个子问题，并尽量使这k个子问题的规模大致相同。2. 治理步：当问题的规模大于某个预定的阈值n0时，治理步由k个递归调用组成。3. 组合步：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。分治法的关键是算法的组合步。究竟应该怎样合并，目前没有统一的模式，因此需要对具体问题进行具体分析，以得出比较好的合并算法。2.3 Hanoi塔问题Hanoi塔问题是一个典型的可用递归方法解决的问题（递归问题通常可转化为非递归问题）。Abc三个塔座，a上有n个盘编号123n，要求将a上的盘移到c上，规则如下： 规则1 每次只能移动一个圆盘； 规则2 任何时候都不能把大盘放在小盘上 规则3 在满足1 和2 的条件下可以将圆盘移到abc中任一塔上； 2.3.1算法分析如下，设A上有n个盘子。如果n=1，则将圆盘从A直接移动到C。如果n=2，则：（1）将A上的n-1（等于1）个圆盘移到B上；（2）再将A上的一个圆盘移到C上；（3）最后将B上的n-1（等于1）个圆盘移到C上。如果n=3，则：1.将A上的n-1（等于2，令其为n）个圆盘移到B（借助于C），步骤如下：（1）将A上的n-1（等于1）个圆盘移到C上。（2）将A上的一个圆盘移到B。（3）将C上的n-1（等于1）个圆盘移到B。2.将A上的一个圆盘移到C。3.将B上的n-1（等于2，令其为n）个圆盘移到C（借助A），步骤如下：（1）将B上的n-1（等于1）个圆盘移到A。（2）将B上的一个盘子移到C。（3）将A上的n-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。从上面分析可以看出，当n大于等于2时， 移动的过程可分解为三个步骤：第一步 把A上的n-1个圆盘移到B上；第二步 把A上的一个圆盘移到C上；第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。 当n=3时，第一步和第三步又分解为类同的三步，即把n-1个圆盘从一个塔移到另一个塔上，这里的n= n-1。 显然这是一个递归过程，算法如下： Void Hanoi ( int n , int a, int b, int c)If( n 0) Hanoi ( n-1, a, c, b); Move( a, c); Hanoi( n-1 , b, c, a);从程序中可以看出hanoi函数是一个递归函数，其功能是把a上的n个圆盘移动到c 上。当n=1时，直接把a上的圆盘移至c上，。如n!=1则分为三步：递归调用hanoi函数，把n-1个圆盘从a移到b利用c作转移的塔；然后把第n大的盘从a移到c ， 然后把n-2个盘从b移到a 利用c作转移的塔，然后把n-1大的盘从b移到c 。1Hanoi塔问题中函数调用时系统所做工作一个函数在运行期调用另一个函数时，在运行被调用函数之前，系统先完成3件事：将所有的实参、返回地址等信息传递给被调用函数保存。为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。从被调用函数返回调用函数前，系统也应完成3件事：保存被调用函数的结果；释放被调用函数的数据区；依照被调用函数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时，按照“后调用先返回”的原则（LIFO），上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，每当从一个函数退出时，就释放其存储区，因此当前运行函数的数据区必在栈顶。堆栈特点：LIFO，除非转移或中断，堆栈内容的存或取表现出线性表列的性质。正是如此，程序不要求跟踪当前进入堆栈的真实单元，而只要用一个具有自动递增或自动递减功能的堆栈计数器，便可正确指出最后一次信息在堆栈中存放的地址。一个递归函数的运行过程类型于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入下一层，即i1层。反之，退出第i层递归应返回至上一层，即i1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”，作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有实参、所有局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。2.Hanoi塔问题递归程序的复杂度分析时间复杂度程序所花时间正比于所输出的信息行数目，而信息行的数目则等价于盘子的移动次数。考察程序，设盘子移动次数为moves（n），则：moves(n) = 2 moves(n-1) + 1 ; moves(1) = 1 .用迭代方法计算公式，得到结果moves(n)=2n-1。 因此，hanoi函数的时间复杂度为O(2 n) 。空间复杂度从每个塔上移走盘子时是按照LIFO进行，因此可以把每个塔表示成一个堆栈。3座塔在任何时候总共拥有的盘子都是n个。如果使用链表形式的堆栈，只需申请n个元素所需要的空间。如果使用的是基于公式化描述的堆栈，塔1和塔2的容量都必须是n，而塔3的容量是n1，因此所需要的空间总数为3n1。Hanoi塔问题的复杂性是以n为指数的函数，因此在可以接受的范围内，只能解决n值比较小（n=30）的hanoi问题。对于这个较小的n值，堆栈在空间需求上的差别相当小，可以随意使用。2.3.2结论通过对上述递归在Hanoi塔问题上的应用分析，我们可以得出如下结论：1、递归调用过程中，在程序执行之前无法知道控制这种调用栈的规模，因为这一规模取决于递归调用的次序。在这种情况下，程序的地址空间可能动态变化；2、递归应用于程序设计时，结构清晰、程序易读，编制和调试程序很方便，不需要用户自行管理递归工作栈。但递归应用于计算机时需要占用大量系统资源（包括堆栈、软中断和存贮空间等），并消耗大量处理时间。因此，可以考虑采用并行计算进行处理3、递归是串行的，其第n步运算依赖于第n-1步运算，所以在计算机软件理论上不存在递归问题并行计算的可能性。实际上是否存在并行递归计算有待进一步探讨。2.3.4 具体的实验代码 见附录1：2.4快速排序算法2.4.1 快速排序算法的分析快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n2)，但由于平均运行时间为O(nlogn)，并且在内存使用、程序实现复杂性上表现优秀，尤其是对快速排序算法进行随机化的可能，使得快速排序在一般情况下是最实用的排序方法之一。快速排序被认为是当前最优秀的内部排序方法。实现: 快速排序的实现基于分治法，具体分为三个步骤。假设待排序的序列为Lm.n。1.分解：序列Lm . n被划分成两个可能为空的子序列Lm . pivot-1和Lpivot+1 . n，使Lm . pivot-1的每个元素均小于或等于Lpivot，同时Lpivot+1. n的每个元素均大于Lpivot。其中Lpivot称为这一趟分割中的主元（也称为枢轴、支点）。2.解决：通过递归调用快速排序，对子序列Lm . pivot-1和Lpivot+1 . r排序。 3.合并：由于两个子序列是就地排序的，所以对它们的合并不需要操作，整个序列Lm . n已排好序。性质: 内部排序;快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。比较排序;快速排序确定元素位置的方法基于元素之间关键字大小的比较。所有基于比较方法的排序方法的时间下界不会低于O(nlogn)。这个结论的具体证明，请参考有关算法的书籍，例如算法导论第8章。快速排序在理想情况下，能严格地达到O(nlogn)的下界。一般情况下，快速排序与随机化快速排序的平均情况性能都达到了O(nlogn)。不稳定性快速排序是一种不稳定的排序方法。简单地说，元素a1, a2的关键字有a1.key=a2.key，则不稳定的排序方法不能保证a1, a2在排序后维持原来的位置先后关系。原地排序在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈），快速排序算法只需消耗确定数量的空间（即S(1)，常数级空间）。这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快速排序也能够很好地工作。时空复杂度 快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)。但需要注意递归栈上需要花费最少logn 最多n的空间。随机化算法 快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”随机化快速排序的唯一缺点在于，一旦输入数据中有很多的相同数据，随机化的效果将直接减弱。对于极限情况，即对于n个相同的数排序，随机化快速排序的时间复杂度将毫无疑问的降低到O(n2)。随机化的划分算法可实现如下：产生随机化的划分TempletInt RandomizedPartition( Type a, int p, int r) Int i= Random( p, r);Swap(ai, ap );Return partition(a, p , r);随机化的快速排序算法通过调用RandomizedPartition来产生随机的划分。TemplateVoid RandomizedQuickSort( Type a , int p , int r )If( p r ) Int q = RandomizedPartition( a, p, r);RandomizedQuickSort( a, p, q-1);RandomizedQuickSort(a , q+1，r)；减少递归栈使用的优化 快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时，对系统栈的频繁存取会影响到排序的效率。一种常见的办法是设置一个阈值，在每次递归求解中，如果元素总数不足这个阈值，则放弃快速排序，调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取，节省了时间的消费。一般的经验表明，阈值取一个较小的值，排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案：阈值T=10，排序算法用选择排序。阈值不要太大，否则省下的存取系统栈的时间，将会被简单排序算法较多的时间花费所抵消。另一个可以参考的方法，是自行建栈模拟递归过程。但实际经验表明，收效明显不如设置阈值。2.4.2 各排序算法的实现与比较见附录2：从测试结果中可以看到，数据量大的时候，二分法插入排序的性能较好。快速排序最佳。冒泡排序由于是稳定的排序方法，排序性能适中，比较适合使用，当数据量大、不要求稳定排序时可以考虑二分法或快速，堆排序。小数据量时用插入或冒泡排序就够了，针对随机数，通常不要使用选择排序。第三章 动态规划3.1 动态规划的基本思想动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。3.2最长公共子序列问题LCS3.2.1 算法分析：1.最长公共子序列的结构解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列1, 2, , m的一个子序列，因此，X共有2m个不同子序列，从而穷举搜索法需要指数时间。事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理：定理: LCS的最优子结构性质设序列X=和Y=的一个最长公共子序列Z=，则：若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；若xmyn且zkxm ，则Z是Xm-1和Y的最长公共子序列；若xmyn且zkyn ，则Z是X和Yn-1的最长公共子序列。其中Xm-1=，Yn-1=，Zk-1=。证明用反证法。若zkxm，则是X和Y的长度为k十1的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾。因此，必有zk=xm=yn。由此可知Zk-1是Xm-1和Yn-1的一个长度为k-1的公共子序列。若Xm-1和Yn-1有一个长度大于k-1的公共子序列W，则将xm加在其尾部将产生X和Y的一个长度大于k的公共子序列。此为矛盾。故Zk-1是Xm-1和Yn-1的一个最长公共子序列。由于zkxm，Z是Xm-1和Y的一个公共子序列。若Xm-1和Y有一个长度大于k的公共子序列W，则W也是X和Y的一个长度大于k的公共子序列。这与Z是X和Y的一个最长公共子序列矛盾。由此即知Z是Xm-1和Y的一个最长公共子序列。这个定理告诉我们，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。2.子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xmyn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用ci,j记录序列Xi和Yj的最长公共子序列的长度。其中Xi=，Yj=。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故ci,j=0。其他情况下，由定理可建立递归关系。3.计算最优值直接利用(2.2)式容易写出一个计算ci,j的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=和Y=作为输入。输出两个数组c0.m ,0.n和b1.m ,1.n。其中ci,j存储Xi与Yj的最长公共子序列的长度，bi,j记录指示ci,j的值是由哪一个子问题的解达