搜索
算法设计与分析云南大学廖鸿志2020/3/232内容计算模型和计算复杂性的测度数据结构与递归技术分治与平衡排序动态规划贪心法回溯法分枝限界法2020/3/233第一章计算模型和计算复杂性的测度2020/3/2341.1引言1.算法的概念基本上几乎所有的程序都是为了实现某种算法，简言之算法就是处理问题的步骤与逻辑，它是有穷规则的有序集合。算法分为数值算法与非数值算法。数值算法有：概率统计计算、线性代数计算、数值逼近、数值微分、数值积分、数学规划等。数值算法是通用的，一般可用解析式表示：而非数值算法只是思想或思路，要根据具体问题按这种思想或思路进行设计。2020/3/2351.1引言2算法的特征(1)有穷性：算法应该是有穷规则，在有穷步骤后终止。(2)确定性：算法的任何一步都应该有且仅有一个解释。(3)能行性：算法应该符合问题的要求，应该在有限时间内完成。(4)输入与输出：有零个或多个外部量作为算法的输入，算法产生至少一个量作为输出。2020/3/2361.1引言程序与算法不同，程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。例如操作系统，它是在无限循环中执行的程序，因而它并不是算法。然而可以将它的各种任务看成一些单独的问题。每一个问题由操作系统的一个子程序通过特定的算法实现。该子程序在得出输出结果后便终止。2020/3/2371.1引言3算法设计与分析的步骤(1)问题的描述：明确输入与输出。(2)建立模型：将核心内容模型化，逻辑化。(3)算法设计与正确性证明：对所有正确的输入都能得到正确的输出（一般需要用谓词逻辑来证明）。(4)程序实现：用某种程序设计语言来实现。(5)算法分析：在程序实现之前进行。2020/3/2381.2计算复杂性的测度算法的计算复杂性(computationalcomplexity)是衡量算法计算难度的尺度，使用最普遍的标准是一个算法需要耗费的时间和空间。算法所需要的时间或空间，通常是问题规模的函数，这个函数就叫做算法的时间或空间复杂度。在实际中用算法主操作的重复次数来表示算法的时间复杂度。2020/3/2391.2计算复杂性的测度问题的规模：也就是该问题所谓的体积，或者说是大小。一个问题的体积可以用一个整数来表示，它是对问题的输入数据或初始数据的多少的一种量度。定义：如果一个问题的体积是n，解决这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称作这一算法的“时间复杂性”。当输入量n逐渐增大时，T(n)的极限情形就称作算法的“渐近时间复杂性”，类似可定义算法的空间复杂性。但实际上人们主要是研究算法的时间复杂性而很少讨论它们的空间耗费。2020/3/23101.2计算复杂性的测度一个算法的复杂性函数的量级是反映算法效能的重要标准。当输入量急剧地增大时，如果设有高效能的算法，单纯依靠提高计算机的速度，有时是很不理想的。设有五个算法A1，A2，A3，A4，A5，它们的时间复杂性函数如下表所示：表中，一个算法的时间复杂性是它处理完一个大小为n的输入所需要的的单位时间数。2020/3/2311例例1.39个景点的全排列39！=2.04×1046用每秒处理1亿次（108）逻辑的计算机，需耗时6.5×1022亿年例2.下围棋3361=1.74×10172=5.52×10146亿年例3.电梯从1楼到10楼，有多少种可能的方式？2020/3/2312算法时间复杂性函数A1T1(n)=nA2T2(n)=nlog2n(nlogn)A3T3(n)=n²A4T4(n)=n³A5T5(n)=2ⁿ1.2计算复杂性的测度2020/3/2313算法时间复杂性一秒钟内所能处理的最大输入量一分钟内所能处理的最大输入量一小时内所能处理的最大输入量A1A2A3A4A5nn㏒2nn²n³2ⁿ1000140311096×104489324439153.6×1062.0×1051897153211.2计算复杂性的测度2020/3/2314算法时间复杂性速度提高前单位时间里所能处理的数据量速度提高十倍后单位时间里所能处理的数据量速度提高一万倍后单位时间里所能处理的数据量A1A2A3A4A5nn㏒2nn²n³2ⁿS1S2S3S4S510S1(S2很大)10S23.16S32.15S4S5+3.3210000S1(㏒2S2≥9㏒29000)9000S2100S321.54S4S5+13.321.2计算复杂性的测度2020/3/23151.2计算复杂性的测度现有问题可以分为以下三类：无法写出算法的问题；有以多项式为界的算法存在的问题，即Ｐ类问题；介于前两类问题之间的问题，“ＮＰ——完全”问题。2020/3/23161.3随机存取模型自学2020/3/2317第二章数据结构和递归技术2020/3/2318表、树、图表：a1,a2,a3,…,ai,ai+1,…an是一个数据元素，ai-1为ai的前驱，ai+1为其后继。第一个元素没有前驱，最后一个数据元素没有后继。顺序存储：数组链式存储：链表2020/3/23192.1图和图的表示邻接矩阵邻接表邻接向量关联矩阵一般有以上几种图的常用表示法2020/3/23202.2树仅有一个没有边进入的顶点，这个顶点称为这棵树的根；除根以外的其它任何顶点，有且只有一条边进入该顶点；从根到每一个顶点都有一条唯一的道路。2020/3/23212.2树二叉树：根最多有两个孩子，若有左子，左孩子为二叉树；若有右孩子，右孩子为二叉树。完全二叉树：结点深度最多差1，除没有孩子的结点所在层为满二叉树，没有孩子的结点集中在左边。满二叉树：所有叶片的深度都相等的完全二叉树。2020/3/23222.2树树的遍历先序遍历中序遍历后序遍历2020/3/23232.3递归技术一个直接或间接地调用自身的过程称为递归过程(recursiveprocedure)；一个直接或间接地调用自身的算法称为递归算法。一个使用函数自身给出定义的函数叫做递归函数(recursivefunction)。在算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。有些数据结构如二叉树等，由于其本身固有的递归特性，特别适合用递归的形式来描述。还有一些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解使设计出的算法简洁易懂且易于分析。2020/3/23242.3递归技术例2.5阶乘函数阶乘函数可以递归地定义为：2020/3/23252.3递归技术定义式的左右两边都引用了阶乘记号，是一个递归定义式，可递归地计算如下：intFactorial(intn){if(n==0)return1;elsereturnn*Factorial(n-1);}2020/3/23262.3递归技术例2.6Fibonacci数列无穷数列1,1,2,3,5,8,13,21,34,55,...，称为Fibonacci数列或级数。它可以递归地定义为：2020/3/23272.3递归技术第n个Fibonacci数可以递归地计算如下：intFibonacci(intn){if(n≤1)return1;elsereturnFibonacci(n-1)+Fibonacci(n-2);}2020/3/23282.3递归技术上述两例中的函数也可以用如下的非递归方式定义：2020/3/23292.3递归技术并非一切递归函数都能用非递归方式定义。为了对递归函数的复杂性有更多的了解，我们再介绍一个双递归函数——Achkerman函数。当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。2020/3/23302.3递归技术Acheman函数A(n,m)有两个独立的整变量m≥0和n≥0，其定义如下：2020/3/23312.3递归技术A(n,m)的自变量m的每一个值都定义了一个单变量函数。由递归式的第三式可知m=0定义了函数“加2”。当m=1时，由于A(1,1)=A(A(0,1),0)=A(1,0)=2以及A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2(n1)，则A(n,1)=2n(n≥1)，即A(n,1)是函数“乘2”当m=2时由于A(n,2)=A(A(n-1,2),1)=2A(n-1,2)以及A(1,2)=A(A(0,2),1)=A(1,1)=2，则有A(n,2)=2的n次方2020/3/23322.3递归技术大家可以试着算一下A(2,10)和A(3,4)答案分别是：222```2｝10个2222```2｝65536个22020/3/23332.3递归技术2.3.1整数划分把一个正整数n表示成如下形式的一系列正整数的和，叫做n的一个划分。2020/3/23342.3递归技术正整数n的不同划分个数称为正整数n的划分数，记作P(n)，P(n)是一个数论函数。例如：正整数6有如下11种不同的划分，所以P(6)=11。这11个划分分别是：6;5+1;4+2,4+1+1;3+3,3+2+1,3+1+1+1;2+2+2,2+2+1+1,2+1+1+1+1;1+1+1+1+1+1。2020/3/23352.3递归技术将最大加数n1不大于m的划分个数记作Q(m,n)。我们可以建立如下的递归关系。1.Q(n,1)=1,n≥1;当最大加数n1不大于1时，任何正整数n只是有种切分形式，即n=1+1+...+1，n个1相加。2.Q(n,m)=Q(n,n),m≥n;最大加数n1实际上不能大于n。因此，Q(1,m)=1。3.Q(n,n)=1+Q(n,n-1);正整数n的划分由n1=n的划分和n1≤n-1的划分组成。4.Q(n,m)=Q(n,m-1)+Q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1的划分组成。2020/3/23362.3递归技术以上的关系实际上给出了计算Q(n,m)的递归式如下：2020/3/23372.3递归技术可以设计出计算Q(n,m)的递归算法如下：intQ(intn,intm){if((n1)||(m1))return0;if((n==1)||(m==1))return1;if(nm)returnQ(n,n);if(n==m)returnQ(n,m-1)+1;elsereturnQ(n,m-1)+Q(n-m,m);}2020/3/23382.3递归技术Hanoi塔问题设a,b,c是3个塔座。开始时，在塔座a上一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,...,n2020/3/23392.3递归技术现在要求将塔座a上的这些圆盘移到b上，并仍按有序位置叠置。在移到圆盘时应该遵守以下规则：1.每次只能移动一个圆盘；2.任何时刻都不允许将大盘压在小盘上；3.在满足规则1和规则2的前提下，可将圆盘移至a,b,c中任何一个塔座上。2020/3/23402.3递归技术这人问题有一个简单的解法。假设塔座a,b,c排成一个三角形，a-b-c-a构成顺时针循环。在移动圆盘的过程中，若是奇数次移动，则将最小的圆盘移到顺时针方的下一塔座上；若是偶数次移动，则保持最小的圆盘不动。而在其他两个塔座这间较小的圆盘移到另一塔座上去。2020/3/23412.3递归技术当n=1时，问题比较简单，只要将编号为1的圆盘从塔座a直接移至b上即可。当n1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘按规则从塔座a移至塔座c，然后将剩下的最大圆盘从塔座a移至塔座b，最后再设法将n-1个较小的圆盘按规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可以分为两次n-1个圆盘的移动问题。2020/3/23422.3递归技术可以设计出解Hanoi塔问题的递归算法如下：voidHanoi(intn,inta,intb,intc){if(n0){Hanoi(n-1,a,c,b);move(a,b);Hanoi(n-1,c,