算法设计与分析报告论文

1、评 语对课程论文的评语：平时成绩：课程论文成绩：总 成 绩：评阅人签名：注：1、无评阅人签名成绩无效；2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；3、如有平时成绩，必须在上面评分表中标出，并计算入总成绩。目录目录2课程学习日程回顾5第一章：算法导引61.1 算法的设计与分析81.1.1 算法的设计。81.1.2 算法的验证。81.1.3 算法分析。81.2 算法的分类91.3 算法的评价91.4递归算法101.4.1 Fibonacci数列101.4.2 汉诺塔问题101.4.3 递归算法特征总结131.5 课堂内容扩展NPC问题141.5.1 NPC问题描述141.5.2 NPC举例14第二

2、章：分治法152.1 分治法152.1.1 化难问题为易问题的校正问题15化粗为精的松弛技术152.1.3 由大到小的分治术162.2 分治法二分检索172.2.3 二分检索思想172.2.4 二分检索的优化最优时间下界172.2.5 代码实现182.3分治法归并分类算法182.4 斯特拉森矩阵乘法192.5快速分类202.6 课堂内容扩展各类排序方法比较21第三章：贪心算法213.1优化问题的数学基础21优化问题的分类21连续函数的优化分类：21什么是最优解223.2引入贪心算法223.3 贪心算法背包问题223.4贪心算法最小生成树23生成树的概念23最小生成树的性质23构造最小生成树，要

3、解决以下两个问题：233.5单源点最短路径233.6课题内容扩展遗传算法24第四章：动态规划254.1动态规划最短路径算法25多段图向前处理算法254.1.2 任意两点间的最短路径Floyed算法264.2动态规划最优二分检索树274.3动态规划矩阵连乘问题284.4动态规划0/1背包问题284.5动态规划TSP问题294.6动态规划流水线调度问题304.7课堂内容扩展并行的多段图动态规划30第五章：基本检索与周游的方法315.1双联通分图和深度优先检索315.2对策树32对策树在围棋应用325.3问题求解技术32相关概念335.4搜索方法（状态转移方法）33第六章：部分课堂算法的实际代码实现

4、336.1动态规划矩阵连乘实例336.2最优二叉检索树356.3多段图的最短路径求解37第七章：课程学习心得和感想42课程学习日程回顾OrderDataRemarks12014年9月27日 主讲算法的基本概念、NP难问题、P问题和一些较为基础的算法，简单提及了以“汉诺塔”为代表的递归问题的算法，并简要书写了汉诺塔的伪代码以及其时间复杂度的推算过程。22014年10月11日复习了前一堂课程的可计算性和不可计算性问题之后，讲了基础的数据结构和递归算法和简单的讲到了分治法；复杂问题的求解，提到了泰勒公式的作用和应用，割圆术的应用，雅可比迭代，缩减技术，还有分治法的伪代码的讲解。讲授了二分检索，归并分

5、类的伪代码过程和时间复杂度的推导过程以及，三数排列问题的原理，还提到了霍尔算法，然后讲了斯特拉森矩阵乘法和他的时间复杂度推导过程。32014年11月01日首先是讲了贪心算法，主要包括：背包问题。简单讲解贪心算法与动态规划的区别与联系。提到了自动成识，参数模型化，向量，两类TSP问题，多段图的顺序推导和倒序推导。42014年10月22日接着上节课内容讲授了最小生成树以及单源最短路径（Dijkstra算法求单源最短路）等问题，开始了部分动态规划的内容。52014年11月29日这一次课主要讲了动态规划的最优二分检索树。然后较为详细的讲了矩阵连乘问题，然后又讲了0/1 背包问题。62014年12月06

6、日讲了TSP商旅问题的求解方法。调度问题，和流水线上的作业调度问题。基本检索与周游方法，双联通分图和深度优先检索，详细的讲解了深度优先检索树的建立过程，72014年12月13日详细介绍了回溯法的内容，和问题求解过程，讲了回溯法求解TSP问题。然后又讲了对策树，还讲了下围棋和国际象棋的内容。第一章：算法导引关于计算机算法的学习和研究首先要了解什么事算法，其次采取考虑算法到底能够做什么，实际应用的算法的具体原理，以及设计和分析算法，算法的优化等一些问题。关于什么是算法这个问题，不同的人有不同的理解，在维基百科中是这样的：在数学和计算机科学之中，算法（Algorithm）为一个计算的具体步骤，常用于

7、计算、数据处理（英语：Data processing）和自动推理。精确而言，算法是一个表示为有限长1列表的有效方法（英语：Effective method）。在百度百科中对于算法的定义是：算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。教材中对算法的定义是：算法就是一组有穷的规则，它规定了决定某一特定类型问题的一系列运算。从上面的定义中可以看出，算法是用指令（也就是计算机的各种语言或者是机器语言等）描述的，能够完成数据处理、计算或者是能够完成一定任务的过程或方法的具体的描述。算法主要有四方面的特性：1.确定性。

8、2.能行性3.输入。4.输出5.无二义性。算法的研究工作是计算机科学这一学科中的重要工作，同样，研究算法需要具备一些相关知识理论。已经知道了什么是算法，那么算法该如何去描述呢？因为算法是解题方法及其过程的精确描述，所以描述算法的方式是没有统一规定的，但是描述算法的工具对算法的质量影响很大。算法可以使用多种不同的描述工具来表示。主要有以下几种方式来描述算法：Ø 自然语言。自然语言也就是人们日常使用的语言。使用自然语言描述算法的好处就是可以使读者比较容易接受。但是使用自然语言描述的算法具有许多缺点。首先，自然语言有时候具有歧义性，不太严格，用自然语言描述算法比较冗长，不够简洁；另外，自然

9、语言的标识性是顺序的，在描述分支和转移时不够直观。由于用自然语言描述算法存在这些缺点，因此在描述大型、复杂的算法时，用自然语言很难清楚、准确地描述出来。只有在不致引起混乱的情况下，才可以用简洁的文字来描述某一步骤的操作。Ø 专用工具。为了更直观、准确地描述算法，人们创造了许多专用的算法工具。这些算法工具有使用图形的（如流程图、N-S图、PAD图、IPO图、Warnier图），也有使用表格的（如判定表），还有使用代码符号的（如伪代码）。n 流程图。流程图是算法的图形描述工具，它用一些几何图形表示各种类型的操作。常用的流程图符号见下图所示：结构化算法有三种基本结构单元，即条件结构、选择结

10、构及循环结构。其中循环结构又可分为当型循环结构及直到型循环结构，具体表示见下图所示：例如，用流程图表示求和算法（即求1->N数字的总和）见下图：n NS图。由于传统流程图的缺点，1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图工具N-S图。N-S图完全去掉了在算法描述中引起麻烦的流程线，全部算法写在一个大的矩形框内，用不同结构的框来表示三种基本结构。图为用N-S图表示的三种基本结构，其中在一个基本结构中还可以包括另一个基本结构。由于N-S图像一个多层的盒子，也称为盒图（box diagram）。如下图所示：例如，用流程图表示求和算法（即求1->N的和

11、）见下图：在明白了有关算的内容之后之后就要了解计算机算法可以用来解决什么问题，也就是说它能做什么的问题。在实际生产中，也总会碰到一些问题，比如汉诺塔（Hanoi Tower）问题，就是算法研究中的一个经典问题，针对汉诺塔问题的研究需要考虑到两方面的因素：理论可行性。是要考虑到研究的问题在此研究领域内，在已有理论的基础上或者是在可预见的范围内是否能够有成立的可能性。问题规模。在考虑算法的这些问题的时候，同样有相似的理论，比如问题的可计算性与不可计算性，或者是可计算性与计算复杂性研究。在一些问题的研究过程中，尤其是在科学问题的研究中，刚开始的时候是完全没有任何经验可以作为依据，完全是凭借着对事物现

12、象的观察来对问题进行研究的，在这种情况下科学家们面临的问题时要在大量的观察现象中进行公式发掘、知识发现等一些颇具深度的工作。1.1 算法的设计与分析算法设计与分析的工作主要分为算法的设计和算法的验证两步骤。1.1.1 算法的设计。在应用计算机来解决实际问题时，算法设计是非常重要的。对于简单的问题，可以直接写出问题的解决方案或者是可以写出相应的算法。但是，对于大型或者是附在的问题，要一下子直接写出每一个操作步骤是比较困难的，所以可以把整个问题进行分解，采用“自顶向下，逐步细化的方法”，匆促倒吸地逐步具体化。这种从全局到局部，从抽象到具体，一步一步西化的方法是处理复杂问题的较为有效的方法。正对一个

13、问题的算法设计，首先要明确这个问题时要“做什么”的问题，可以用自然语言或是数学公式来描述“做什么”，然后逐步既然怒实现级，把一些较为抽象的东西具体化，逐步解决“如何做”的问题，然后将全部算法都描述成可由计算机实现的基本操作。这中方法叫做面向对象的解决方法。从抽象到具体的过程，做到“逐步细化”或“逐步求精”。算法设计从较为粗略的角度考虑，就是吧问题分类，而这个分类则是要求严格的分类。对于不同的问题要采取不同的方法。对于大型的问题，可以采用分割技术或分治策略，将一个问题划分为若干个独立的子问题。如果可能，字问题继续分解，直到每个子问题都比较容易处理为止，然后在着重设计解决每个字问题的详细算法。在算

14、法的底层设计中可以采用递推或者是递归技术，或采用穷举等策略使算法具体化。具体采用哪种技术或者是策略，则需要算法设计人员根据问题确定。1.1.2 算法的验证。算法验证只能说是在之前设计的算法上进行研究，只能说是算法具有什么问题，不能说是没有什么问题。每一种算法都有各自的优点和缺点或者是这个算法他是否还有可以提升效率的空间。算法验证是要完成算法的代码编写是否可以进一步优化，算法运行时所占用的内存空间能否更少以及基本的运算时间。1.1.3 算法分析。算法分析不是分析算法的具体运行时间，因为算法的运行时间与所使用的语言、机器硬件、OS（操作系统）等有关系。要分析一个算法，有两方面的问题要明确：第一，要

15、使用哪些运算以及执行这些运算所用的时间。一类是基本运算，包括加减乘除基本的整数算术运算，也包括浮点算数、比较、对变量赋值和过程调用等。另一类运算时又一些更基本的任意长序列的运算所组成（比如两个字符串的比较运算可以是一系列字符比较指令，而字符比较指令又可使用移位和位比较指令）。第二，要确定能反映出算法在各种情况下工作的数据集，即要求我们编出能产生最好、最坏和有代表性情况的数据配置，通过使用这些数据配置来运行算法，以了解算法的性能。对一个算法要做出全面地分析可分为两个阶段来进行，即使前分析（a priori analysis，求出该算法的一个时间界限函数）和事后测试（a posteriori te

16、sting，收集此算法的执行时间和实际占用空间的统计资料）。简而言之，算法分析就是研究算法随着问题规模变化时，问题会怎么样变化的工作。1.2 算法的分类对于算法的分类，在不同的标准下，所分类出来的算法也有所不同。从计算时间上可以把算法分成两类，凡可用多项式来对其计算时间界限的算法，称为多项式时间复杂度算法（polynomial time algorithm），也就是P算法。第二，指数时间复杂度算法(exponential time algorithm)，也就是NP算法。以下六种计算时间的多项式时间算法是最为常见的，其关系为：O(1)<O(logn)<O(n)<O(nlogn)

17、<O(n2)<O(n3)指数时间算法一般有O(22)、O(n!)和O(nn)等，其关系为：O(22)<O(n!)<O(nn)当n取值很大是，指数时间算法和多显示时间算法在所需时间上相差特别大，因为根本就找不到这样一个m，是的2n小于nm。换而言之，对于任意的m0，总可以找到n0，当nn0时，有22nn因此，只要有人能将现有指数时间算法中的任意一个算法简化为多项式时间算法，就取得了一个伟大的成就。如果一个算法在输入量为n的情况下计算时间为T(n)，则记作T(n)=O(f(n),他表示时间以函数f(n)为上界，T(n)=(g(n) 表示时间以函数g(n) 为下届。典型的时间

18、复杂度是指数时间。下面是常见算法的界：P算法的界：C、n、lgn、lnn、n2、 :这种算法在理论和实际都是可行的。NP算法的界：2n、n!、nn、 :这种算法在理论上是可行的，但是在实际上是没意义的。例如，TSP问题（Travelling Salesman Problem ）的时间复杂度是n！，要解决这个问题的算法的优化问题，那么就要找出他的近似算法才是最好的解决方案。对于NP算法，可以分为串行算法和前行算法，也就是数值算法和非数值算法两类。如何区分P算法问题和NP算法问题或者说是P问题和NP难问题的区别在哪？复杂度类P即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所

19、有可以在多项式时间内验证解是否正确的决定问题组成，或者等效的说，那些解可以在非确定型图灵机上在多项式时间内找出的问题的集合。（注引自Wikipedia）。其中，P算法问题相对于NP难问题来说P算法是易于计算的。NP算法是指数时间复杂度算法，是难计算的问题。当问题规模大到一定程度的时候，时间复杂度变化情况对比即NP问题，有些问题可用P算法，有些可用NP算法或只能用NP，一个问题实际用什么算法要求证明，证明可能会产生一个NP难问题。在众多问题当中，调度问题也是NP难问题，NP问题首先要考虑的是如何转换为P问题，比如TSP问题。同样这个问题的变化，也就是如何将NP难问题转换为P问题，是一个世界性难题

20、。现在人们使用虚拟计算机，让用户感知世界上所有PC如同一台PC，通过这个庞大的PC来完成一些转换工作，比如，设法找出NP难问题的近似结果，在这一过程中产生了只能计算之一学科。1.3 算法的评价算法复杂度分为时间复杂度和空间复杂度。其中，时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。课堂上指出，若使用具体执行时间来衡量一个算法的复杂性是不科学的。因为算法执行时间取决于以下几个因素：1.机器硬件。2.OS。3.编程语言。因此，我们使用渐近时间复杂度来衡量算法的复杂性，即当问题规模趋向无穷大时，该算法时间复杂度的数量级。从计算时间上，我们把算法分为多项式时间复杂度（对

21、应于P算法，属于易解决的问题），指数时间复杂度（对应于NP算法，理论可计算而实际难计算）。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。在多项式时间内验证一个解是否正确的问题称为NP问题。另外还有一类问题属于NPC问题（如TSP），该问题的解决可以通过简化问题或者寻找近似解得到解决。1.4递归算法1.4.1 Fibonacci数列递归算法（包括直接递归和间接递归子程序）都是通过自己调用自己，将求解过程转换为相同性质的子问题，最终达到求解的目的的。递归充分利用了计算机系

22、统内部技能，自动实现调用过程中相关而且必要的信息的保存与恢复，从而省略了求解过程中许多细节的描述。递归算法的例子很多，比如求解Fibonacci数列前n项和的求解就是一个很好的递归算法求解问题，对于Fibonacci数列，有 F1=F2=1，F(n)=F(n-1)+F(n-2)。求第n项Fn则有：Fn=Fn-1+Fn-2，Fn-1=Fn-2+Fn-3，Fn-2=Fn-3+Fn-4，F3=F2+F1.第n项就等于前两项的和，第n-1项就等于他前面两项的和，以此类推，就可以得到F3的值，然后再由F3得到F4，以此就可以得到第n项Fn的值了。Fibonacci数列用二叉递归程序来写是很直观的，用C+

23、语言的描述如下：long fib(int n)if(n=2|n=1)return 1;elsereturn fib(n-1)+fib(n-2);1.4.2 汉诺塔问题汉诺塔问题描述： A、B、C 三个桌子，其中A桌子上放了几个大小不同的盘子，盘子的排列顺序为： 从上到下，依次从小到大递增；现要求把这些盘子从 A 桌子上移动到 C 桌子上，盘子移动时有一点要求：每次移动必须保证三张桌子上大盘子在下、小盘子在上（如下图）；对于该算法存在两种理解：算法理解：理解1：宏观上我们可以这样理解：要将A上的n个盘子按照要求移动到C上，我们可以想到：先将上边的 n-1 个盘子移动到B上，再将A上剩余的最大的盘

24、子移动到C上，然后将B上所有的盘子移动到C上，这是比较简单的理解，但是对于算法实现的过程，还是没有弄透彻。理解2：我们知道当盘子数为n时，移动的次数应该为 2n-1；这个有公式 H(n) = 2H(n-1) +1 得来，理解为：上边的n-1个盘子先翻转到B上，将最大的盘子移动到C上，花费1步，然后将B上的盘子翻转到C上，花费2H(n-1)步。理解3：只要轮流两步操作既可以实现：首先，把三张桌子按顺序首尾相接的排列，形成一个环，然后对A上的盘子开始移动，顺时针摆放成 A B C的顺序：若n为奇数，圆盘的移动顺序是 A->C->B->A->C->B->A. 即

25、间隔两个步长移动 。此处的n代表盘子位的层数，比如说 3 层汉诺塔就是从下往上数第1、3 个盘子移动的顺序。若n为偶数，圆盘移动的顺序为A->B->C->A->B->C->A.即 间隔一个步长移动。对n的解释同上 第二个盘子移动 A->B->C。综上所述，实现汉诺塔的伪代码及运行结果如下：#include"stdafx.h"#include<iostream>usingnamespace std;void move(char src,char dest)cout<<src<<"&g

26、t;"<<dest<<endl;void hanoi(int n,char src,char medium,char dest)if(n=1)move(src,dest);elsehanoi(n-1,src,dest,medium);move(src,dest);hanoi(n-1,medium,src,dest);int main()int m;cout<<"Input the number of diskes:"cin>>m;cout<<"The steps to moving "

27、<<m<<"diskes :"<<endl;hanoi(m,'A','B','C');return 0;1.4.3 递归算法特征总结关于递归算法，有两个主要特点：第一，他在时间上重复计算，就比如上面的问题，他是从Fn到F3，然后再从F3求和到Fn，所以计算时间上是重复的,计算前50项大约用了 秒。第二，递归算法在计算空间上占用也比较大。因为计算值得过程中，要把Fn到F1的值全部保留下来，才能得到Fn，这样就使得内存开销比较大。所以在有些类递归问题上，就要考虑如何消去递归这问题。以期待得到更好

28、的解决方案。可以使用递归算法求解的问题，必须同时满足以下三个要求：1) 问题P的描述设计规模，即P(size);2) 规模发生变化后，问题的性质不发生变化。3) 问题的解决有出口。其表现形式为：Procedure P(参数表)begin if 递归出口 then 简单操作 elsebegin 简单操作；callP；简单操作 end；endp；1.5 课堂内容扩展NPC问题在这节课中，戴老师提到了NP，P问题的基础上，提了一下NPC以及NP-hard问题。这是我之前尚未涉猎的地方，因此在这部分，我将此内容列举为课堂内容的扩展。1.5.1 NPC问题描述在计算复杂度理论的世界中，NPC问题，又称N

29、P完全问题或NP完备问题，是NP（非决定性多项式时间）中最难的决定性问题。因此NP完备问题应该是最不可能被化简为P（多项式时间可决定）的决定性问题的集合。许多人推测若任何NPC问题得到多项式时间的解法，那此解法就可应用在所有NP问题上。从以上定义可以看出：同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P了。这是一个引人入胜的理论，不过目前并未有优秀的算法能让此类问题得到良好的解决。1.5.2 NP

30、C举例这里简单的列举两个比较容易理解的NPC问题。内容如下：l 旅行推销员问题：（Traveling salesman problem）；问题描述：旅行推销员问题（Travelling Salesman Problem，又称为旅行商问题、货郎担问题、TSP问题）是一个多局部最优的最优化问题：有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线。也即求一个最短的哈密顿回路。算法：穷举法，即寻找一切组合并取其最短。这种算法的排列数为n!(其中n为节点个数)。用动态规划技术，我们可以在O（N22N）时间内解决此问题。虽然这仍然是指数级的，但要比O（N！）

31、快得多。l 分团问题：（Clique problem）；问题描述：一个大小为3的clique，clique是一个图中两两相邻的一个点集，或是一个完全子图(complete subgraph)，如右图中的1, 2, 5三个点。问一个图中是否有大小是k以上的clique。证明clique problem是NP完备可以很简单的从独立顶点集问题（Independent set problem）reduce。因为存在一个大小是k以上的clique等价于它的complement graph中存在一个大小是k以上的Independent set。算法：最简单的方法是用暴力法列举图中所有k个点的子集合，并检查

32、它是不是clique。在一个有V个点的图中用暴力法找大小是k的clique至少要检查个子集合。第二章：分治法2.1分治法物体在空间中位置的表示，所采用的笛卡尔坐标系统也就三维坐标系统，他是采用了定量的思维，巧妙的把几何问题转变为解析几何，把纯几何问题转换为利用数学的方法来解决问题的方法。这是在物体的空间位置的表示的方法上是这样处理的，同样，在实际当中面临的问题多种多样，所以，人们力求将复杂问题简单化，或者说是将一个复杂问题分解转换为一些较为简单而又抽象化的问题来求解。通常所采取的方法是按照以下的步骤来对问题作多步转换以使得问题求解。实际问题当中，尤其是针对一些复杂问题的求解，这时候就要对所研究

33、的复杂问题进行分解，转换为较为简洁的问题。2.1.1 化难问题为易问题的校正问题对于问题由难到易的化简，比如我们根据以往的学习的知识很容易就可以知道4=2，但是2=？这个问题就变得稍显复杂了，那么如何将这个问题转化为一个较为简单的问题呢？一般来讲，较为复杂的问题的计算，如果需要高效的计算效率，一方面是减小问题的规模，这是从问题的本质根源的角度来解决问题的，另一方面就是在问题求解过程中提高计算的效率，比如采用高速计算，随着科学研究的进一步发展，当前的计算效率已经无法满足问题的复杂程度，尽管是高速计算，在高速计算的应用当中，就产生出来智能计算。同样在问题的转换过程中，如何将一些非线性的问题转化为线

34、性的问题，以及线性问题转换为非线性的问题，这些都是需要解决的一些难问题。在数学当中，同样有一些将复杂的多项是转换为较为简单的多项式。泰勒公式泰勒公式是可以将函数的某个点的信息描述其附近的值的公式。如果函数足够光滑的话，在已知函数在某一点的各阶导数值得情况下，泰勒公式可以用这些倒数值作系数构建一个多项是来近似函数在这一点的领域中的值。泰勒公式还给出了这个多项是和实际的函数值之间的偏差。泰勒公式中，第一项是常数，后面的部分是线性的。当一个多项是比较复杂的时候，可以对其求导，通过观察其导数的变化来反映出函数本身的情况，或者是对多项是进行多次求导求出其值得变化情况，这样问题就变得简单多了。2.1.2

35、化粗为精的松弛技术l 加权工程项目中，测量往往是不可少的一项工作，就是因为工程设计与现实情况总是存在着一些差别，比如测量过程中出现的误差，因为人为操作存在疏漏的误差或者是因为一起不够精密产生的误差等等，在这种情况下，我们就要采用多次测量的方法来尽量减小其中的误差。通常，所采用的方法是在多次测量的值中取其中的众数、平均数、或者是加全拼拘束，必要的时候需要计算其他的一些值，方差等等。这样，就将一些粗略的测量结果精细化就可以得到精确的结果。l 割圆术在古时候，为了得出一个正圆的面积，三国时代数学家刘徽发明出了割圆术。刘徽割圆术是建立在圆面积论的基础之上的。他首先论证，将圆分割成多边形，分割来越细，多

36、边形的边数越多，多边形的面积就和圆面积没有差别了。他说，将正6边形一条边的长度乘以圆半径，再乘3，得12边形的面积。将12边形的一条边长乘半径，再乘6，得24边形面积。越割越细，多边形和圆面积的差越小。如此割了再割，最后终于和圆合为一体，就毫无差别了。化大为小的缩减技术数理计算的问题中，求出n！的值就是个很好的例子。fn!=n×fn-1!,f1=1他的时间复杂度，设n!的时间复杂度为Tn,那么就有：Tn=C+Tn-1=C+(C+Tn-2)=(n-1)C+T1=nC这种情况下，n!的时间复杂度就转换为较为简单的T1的表达式了。2.1.3 由大到小的分治术接下来我们可以做出以下归纳：为解

37、决一个给定的问题，算法需要一次或多次的递归调用其自身来解决相关的子问题，即我们把一个大规模的问题划分为n个规模较小的而且结构与原来问题相似的子问题，递归解决这些子问题，然后将他们的结果分别合并，这样就得到了问题的解决方案。这即是分治法的精髓所在。通过总结可知分治法主要的特点有：Ø 通常将问题分解为比较小的问题来解决Ø 子问题与原问题有相同的类型Ø 子问题的解可以合并为该问题的解；Ø 可以用递归的过程来表示分治法的适用范围有：通常使用的分治法有二分检索，找最大值和最小值，归并分类，快速分类及解决选择问题。通过使用这些方法解决查找值，找最大或最小值，分类，选

38、择问题的时，相比一般的解决方法，分治法所消耗的时间和空间上的代价都是比较小的。分治法从步骤上可以分为三步，分解(Divide): 将一个问题为N的问题分解成一系列子问题。解决(Conquer): 递归的处理每个子问题.如果子问题足够小, 则直接给出解。合并(Combine): 把每个已经处理好的子问题合并, 得到最终的解。同样，计算机每次处理一个例子的时间复杂度我们用C来表示。分治法的思想策略是，把一个大问题分解为同类型的小问题进行求解，然后对所得到的结果进行合并，就可以达到将大问题求解的目的。分治策略的抽象化控制：procedure DANC(p,q)global n,A(1:n):inte

39、ger m,p,q; /1pqn，A(1:n)用来存储n个输入/if SMALL(p,q)thenreturn (G(p,q)/生成值得函数或者生成结果的函数/else mDIVIDE(p,q) /pm<q，可以分为多个问题，在这里是分为两个/return(COMBINE(DANDC(p,m),DANDC(m+1,q)/其中/endifend DANDC其中分治法的时间复杂度的推算过程如下：Tn=gnn足够小2Tn2+fn否则其中，Tn表示输入规模为n的DANDC时间，g(n)是对于足够小的输入规模能直接计算出答案的时间，f(n)是COMBINE的时间。2.2 分治法二分检索2.2.3

40、二分检索思想二分检索是用来解决元素是按非降序排列来查找某一元素的方法，通常采用将表中间位置记录的关键字与检索关键字比较，如果两者相等，则检索成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于检索关键字，则进一步检索前一子表，否则进一步检索后一子表。重复以上过程，直到找到满足条件的记录，使检索成功，或直到子表不存在为止，此时检索不成功。对于一个含有n个元素的给定序列I=(a1,a2,a3,an)，要实现查找某个元素是否在I中出现且返回其下标值。通常这样的问题完成查找的时间复杂度为O(n)。但二分查找算法则更优，因为其查找时间为O(logn)，其思想是不断将数组进行对半

41、分割，每次拿中间元素和目标元素进行比较。这个问题的描述可以表示为：I=(n,a1,a2,an,x),其中x是要查找的元素。将他分解成几个子问题，一种是，选一个下标为k，由此得到3个子问题：I1=k-1,a1,a2,ak-1,x,I2=1,ak,xI3=n-1,ak+1,ak+2,an,x。三者中，对于I2比较x和ak就容易得到解决，如果x=ak，则有j=k且不对I1，I3进行求解；否则，在I2子问题中的j=0，此时，如果x<ak,则只有I1用来求解，在I3子问题中的j=0.如果，x> ak,只有I3用来求解，在I1子问题中的j=0.在和ak做比较之后，留下的子问题再一次做相同的分治

42、方法来处理，知道得出结果。在此过程中，如果每一次选取的下标的值k都是中间元素的下标，即：k=(n+1)2,产生的算法也就是二分检索法。2.2.4 二分检索的优化最优时间下界如何确定以比较为基础进行二分检索的最优时间下界？这个问题就可以转化为二叉树问题，比如，当n=5时，则二叉树的节点数据为5个，他的最小高度是多少？同样，总结点数为n，树的高度最小为多少，最大为多少的问题。时间复杂度最好的情况是2h-1=nh=log2(n+1)。2.2.5 代码实现int BinSearch(int sSource, int array_size, int key) int low = 0, high = ar

43、ray_size - 1, mid; while (low <= high) mid = (low + high) / 2;/获取中间的位置if (sSourcemid = key) return mid; /找到则返回相应的位置if (sSourcemid > key) high = mid - 1; /如果比key大则往低的位置查找else low = mid + 1; /如果比key小，则往高的位置查找 return -1; 2.3分治法归并分类算法归并分类，在给定的n个元素的集合，如果把他们按照一定的次序分类，最直接的方法就是插入法，对A（1：n）中元素作插入法的基本思想是

44、,从序列的第二个元素开始遍历，把每一个遍历的元素放到已经分类好的子集的位置上，但是这样的操作，在A(j)插入时，有可能会移动A(1:j-1)的所有元素。这个过程最坏的情况界限是2jnj=nn+12-1=(n2)如果输入数据本来就是按照非将此排序的，那么最好的情况，计算时间是(n).如果使用分类策略来设计分类算法的，则可使最坏情况时间变为O(nlogn).归并分类算法。算法的基本思想是：将A(1),A(n)分成两个集合A(1),A(n/2)和A(n/2+1),A(n).对每一个集合单独分类，然后将已分类的两个序列归并成一个含n个元素的分好类的序列。如下图：图一：归并分类举例归并分类的控制过程表示

45、如下：procddure MERGESORT(low,length)integer low,length;if low<length;then mid<(low+length)/2call MERGESORT(low,mid); call MERGESORT(mid+1,length) call merge(low,mid,length)end ifend MERGESORT时间复杂度推算：Tn=2Tn2+C=22Tn22+C×n2+C×n=22Tn22+2×C×n=23Tn23+22×C×n=24Tn24+23×

46、;C×n=2lognT1+C×n×logn,当n2k=1时=C1×n+C×n×lognn=log2k推算最优的时间复杂度：2T(n)n!n2n2,Tnn2×logn2当n大于等于4时，T(n)n2×logn2n4×n×logn,n=low是排序方法的最优情况,以比较为基础的分类算法的最坏情况的时间下界为(nlogn)。2.4 斯特拉森矩阵乘法假设有连个矩阵想成得到另外一个矩阵：Am×n×Bn×l=Cm×l，三个矩阵的元素分别为aij,bij,cij,其中C

47、ij=i=1maik×bkj,这样，计算每一个C(i,j)需要做m次乘法和m-1次假发，而乘积矩阵C有m2个元素，因此，由矩阵乘定义直接产生的矩阵乘算法的时间为n3。针对这个n3，科学家斯特拉森（V.Strassen）采用分支策略进行了改进，得到的算法的计算时间为n2.81.斯特拉森矩阵乘法的基本思想是：将两个相乘的矩阵（假设都是n阶）利用矩阵分块法的性质，把每个矩阵分成4个n/2阶的子矩阵并施以通常的矩阵乘法运算。如果分块子矩阵的阶数大于2阶，那么就再把每一个子矩阵进行分块，知道每个子矩阵只含有一个元素，以至于可以直接计算其乘积为止。对于两个n阶矩阵相乘，采用分支算法的时间复杂度T

48、(n)可以表示为如下递归关系式：Tn=b, n28Tn2+dn2,n>2经过推导得到(c+1)nlog7=O(nlog7)O(22.81)。2.5快速分类快速分类是通过选取A（1：n）的某个元素，然后将其他元素重新排列，使A（1：n）中所有在t以前出现的元素都小于或等于t，而所有在t后面出现的元素都大于或等于t。分类例子如下图。这种重新整理叫做划分，元素t=3称为划分元素。因此，所谓快速分类就是通过反复对产生的文件进行划分来实现的。快速分类根据数据的大小，最坏时间复杂度为O(n2),而平均情况却为O(nlogn);图二：快速分类算法举例实际的简要代码实现：procedure QUICKS

49、ORT(p,q) /将全程数组A（1：n）中的元素A（p），A（q）按递增的方式分类。认为A（n+1）已被定义，且大于或等于A（p：q）的所有元素，即A（n+1）=+/integer p,q； global n,A(1:n);if p<q; then j<q+1 call PARTITION(p,j) /j是划分元素的位置/ call QUICKSORT(p,j-1) call QUICKSORT(j+1,q) endifend QUICKSORT2.6 课堂内容扩展各类排序方法比较表一：各分类算法时间复杂度比较排序方法简单排序快速排序堆排序归并排序基排序时间复杂度O(n2)

50、60; O(nlogn)O(nlogn) O(nlogn) O(d(n+rd)其中，直接插入排序、冒泡排序为简单排序。在实际应用中，应该根据实际的情况作出选择。首先考虑排序对稳定性的要求，若要求稳定，则只能在稳定的方法中选取，否则可以在全部的方法中选取；其次考虑其丢弃结点数n的大小，若n较大，则可以在改进的方法中选取，否则在简单的方法中选取；然后再考虑其它的一些因素。大致有以下结论：      1、当待排序的结点数n较大时，关键字的值分布比较随机，并且对排序稳定性不作要求时，宜选取快速排序法；  

51、;    2、当待排序的结点数n较大时，内存空间又允许，并且要求排序稳定时，宜采用归并排序法；      3、当待排序的结点数n较大时，关键字的值的分布可能出现升序或者逆序的情况，并且对排序稳定性不作要求时，宜采用堆排序方法或者归并排序法；      4、当待排序的结点数n较小时，关键字的值基本有序（升序）或者分布比较随机，并且有排序稳定性要求时，宜采用插入排序法；      5、当待排序的结点数n较小时，对排序稳定

52、性不作要求时，宜采用选择排序方法，若关键字的值不接近逆序，也可以采用直接插入排序法；      6、已知两个有序表，若要将它们组合成一个新的有序表，最好的方法就是归并排序法。第三章：贪心算法3.1优化问题的数学基础优化问题的分类l 线性函数的优化与非线性函数的优化l 约束与无约束优化（以等高线和梯度为例）l 确定性优化与随机优化l 静态优化与动态优化（TSP与DTSP为例）l 单目标优化与多目标优化连续函数的优化分类：Ø 函数优化问题，出现高维，非线性，不连续，没有明确表达式时可以使用演化算法，例如遗传算法。Ø 模型参数优化

53、：根据经验或者是专业知识，可使用最小二乘法进行拟合。Ø 模型优化：使用泰勒公式对复杂函数进行转换，使之成为多项式，进行分段拟合等。介绍了自动程序设计/模型挖掘，使用CA，GEP(基因表达式程序设计。什么是最优解对于有n个输入的问题，其找到的解就是这n个输入的子集，只是这个子集必须满足某些事先给定的条件，但是满足条件的自己可能有很多个，我们就把这些必须满足的条件称为约束条件，把这些满足约束条件的子集称之为这个要求解的问题的可行解。为了衡量可行解的优劣，事先也给出了一定的判断标准，这些判断标准一般以函数的形式给出，这些函数称之为目标函数，那些使目标函数取得极大值或极小值的可行解称之为最优

54、解。3.2引入贪心算法贪心算法是分级处理方法的改进，贪心算法的两个要素是：第一，选取一种度量标准。第二，按照度量标准依次用n次后输入n个每个排序后的输入。如果当前输入和已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解当中去。这种能够得到某种量度意义下的最优解分级处理方法称之为贪心方法。贪心方法的抽象化控制如下所示：procedure GREEDY(A,n)/A(1:n)包含n个输入/Solution /将解向量 solution 初始化为空 /for i<- 1 to n do /分级处理方法度量标准/ x<-SELECT(A)/按照度量标准，

55、从A中选择一个输入，并赋值于x，并将2从A中删除/ if FEASIBLE(solution,x)/布尔函数，判定x是否可以包含在解向量中/then solution<-UNION(solution)/UNION函数判定x是否包含在解向量中，将x与解向量合并修改目标函数/endifrepeatreturn (solution)end GREEDY3.3 贪心算法背包问题背包问题的描述是这样的，有n种物品和一个可以容纳M质量的背包，每个物品i的质量为Wi。假定将物品i的一部分x放入背包就会得到pixi的效益，其中：0xi1,pi>0.如何达到装包效益最大化的目的，我们就要考虑哪些物品

56、需要装包，哪些物品不需要装包的问题。如果物品的总重量小于等于M，那么自然是全部装入背包就是效益最大化，如果给定物品的总重量大于M，那么这个问题就要添加一定的约束条件。效益极大化目标函数：1inpixi约束条件：1inwixiM装包总质量不能超过M，即不能把背包撑破了0xi1,pi>0,wi>0,1in满足约束条件的任一集合（x1,x2,x3 ,.xi）都是可行解，目标函数取得最大值的可行解叫做最优解，即最佳装包方案。贪心算法的抽象化控制语言：procedure GREEDY(A,n)/A(1:n)包含n个输入/Solution /将解向量 solution 初始化为空 /for i

57、<- 1 to n do /分级处理方法度量标准/ x<-SELECT(A)/按照度量标准，从A中选择一个输入，并赋值于x，并将2从A中删除/ if FEASIBLE(solution,x)/布尔函数，判定x是否可以包含在解向量中/then solution<-UNION(solution)/UNION函数判定x是否包含在解向量中，将x与解向量合并修改目标函数/endifrepeatreturn (solution)end GREEDY3.4贪心算法最小生成树生成树的概念 连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树。最小生成树的性质用哲学的观点来说，每个事物都有自己特有的性质，那么图的最小生