算法设计与分析课件

算法设计与分析云南大学廖鸿志2024/12/292内容计算模型和计算复杂性的测度数据结构与递归技术分治与平衡排序动态规划贪心法回溯法分枝限界法2024/12/293第一章计算模型和计算复杂性的测度2024/12/2941.1引言1.算法的概念基本上几乎所有的程序都是为了实现某种算法，简言之算法就是处理问题的步骤与逻辑，它是有穷规则的有序集合。算法分为数值算法与非数值算法。数值算法有：概率统计计算、线性代数计算、数值逼近、数值微分、数值积分、数学规划等。数值算法是通用的，一般可用解析式表示：而非数值算法只是思想或思路，要根据具体问题按这种思想或思路进行设计。2024/12/2951.1引言2算法的特征(1)有穷性：算法应该是有穷规则，在有穷步骤后终止。(2)确定性：算法的任何一步都应该有且仅有一个解释。(3)能行性：算法应该符合问题的要求，应该在有限时间内完成。(4)输入与输出：有零个或多个外部量作为算法的输入，算法产生至少一个量作为输出。2024/12/2961.1引言程序与算法不同，程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。例如操作系统，它是在无限循环中执行的程序，因而它并不是算法。然而可以将它的各种任务看成一些单独的问题。每一个问题由操作系统的一个子程序通过特定的算法实现。该子程序在得出输出结果后便终止。2024/12/2971.1引言3算法设计与分析的步骤(1)问题的描述：明确输入与输出。(2)建立模型：将核心内容模型化，逻辑化。(3)算法设计与正确性证明：对所有正确的输入都能得到正确的输出（一般需要用谓词逻辑来证明）。(4)程序实现：用某种程序设计语言来实现。(5)算法分析：在程序实现之前进行。2024/12/2981.2计算复杂性的测度算法的计算复杂性(computationalcomplexity)是衡量算法计算难度的尺度，使用最普遍的标准是一个算法需要耗费的时间和空间。算法所需要的时间或空间，通常是问题规模的函数，这个函数就叫做算法的时间或空间复杂度。在实际中用算法主操作的重复次数来表示算法的时间复杂度。2024/12/2991.2计算复杂性的测度问题的规模：也就是该问题所谓的体积，或者说是大小。一个问题的体积可以用一个整数来表示，它是对问题的输入数据或初始数据的多少的一种量度。定义：如果一个问题的体积是n，解决这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称作这一算法的“时间复杂性”。当输入量n逐渐增大时，T(n)的极限情形就称作算法的“渐近时间复杂性”，类似可定义算法的空间复杂性。但实际上人们主要是研究算法的时间复杂性而很少讨论它们的空间耗费。2024/12/29101.2计算复杂性的测度一个算法的复杂性函数的量级是反映算法效能的重要标准。当输入量急剧地增大时，如果设有高效能的算法，单纯依靠提高计算机的速度，有时是很不理想的。设有五个算法A1，A2，A3，A4，A5，它们的时间复杂性函数如下表所示：表中，一个算法的时间复杂性是它处理完一个大小为n的输入所需要的的单位时间数。2024/12/2911例例1.39个景点的全排列

39！=2.04×1046

用每秒处理1亿次（108）逻辑的计算机，需耗时6.5×1022亿年例2.下围棋

3361=1.74×10172=5.52×10146亿年例3.电梯从1楼到10楼，有多少种可能的方式？

2024/12/2912算法时间复杂性函数A1T1(n)=nA2T2(n)=nlog2n(nlogn)A3T3(n)=n²A4T4(n)=n³A5T5(n)=2ⁿ1.2计算复杂性的测度2024/12/2913算法时间复杂性一秒钟内所能处理的最大输入量一分钟内所能处理的最大输入量一小时内所能处理的最大输入量A1A2A3A4A5nn㏒2nn²n³2ⁿ1000140311096×104489324439153.6×1062.0×1051897153211.2计算复杂性的测度2024/12/2914算法时间复杂性速度提高前单位时间里所能处理的数据量速度提高十倍后单位时间里所能处理的数据量速度提高一万倍后单位时间里所能处理的数据量A1A2A3A4A5nn㏒2nn²n³2ⁿS1S2S3S4S510S1(S2很大)10S23.16S32.15S4S5+3.3210000S1(㏒2S2≥9㏒29000)>9000S2100S321.54S4S5+13.321.2计算复杂性的测度2024/12/29151.2计算复杂性的测度现有问题可以分为以下三类：无法写出算法的问题；有以多项式为界的算法存在的问题，即Ｐ类问题；介于前两类问题之间的问题，“ＮＰ——完全”问题。2024/12/29161.3随机存取模型自学2024/12/2917第二章数据结构和递归技术2024/12/2918表、树、图表：a1,a2,a3,…,ai,ai+1,…an是一个数据元素，ai-1为ai的前驱，ai+1为其后继。第一个元素没有前驱，最后一个数据元素没有后继。顺序存储：数组链式存储：链表2024/12/29192.1图和图的表示邻接矩阵邻接表邻接向量关联矩阵一般有以上几种图的常用表示法2024/12/29202.2树仅有一个没有边进入的顶点，这个顶点称为这棵树的根；除根以外的其它任何顶点，有且只有一条边进入该顶点；从根到每一个顶点都有一条唯一的道路。2024/12/29212.2树二叉树：根最多有两个孩子，若有左子，左孩子为二叉树；若有右孩子，右孩子为二叉树。完全二叉树：结点深度最多差1，除没有孩子的结点所在层为满二叉树，没有孩子的结点集中在左边。满二叉树：所有叶片的深度都相等的完全二叉树。2024/12/29222.2树树的遍历先序遍历中序遍历后序遍历2024/12/29232.3递归技术一个直接或间接地调用自身的过程称为递归过程(recursiveprocedure)；一个直接或间接地调用自身的算法称为递归算法。一个使用函数自身给出定义的函数叫做递归函数(recursivefunction)。在算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。有些数据结构如二叉树等，由于其本身固有的递归特性，特别适合用递归的形式来描述。还有一些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解使设计出的算法简洁易懂且易于分析。2024/12/29242.3递归技术例2.5阶乘函数阶乘函数可以递归地定义为：2024/12/29252.3递归技术定义式的左右两边都引用了阶乘记号，是一个递归定义式，可递归地计算如下：intFactorial(intn){ if(n==0) return1; else returnn*Factorial(n-1);}2024/12/29262.3递归技术例2.6Fibonacci数列无穷数列1,1,2,3,5,8,13,21,34,55,...，称为Fibonacci数列或级数。它可以递归地定义为：2024/12/29272.3递归技术第n个Fibonacci数可以递归地计算如下：intFibonacci(intn){ if(n≤1) return1; else returnFibonacci(n-1)+Fibonacci(n-2);}2024/12/29282.3递归技术上述两例中的函数也可以用如下的非递归方式定义：2024/12/29292.3递归技术并非一切递归函数都能用非递归方式定义。为了对递归函数的复杂性有更多的了解，我们再介绍一个双递归函数——Achkerman函数。当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。2024/12/29302.3递归技术Acheman函数A(n,m)有两个独立的整变量m≥0和n≥0，其定义如下：

2024/12/29312.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(n>1)，则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次方2024/12/29322.3递归技术大家可以试着算一下A(2,10)和A(3,4)答案分别是：222```2｝10个2222```2｝65536个22024/12/29332.3递归技术2.3.1整数划分把一个正整数n表示成如下形式的一系列正整数的和，叫做n的一个划分。2024/12/29342.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。2024/12/29352.3递归技术

将最大加数n1不大于m的划分个数记作Q(m,n)。我们可以建立如下的递归关系。Q(n,1)=1,n≥1;当最大加数n1不大于1时，任何正整数n只是有种切分形式，即n=1+1+...+1，n个1相加。Q(n,m)=Q(n,n),m≥n;最大加数n1实际上不能大于n。因此，Q(1,m)=1。Q(n,n)=1+Q(n,n-1);正整数n的划分由n1=n的划分和n1≤n-1的划分组成。Q(n,m)=Q(n,m-1)+Q(n-m,m),n>m>1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1的划分组成。2024/12/29362.3递归技术以上的关系实际上给出了计算Q(n,m)的递归式如下：2024/12/29372.3递归技术可以设计出计算Q(n,m)的递归算法如下：intQ(intn,intm){ if((n<1)||(m<1)) return0; if((n==1)||(m==1)) return1; if(n<m) returnQ(n,n); if(n==m) returnQ(n,m-1)+1; else returnQ(n,m-1)+Q(n-m,m);}2024/12/29382.3递归技术Hanoi塔问题设a,b,c是3个塔座。开始时，在塔座a上一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,...,n2024/12/29392.3递归技术现在要求将塔座a上的这些圆盘移到b上，并仍按有序位置叠置。在移到圆盘时应该遵守以下规则：每次只能移动一个圆盘；任何时刻都不允许将大盘压在小盘上；在满足规则1和规则2的前提下，可将圆盘移至a,b,c中任何一个塔座上。2024/12/29402.3递归技术这人问题有一个简单的解法。假设塔座a,b,c排成一个三角形，a->b->c->a构成顺时针循环。在移动圆盘的过程中，若是奇数次移动，则将最小的圆盘移到顺时针方的下一塔座上；若是偶数次移动，则保持最小的圆盘不动。而在其他两个塔座这间较小的圆盘移到另一塔座上去。2024/12/29412.3递归技术当n=1时，问题比较简单，只要将编号为1的圆盘从塔座a直接移至b上即可。当n>1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘按规则从塔座a移至塔座c，然后将剩下的最大圆盘从塔座a移至塔座b，最后再设法将n-1个较小的圆盘按规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可以分为两次n-1个圆盘的移动问题。2024/12/29422.3递归技术可以设计出解Hanoi塔问题的递归算法如下：voidHanoi(intn,inta,intb,intc){ if(n>0) { Hanoi(n-1,a,c,b); move(a,b); Hanoi(n-1,c,b,a); }}2024/12/29432.3递归技术二叉树中序遍历递归算法VoidMidOrder(root){ if(root!=null) { MidOrder(root->lchild); treat(root); MidOrder(root->rchild); }}2024/12/29442.3递归技术算法Hanoi以递归形式给出，每个圆盘的具体移动方式不清楚，因此很难用手工移动来模拟这个算法。但该算法易于理解，也容易证明其正确性，而且易于掌握它的设计思想。由昆可见，用递归技术来设计算法很方便，而且设计出的算法往往比通常的算法有效。2024/12/29452.3递归技术2.3.3递归过程的实现像Hanoi这们的递归算法，在执行时需要多次调用自身。实现这种递归调用的关键是为算法建立递归调用工作栈。2024/12/29462.3递归技术通常，在一个算法中调用另一个算法时，系统需要在运行被调用算法之前先完成3件事：将所有实参指针，返回地址等信息传递给被调用算法；为被调用算法的局部变量分配存储区；将控制转移到被调用算法的入口2024/12/29472.3递归技术在从被调用算法返回调用算法时，系统也相应地完成3件事：保存被调用算法的计算结果；释放根本给被调用算法的数据区；依照被调用算法保存的返回地址将控制转移到调用算法。2024/12/29482.3递归技术当有多个算法构成嵌套调用时，按照后调用先返回的原则进行。递归算法之间的信息传递和控制转移必须通过栈来实现，即系统闺怨整个程序运行时所需要的数据空间安排在一个栈中，每调用一个算法，就为它在栈顶分配一个存储区，每退出一个算法，就释放它在栈顶的存储区。当前正在运行的算法的数据一定在栈顶。2024/12/29492.3递归技术2024/12/29502.4解递归方程对于k阶齐次方程

F(n)=a1F(n-1)+a2F(n-2)+…+akF(n-k)，已知：F(0),F(1),…,F(k-1)共k个初值特征方程为：

xk-a1xk-1-a2xk-2-…-ak-1x–ak=0；有k个根q1,…,qk2024/12/29512.4解递归方程qi(i=1…k)互不相同，通解如下：

F(n)=C1q1n+C2q2n+…+Ckqkn若有重根q1≠q2≠…≠qi=…=qi+r-1≠qi+r≠…≠qk

，通解为：

F(n)=C1q1n+C2q2n+…+ Ci-1qi-1n+(Ci+Ci+1n+…+Ci+r-1nr-1)qin

+Ci+rqi+rn+…+Ckqkn2024/12/29522.4解递归方程对于k阶非齐次方程

F(n)=a1F(n-1)+a2F(n-2)+… +akF(n-k)+f(n)通解为：F(n)=F,(n)+F*(n)。其中F’(n)为无f(n)时的通解，即k阶齐次方程的通解，F*(n)为特解

2024/12/29532.4解递归方程先写出特征方程然后根据k个初值求出待定参数Ci最后验证2024/12/29542.4解递归方程练习1F(n)=7F(n-1)–12F(n-2);F(0)=4,F(1)=0解：特征方程为x2-7x+12=0； 解得：x1=3，x2=4；F(n)=C13n+C24n ∵F(0)=4,F(1)=0

∴C1=16，C2=-12

∴F(n)=16×3n-12×4n2024/12/29552.4解递归方程练习2F(n)=6F(n-1)–9F(n-2)+3 F(0)=0,F(1)=1解：特征方程为x2-6x+9=0； 解得：x1=x2=3；F(n)=(C1+nC2)3n+C3×3

∵F(0)=0,F(1)=1,F(2)=6,F(1)-9F(0)+3=9

∴C1=-3/4，C2=5/6，C3=1/4

∴F(n)=-3/4×3n+5/6×3n+3/42024/12/29562.4解递归方程练习3F(n)=7F(n-1)–10F(n-2)+3n F(0)=0,F(1)=1解：特征方程为x2-7x+10=0； 解得：x1=2，x2=5；

F(n)=C12n+C25n+C33n ∵F(0)=0,F(1)=1,F(2)=7F(1)-10F(0)+32=16

∴C1=8/3，C2=11/6，C3=-9/2

∴F(n)=8/3×2n+11/6×5n-9/2×3n2024/12/2957第三章分治与平衡

杨素勤（１２００６００９８５）2024/12/2958分治与平衡的思想把一个问题分成k个同类子问题处理的分治思想和子问题规模大体相等的平衡思想（balancing）相结合,即为分治与平衡算法.2024/12/2959两个非递减序列的合并下面将介绍两个有序非递减序列如何合并为一个有序序列：给定两个非递减有序数列和把这两个序列按非递减有序合并入。分别取出两个序列中的第一个元素，对这两个元素进行比较。如果a1不大于b1,则将a1存入c1，取出a2与b1进行比较。如果a1大于b1则将b1存入c1取出b2与a1进行比较。重复上述步骤，直到两个序列完全合并。2024/12/2960两个非递减序列合并的算法将：和合并存入ProcedureMERGEI

i=1;j=1;k=1;While(i<=m)and(j<=n)doIfA[i]<=B[j]thenbeginC[k]=A[i];i=i+1;k=k+1;end;2024/12/2961两个非递减序列合并的算法elseC[k]=B[j];j=j+1;k=k+1;end;ifi>mthen{将bj、bj+1、…、bn

依次赋值给Ck}Else{将ai、ai+1、…、am依次赋值给Ck}算法中，最大的比较次数为m+n-1.2024/12/2962合并排序思想设给定集合S={x1,x2,……,xn},且n=2k。当n>2时，把S分成两个不相交的子集合S1={x1,x2,……xn/2}和集合S2={xn/2+1,xn/2+2,……,xn}。直到集合S分解到每个子集合的元素不超过2时为止。比较1次即可将只有两个元素的子集排序.调用前面的MERGEI算法将各个子集合合并。2024/12/2963合并排序算法procedureMERGESORTinteger:n;array:A[1:n]ofinteger;procedureSORT(A,i,j);integer:i,j,m;array:A[i:j]ofinteger;beginifj-i=1thenifA[i]>A[j] 2024/12/2964合并排序算法elsebeginm=(i+j-1)/2; SORT(A,i,m); SORT(A,m+1,j); MERGEI(A[i:m]，A[m+1:j]) end;end;begin read(n,A); SORT(A,1,n); write(A);end2024/12/2965用二叉树来表示排序a>=bb>=ca>=ca>=cb>=ca,b,ca,c,bc,a,bb,c,ac,b,ab,a,cYNYNYNYNYN2024/12/2966用二叉树来表示排序左图为一棵平衡二叉树，平均比较次数(时间复杂度)为(2×2+3×4)÷6=2.67。原始数据的状态会影响排序的效率。2024/12/2967用二叉树来表示排序N个数排序，有n！种结果，对应的二叉树有n！片树叶。如果算法对应一棵平衡二叉树一定存在一个k使K对应平衡二叉树中深度小的结点，而k+1则对应二叉树中深度大的结点。若，任何需要比较进行的排序算法，已经是最好的算法数量级。2024/12/2968快速排序将集合S={a1,a2,……,an}分成小于a，等于a，大于a的三个子集合S1，S2，S3。分别将S1与S3排序，最后将S1，S2和S3连接起来。 优点：（1）划分以后就减少了待排序元素的数量。 （2）子集合排序后采用连接而不用比较就可以归并。 缺点：a难以确定恰当地确定，因此平衡的思想就难以体现。

2024/12/2969快速排序算法先要解决如何在同一数组中划分子集合：a1，a2，a3，……，an-1，anwhilei<jdobeginwhileai<adoi=i+1;whileaj<adoj=j-1;

交换ai和ajend;2024/12/2970快速排序算法procedureQUICKSORT(S); if||S||<=2then begin

将S中的元素直接排序；

return(S) end else begin

从集合S中随机选取一个元素a； 把S中的元素分成小于a，等于a和大于a三个子集合S1,S2,S3; return(QUICKSORT(S1)接着S2接着QUICKSORT(S3)) end2024/12/2971课后作业考虑分治—合并排序算法，重新设计MERGEI(A,B)，考虑ｎ不一定等于实现快速排序算法。第四章排序2024/12/2973目录4.1排序的定义4.2基数排序4.3比较排序的时间下界4.4堆选排序4.5插入法2024/12/29

2024/12/29744.1排序的定义半序的定义

定义如果集合S上的一个关系R，对于S中的任何元素a，b，c，若

1.aRa为真（自反性）；

2.由aRb和bRc可得aRc（传递性）；

3.由aRb和bRa可得a=b

（反对称性）；则称R为集合S上的一个半序(partiaorder)。2024/12/29

2024/12/29754.1排序的定义排序的定义

给定一个从有线性序R的集合中抽出来的n个元素a1，a2，…，an。所谓将这n个元素排序就是要找出1，2，…，n的一个特定排列

∏(1)，∏(2)

，…，∏(n)，使得对于任何i，

1≤i＜n，有a∏(i)Ra∏(i+1)。当关系R是“≤”时，既有

a∏(i)≤

a∏(i+1)≤…≤a∏(n)。2024/12/29

2024/12/29764.2基数排序待排序元素a1，a2，…，an，将其置于一个桶（队列）Q中。ak均为k元组，每一元由m个不同的符号而组成,另设m个不同的桶分别对应m个符号。将Q中元素按元分装到m个桶中，再将m个桶中的元素归并到Q中，如此进行k次，即可使Q中的元素有序。2024/12/29

2024/12/29774.2基数排序例用桶排序法将以下6个数排序：

379，258，731，432，913，455

0号桶1号桶2号桶3号桶4号桶5号桶6号桶7号桶8号桶9号桶按各位数置桶731432913455258379第一次合并后队列731432913455258379按十位数置桶913731432455258379第二次合并后队列913731432455258379按百位数置桶258379432455731913结果2583794324557319132024/12/29

2024/12/29784.2基数排序算法4.1桶排序法

输入一个序列A1，A2，…，An；这里每个元素Ai是一个K元组（ai1ai2…aik），其中，对一切i,，j；1≤i≤n，

1≤j≤k，有0≤aij≤m-1。输出序列A∏(1)≤

A∏(2)≤

…

≤A∏(n)，它是A1，A2，…，An的一个排列。方法使用队列QUEUE存放“当前的元素序列”，还有m个桶Q[0]，Q[1]，…，Q[m-1]，它们都是一个先进先出的对列。用Q[i]来存放当前的分量是正数i的那些元素。（参见过程BUCKETSORT）。2024/12/29

2024/12/29794.2基数排序基数排序算法（算法4.1）

procedureBUCKETSORTbegin

置A1，A2，…，An到队列QUEUE中；

fori←jstep-1until1dobeginforI←0tom-1do置Q[I]为空；

whileQUEUE非空do把QUEUE中的第一个元素Ai置入桶Q[aij]中；

forl←0tom-1do依次置Q[l]中的元素到QUEUE中

endend定理4.1

算法BUCKETSORT将n个元素排序所需的时间是O(k(m+n))，其中k是每个元素的长度，每个分量是介于0到m-1之间的整数。2024/12/29

2024/12/2980问题能否用基数排序法对不超过k元的多元组进行排序?若回答肯定,对元组分别为多数字和字符串时如何处理?2024/12/29814.3比较排序的时间下界引理4.1

一棵高为h的二叉树，最多有2h个叶。定理4.3

将n个不同元素排序的任一判定树的高不小于「log2n!」。2024/12/29

2024/12/29824.4堆选排序堆选排序堆是一棵完全二叉树且

ai>=a2i,ai>=a2i+1

把所有要排序的元素建成一个堆，然后删去根节点上的元素。将最大深度的最右边的叶元素移至根结点，将这棵树再建成一个堆。重复上述过程，直到这棵树只剩一个顶点为止。从这个堆的根节点上删去的元素序列（按删去的先后顺序排列起来）就是一个排序好的非递增序列2024/12/29

2024/12/29834.4堆选排序堆排序的过程是，把初始数据“堆化”后，重复执行如下两个步骤：1.删除根节点的元素；2.将最深最右的叶元素移到根节点并删去这个叶，重新堆化。在实际处理时，只需将根节点元素和待删叶元素互换，就能达到删除根节点元素和把最深最右的叶元素移至根节点上的双重目的，然后对剩下的元素重新堆化。例对50，24，30，20，21，18，3，12，5，6进行堆排序。2024/12/29

2024/12/29844.4堆选排序例对50，24，30，20，21，18，3，12，5，6进行堆排序。下列的图表示删去根元素和重新堆化的过程。50242012530211836(i)624201253021183(ii)删去50，将6移至根部2024/12/29

2024/12/29854.4堆选排序如果用数组记录上述过程，数组元素的变化如下：(i)50，24，30，20，21，18，3，12，5，6(ii)6，24，30，20，21，18，3，12，5，50(iii)30，24，6，20，21，18，3，12，5，50(iv)6，24，18，20，21，6，3，12，5，50302420125621183(iii)将6与它的最大儿子30交换302420125182163(iv)将6与它的最大儿子18交换2024/12/29

2024/12/29864.4堆选排序算法4.3构造一个堆输入数组A[i]，1≤i≤n。输出把A的元素变成一个堆，即使得对于1＜i≤n，

A[i]≤A[「i/2

」]。方法见过程BUILDHEAP。2024/12/29

2024/12/29874.4堆选排序构造一个堆（算法4.3）

procedureBUILDHEAPbeginprocedureHEAPIFY(i,j)beginif2i<jthenifA[2i]≤A[2i+1]且A[i]≤A[2i+1]thenbegin

交换A[i]和A[2i+1]；

HEAPIFY(2i+1,j);endif2i=jthenifA[i]<A[j]then交换A[i]和A[j]endbeginread(A[1]，A[2]，…，A[n]);fori←「n/2」step-1until1doHEAPIFY(i,n)end2024/12/29

2024/12/29884.4堆选排序算法4.4

堆选排序算法。输入数组A[1:n]。输出按非递减序排列的结果。方法见过程HEAPSORT

procedureHEAPSORT:beginBUILDHEAP;fori←nstep-1until2dobegin

交换A[1]和A[i]；

HEAPIFY(1,i-1);endend

2024/12/29

2024/12/29894.4堆选排序定理4.5

算法HEAPSORT对n个元素排序所需的时间是O(nlog2n)。2024/12/29

2024/12/29904.5插入法分段逆序插入法

设A={a1，a2，…，am}是一个非递减序列。B={b1，b2，…，bm+∈}是序列A的伴随序列，即对一切1≤i≤m，有bi≤ai，其中∈的值是0或1。将B中的元素插入到序列A中，使A、B合并为一个大的非递减的序列。因为已知bi≤ai，所以对任何bi，只要能把它插入到a1，a2，…，ai-1的合适位置即可。如果在bi插入前，已有某个bj(j≠i)

已插入到a1，a2，…，ai-1中，bi同样可以插入到ai左部的部分序列中。2024/12/29

2024/12/29914.5插入法bi插入的方法就是所谓的分段逆序插入法。对较小的m，序列B中元素的插入顺序和所需比较的次数见下表。Aa1a2a3a4a5a6a7a8a9a10a11a12a13…a21a22a23…a43a44…Bb1b2b3b4b5b6b7b8b9b10b11b12b13…b21b22b23…b43b44…bi插入顺序13254111098762120…124342…2285…最大的比较次数0223344444455…566…67…Bi插入的顺序和所需的比较次数2024/12/29

2024/12/29924.5插入法bi的插入顺序和所需比较次数是这样得到的。因为b1≤a1，直接把b1置于a1的前面。当m+∈≥3时，先将b3按折半查找插入序列b1a1a2中，需要两次比较。插入的结果，即使b3小于a2，再插入b2时，也不过是将它插入b1a1和b3构成的长度为三的序列中，仍然只要两次比较。至此，a4以前一共有6个元素。如果m+∈≥则先插b5，后查b4，它们最多时插入一个7元序列中，各需三次比较等等。为严格描述分段逆序折半插序，定义了一个递归函数f(n)

（称做分段函数）。它是f(n)=1,当n=1时2n+f(n-1),当n=1时2024/12/29

2024/12/29934.5插入法算法4.5

分段逆序插入法

输入非递减序列A=={a1，a2，…，am}和它的伴随序列B={b1，b2，…，bm+∈}，对一切1≤i≤m，有bi≤ai，其中∈的值是0或1。输出由A和B的全体元素组成的一个非递减序列。方法见过程BYFINSERT

procedureBYFINSERT(‖B‖,A,B)begin

将b1插到a1的前面；找到一个整数k≥2，使得f(k-1)<m+∈≤f(k);

按b3，b2；b5，b4；…；bf(k-2)，bf(k-1)-1，…，bf(k-2)+1；bm+∈，…，bf(k-1)+1的顺序将bi折半插入序列A中。

end2024/12/29

2024/12/29944.5插入法插入排序法

把要排序的n个元素，分成两个一对分别比较，把各对中较大的元素记入子序列S1中，较小的序列记入子序列S2中，即S1和S2中的元素有一对一的大小关系。当n为奇数时，S中的第n个元素记入S2的末尾。然后，将S1中的元素排序（递归的应用插入法）。最后，使用分段逆序插入法把S2中的元素插入已排序的S1中，就得到n个元素的有序序列（当元素个数较少时（n≤4），就直接排序）。2024/12/29

2024/12/29954.5插入法例用排序法将以下11个元素排序，它们是

11，127，43，574，5，560，700，708，9，20，31第一步：11~127，43~574，5~560，700~708，9~20，31，得

S1={127，574，560，708，20}S2={11，43，5，700，9，31}第二步：将S1的元素排序。因为‖S1‖=5>4，做127~574，560~708，得

S1′={574，708}S2′={127，560，20}

对S1′排序。因为‖S1′‖=2<4，用“”比较“直接排序，得排序的S1′为574，7082024/12/29

2024/12/29964.5插入法

由S1′和S2′的关系，有

574<708

↓↓12756020

按分段逆序插入法，用两次比较（20~574，20~127）先将20插入序列

127<574<708

之中，然后将560插入序列

20<127<574<708

之中，也只需两次比较（560~127，560~574），得到S1的排序结果为

20<127<560<574<7082024/12/29

2024/12/29974.5插入法第三步：用逆序插入法将S2插入S1。根据S1和S2的元素对应关系，有

20<127<560<574<708

↓↓↓↓↓91154370031按分段逆序插入法，插入顺序依次是5，11，700，43，31。各插入结果是：

5<9<20<127<560<574<708

↓↓↓1143700312024/12/29

2024/12/29984.5插入法

5<9<11<20<127<560<574<708

↓↓4370031

5<9<11<20<127<560<574<700<708

↓43315<9<11<20<43<127<560<574<700<708315<9<11<20<31<43<127<560<574<700<708累计总的比较次数，最多要26次。2024/12/29

2024/12/29994.5插入法算法4.6

插入排序输入数组A=={a1，a2，…，an}

输出元素a1，a2，…，an的一个非递减序列。

方法见过程INSERT(S1i,i)。在应用时，只要执行语句调用INSERT(S10,0)。这里S10=A。

2024/12/29

2024/12/291004.5插入法procedureINSERT(S1i,i)if‖S1i‖≥4thenbegin

把S1i中的元素分成「‖S1i‖/2」对两两比较；各组中的较大元素依次记入S1i+1中；各组中的较小元素依次记入S2i+1中。当‖S1i‖为奇数时，将S1i中最末的一个元素记入S2i+1的末尾；

INSERT(S1i+1,i+1);return(BYFINSERT(「‖S1i‖/2」,S1i+1,S2i+1)endelsebegin

直接将S1i中的元素排序；

return(S1i)end2024/12/29

2024/12/29101第五章动态规划2024/12/29102引言所谓动态规划（Dynamicprogramming）常常能得到一个比穷举法有效的算法。动态规划的指导思想是，在每种情况下，列出各种可能的局部解，然后按某些条件，从局部解（或中间结果）中挑选出那些有可能产生最佳解的结果而扬弃其余。从而大大缩减了计算量。动态规划遵循所谓“最佳原理”的原则。即“不论前面的状态和策略如何，后面的最优策略只取决于由最初策略所确定的当前状态。”即“最优化从当前状态开始”.2024/12/29103引言动态规划所适用的问题：1）优化问题2）分阶段处理的问题3）状态之间有确定次序的问题。不能跨越2024/12/291045.1单源最短路径问题1.多级图

G={V,E}其中V是顶点的集合,E是边(弧)的集合

Vi也是顶点的集合,Ei是边的集合,如果

V=∪Vi∩iVi为空当(vl,vt)属于Ei且vl属于Vi时,必有Vt属于Vi+1,则G为多级图2024/12/291055.1单源最短路径问题最短路径：是按道路上的代价函数来判定的。如果是两个城市，道路上的代价函数可能是城市间的里程，或者旅差费用等。2024/12/291065.1单源最短路径问题COST（i,j）第i级顶点vj到汇点的最短路径长度C(i,j)边(vi,vj)上的权值COST（i,j）=min{c(j,l)+COST（i+1，l）},其中l属于顶点集Vi+12024/12/291075.1单源最短路径问题2024/12/291085.1单源最短路径问题对于图5.1，计算过程如下：COST（3,6）=min{6+COST（4,9）,5+COST（4,10）}=min{6+4,5+2}=7COST（3,7）=min{4+COST（4,9）,3+COST（4,10）}=min{4+4,3+2}=5COST（3,8）=72024/12/291095.1单源最短路径问题COST（2,2）=min{4+COST（3,6）,2+COST（3,7）,1+COST（3,8）}=min{11,7,8}=7COST（2,3）=9COST（2,4）=11+COST（3,8）=18COST（2,5）=15COST（1,1）=min{9+COST（2,2）,7+COST（2,3）,3+COST（2,4）,2+COST（2,5）}=min{16,16,21,17}=162024/12/291105.1单源最短路径问题因此，从S到T的一条最短路径的代价是16。只要我们每次记下使COST（i,j）达到最小的第j+1级的顶点号，这条路径也就找到了。2024/12/291115.1单源最短路径问题算法：两点间的最短路算法(由后向前)_用cost(j)代替cost(i,j),即不记录顶点所在级,存储多级图时应如何处理?____________________________________PROCEDUREFGRAPHBeginFori←1tondoCOST[i]←0;Forj←n-1to1do//计算COST[j]//2024/12/291125.1单源最短路径问题Begin设L是这样一个顶点，边（j,L）属于E且c(j,L）+COST[L]最小；COST[j]←c(j,L）+COST[L];D[j]←L;End2024/12/291135.1单源最短路径问题//找最小代价的道路//P[1]←1，P[k]←n;Forj←2tok-1doP[j]←D[P[j-1]]End________________________________2024/12/29114第六章贪心法任何问题，通常都有n个输入和一些约束条件。任何满足这些约束条件的子集可称为一个可能解。最佳解是满足目标函数达到最大值或最小值的一个可能解，而目标函数是问题中给定的。贪心法是一个多步决策法，每一步的选择都使得能构成问题的一个可能解（即满足问题的全部约束条件），同时使目标函数的值增加最快或增加最小。贪心法的选择过程是以某些最优化量度为根据，而最优化量度有时可以是目标函数本身，有时也可能是别的量度。最优化量度的选择是贪心法的关键。2024/12/291156.1背包问题背包问题的来源：设某港口有n种不同的货物送往某地，每种货物的总重量是已知的，各种不同货物的运价也是确定的。某支船队承运部分货物，船队的总吨位是确定的。每种货物允许分批发送。考虑这支船队应装运哪些货物才能使它一次获得的运费最多？2024/12/291166.1背包问题背包问题的一般描述：给定n种不同的物品和一个背包。物品i的重量是Wi，背包容量为M。假定物品i的一部分xi(0≤xi≤1)，被放进背包里，就会得到利润

Pixi。因为背包的容量为M，要求被装进的物品的总重量不超过M（若只考虑物重而不考虑其形状和体积）。问应怎样选择物品的种类和数量，使背包装满，而获得最大的利润。2024/12/291176.1背包问题背包类问题还可形式化描述为：给定M>0，Wi>0，Pi>0，1≤i≤n，使之满足：使：达到最大。满足0≤xi≤1的任何向量（x1,x2,…xn）都是一个可能解。这样的解显然有无穷多个。而最佳解必需是使式（6.2）的值达到最大的一个可能解。（6.1）（6.2）2024/12/291186.1背包问题例：给定n=3，M=40，（W1,W2,W3）=（28,15,24）,(p1,p2,p3)=(35,25,24)。以下是此例的五个可能解：

（x1,x2,x3）∑Wixi∑pixi（1）（1,4/5,0）4055（2）（1/2,1,1/3）3750.5（3）（1/28,1,1）4050.25（4）（5/7,1,5/24）4055（5）（25/28,1,0）4056.252024/12/291196.1背包问题对于这个简单的实例，因为它的可能解有无穷多个，所以用组合的方法求最佳解是行不通的。考虑，如果成立，最佳解将取xi=1。因此，不妨假定成立。这就不可能取一切xi=1。在此前提下，任何最佳解都必须将背包装满。同时，由于pi>0，使利润增加。这样得到的解比原来的解要好。2024/12/291206.1背包问题人们可能会想到的贪心的策略：（1）按pi递减顺序装包（效益增长最快）每次选择利润Pi最大的物品装包，使得目标函数增加最快。当放不下时，才选择一个适当的xi<1，使物品装满，可求出每一种货物装入背包的比例X(x1,x2,x3)x1=1，CU=M-28=40-28=12，

x2=CU/W2=12/15=4/5，CU=0，

x3=0

所以，X=(1,4/5,0)，2024/12/291216.1背包问题（2）按Wi非递减顺序装包（背包容量消耗最慢）

x2=1，CU=M-15=40-15=25，

x3=1，CU=25-24=1x1=1/28

所以，X=(1/28,1,1)。（3）按Pi/Wi（单位重量效益）递减顺序装包每次选择利润与重量比最大的物品先装包。先算出每种货物的单位重量效益：(35/28,25/15,24/24)x2=1，CU=25x1=25/28

2024/12/291226.1背包问题总结：由上面的结果可看出，策略(1)显然不是最佳解，因为这种选择方法虽然每一步都使目标函数得到最大的增量，但由于背包也很快背装满了，加入目标函数的Pi的个数少了，不一定能使目标函数达到最大。策略(2)也不是最佳解，虽然背包的重量上升很慢，却没有兼顾利润的增长速度，不能保证得到最佳解。策略(3)考虑到利润增长和容量消耗二者的综合效果，因此可以得到一个相对的最佳解。

2024/12/29123背包问题的贪心算法：Input:P(1,2…n),W(1,2…n),MOutput:x1,x2…xnVoidGreedy(){ floatP[],W[],X[],M,CU;inti,n;

输入P[1,2…n],W[1,2…n],M;//按p[i]/w[i]从大到小的顺序输入

for(i=1;i<=n;i++){x[i]=0;}CU=M//CU是背包的剩余容量

intI=1；

while(W[I]<=CU){//背包未满

x[I]=1;CU=CU-W[I];I=I+1;}x[I]=CU/W[I];}2024/12/291246.2多处理机调度设有n台相同的处理机P1,P2,…,Pn，处理m个独立的作业J1,J2,…,Jm，以互不相关的工作方式工作。规定：任何作业可以在任何一台处理机上运行，但未完工前不允许中断作业；作业也不能折分成更小的子作业。多处理机调度：已知作业Ji需要的处理机时间为ti，i=1,2,…,m。我们的任务是给出一种作业调度方案，使m个作业在尽可能短的时间内，由n台处理机完成。2024/12/291256.2多处理机调度例：设有三台处理机和九个作业，这些作业需要的运行时间分别是81，40，26，4，65，98，53，71，15。按上述调度法则，各处理机分配的作业表将如下图所示。总完工时间是166。

P1P2P3J181J753J44J240J698J871J326J565J915（a）一种简单的多处理机调度方案2024/12/291266.2多处理机调度P1P2P3J698J240J44J181J753J326J271J565J915（a）先长后短调度方案（a）是按作业花费时间的长短进行调度的，把需时较长的作业优先安排，先将作业按运行时间的长短从大到小排成非递增序，然后给空闲的处理机依次分配作业。总完工时间是160。2024/12/291276.2多处理机调度P1P2P3J698J753J181J240J326J44J871J565J915（b）最佳调度方案（b）是本例的一个最佳调度方案。它们的完工时间是151。由此可见贪心算法得到的不一定是最佳方案。2024/12/29128第七章回溯法问题描述算法思想状态空间树皇后问题算法复杂度分析2024/12/291297.1问题分析求一个n元向量（x1,x2,……,xn）,使之满足对问题的某个判定函数B（x1,x2,……,xn

）规定的条件。若Xi∈i,||Si||=Mi,则所有可能的选择有mi种,对Xi的取值有明确要求，称为显约束。判断函数规定的约束成为隐约束。2024/12/291307.2算法思想

从部分分量（x1,x2,…,xi）出发（i=1，2，…，n-1),选择xi+1,如果（x1,x2,…,xi+1）满足判定函数规定的条件，且i+1=n，则得到一个解；若（x1,x2,…,xi+1）满足判定函数，但i+1<n,继续选择xi+2，若（x1,x2,…,xi）不满足判定函数，则另选xi+1，如果可供选择的xi+1均不满足判定条件，则重新选择xi（回溯）.2024/12/291317.2算法思想注意：判定函数的设计应使其部分向量可计算！2024/12/291327.3状态空间树为了我们叙述的方便，我们在这里先介绍一些相关的概念，回溯法是采用体统地搜索给定问题的解空间的方法来确定问题的解。使用一种所谓解空间的树形结构将使这种搜索容易实现。对于一个解空间，可能有很多树形结构与之相对应。相关的例子请参照课本。我们现在来定义解空间树形结构的一些术语。2024/12/291337.3状态空间树树上的每一个节点定义了一个“问题状态”；从根到每个节点的所有路径定义了这一问题的“状态空间“；“问题状态”集的子集S组成了问题的“解状态集”；可以生孩子的节点成为“活节点”，存储活节点的表成为活节点表；2024/12/291347.3状态空间树正在生孩子的节点称为扩展节点；不能生孩子的节点称为死节点。2024/12/291357.4皇后问题介绍完相关的概念后，我们将介绍一个关于回溯法的例子，当然，这个例子具有广泛的代表性，这就是皇后问题。2024/12/291367.4皇后问题问题：

n个皇后，置于n*n的方格内，如果任何两个皇后处于同一行，同一列，或处于与边线成45°角的斜线上，都会遭到对方攻击，求一种互不遭到攻击的状态。2024/12/291377.4皇后问题我们规定第i个皇后位于第i行，n个皇后所在的列构成一个n元向量（x1,x2,…,xi），xi∈{1，2，…，n}.2024/12/291387.4皇后问题皇后甲（i,j）皇后乙（k,l）

|(i-k)/(j-l)|≠1B=(i-k)/(j-l)2024/12/291397.4皇后问题下面我们已四皇后问题为例：首先：i=1（放置第1个皇后）（12024/12/291407.4皇后问题i=2

（1，2×（因（1-2）/（1-2）=1）故（1，32024/12/291417.4皇后问题i=3（1，3，2×（1，3，4×

我们发现第三个皇后已经没有合适的位置，此时需要重新放置第（i-1）个（