数据结构与算法分析教学ppt课件第十章算法设计与分析导论.ppt

《数据结构与算法分析教学ppt课件第十章算法设计与分析导论.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析教学ppt课件第十章算法设计与分析导论.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C/C+&Java北京工业大学北京工业大学 计算机学院计算机学院软件学科部软件学科部 陈文博陈文博 2004数据结构与算法1第十章第十章第十章第十章算法设计与分析导论算法设计与分析导论算法设计与分析导论算法设计与分析导论数据结构与算法2 主要内容主要内容 算法设计与分析内容介绍算法设计与分析内容介绍 算法分析的方法算法分析的方法 递归与分治算法递归与分治算法 回溯算法回溯算法 贪心算法贪心算法 数据结构与算法3算法设计与分析内容介绍算法设计与分析内容介绍 从引例看算法设计从引例看算法设计 表达算法的抽象机制表达算法的抽象机制 数学算法与数据结构算法数学算法与数据结构算法 算法与数据结构的关系算

2、法与数据结构的关系 算法分析的方法算法分析的方法 常用算法模式常用算法模式数据结构与算法4010203040506071234四染色地理结论的实现四染色地理结论的实现123456712345670111111100011010011001010100111101111001011000110从引例看算法设计从引例看算法设计11数据结构与算法5Backtracking Algorithm Idea数据结构与算法6public boolean backtrack()Stack S=new ArrayStack();/Initialize system;i=1;/the i is number of

3、 a task j=1;/the j is item number of choice do (!whole project has completed)/accomplish backtrack数据结构与算法7do while(!The choice exceeds the scope)&(!whole project has completed)if(!matchConstraint(i,j)j+;else break;if(!The choice exceeds the scope)S.push(i,j);i+;j=1;/new task in beginning else if(!S.

4、empty()(i,j)=S.pop();j+;/test new choice else return false;if(whole project has completed)return true;(!whole project has completed)数据结构与算法8 ADT Stack 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R|ai-1,ai D,i=2,.,n 约定约定an 端为端为栈顶栈顶，a1 端为端为栈底栈底。ADT Stack 基本操作：基本操作：Stack()empty()push(e)pop()数据结构与算法9

5、表达算法的抽象机制表达算法的抽象机制数数 据据 模模 型型初始状态初始状态结果状态结果状态算算 法法顶层算法顶层算法底层算法底层算法宏观步骤宏观步骤 算法骨干算法骨干变量抽象变量抽象 运算粗化运算粗化微观步骤微观步骤 算法细节算法细节变量具体变量具体 运算细化运算细化ADT(抽象抽象)运算步骤运算步骤数据结构与算法10数学层面的算法与数据结构层面的算法数学层面的算法与数据结构层面的算法 数据结构层面的算法数据结构层面的算法public Object pop()if(empty()throw new EmptyStackException();Object topElement=stacktop

6、;return topElement;涉及对具体数据结构的操作涉及对具体数据结构的操作数据结构与算法11 数学层面的算法数学层面的算法不涉及对具体数据结构的操作不涉及对具体数据结构的操作只使用数据结构只使用数据结构ADT的接口的接口数据结构与算法12算法与数据结构的关系算法与数据结构的关系算法算法 vsvs 抽象的逻辑的数据结构抽象的逻辑的数据结构 四染色算法四染色算法 vsvs 具体的数据结构具体的数据结构 四染色算法四染色算法 vsvs 逻辑的数据结构逻辑的数据结构 （往往由（往往由控制结构控制结构得到体现）得到体现）whileif else if do 数据结构与算法13算法分析的方法算

7、法分析的方法 渐进时间复杂度渐进时间复杂度 平均时间复杂度平均时间复杂度v 一般的分析方法一般的分析方法v 递归方程的求解递归方程的求解数据结构与算法14四染色算法的分析四染色算法的分析例例 四染色回溯算法四染色回溯算法4*4*44n=4nT(n)=O(4n)数据结构与算法15void hanoi(int n,char x,char y,char z)/将塔座将塔座x x上按直径由小到大且至上而下编号为上按直径由小到大且至上而下编号为1 1至至n n/的的n n个圆盘按规则搬到塔座个圆盘按规则搬到塔座z z上，上，y y可用作辅助塔座。可用作辅助塔座。if(n=1)move(x,1,z);/将

8、编号为的圆盘从将编号为的圆盘从x移到移到z else hanoi(n-1,x,z,y);/将将x上编号为至上编号为至n-1的圆盘移到的圆盘移到y,z作辅助塔作辅助塔 move(x,n,z);/将编号为将编号为n的圆盘从的圆盘从x移到移到z hanoi(n-1,y,x,z);/将将y上编号为至上编号为至n-1的圆盘移到的圆盘移到z,x作辅助塔作辅助塔 Hanoi塔塔算法的分析算法的分析数据结构与算法16T(n)T(n-1)T(n-1)O(1)T(n)=T(n-1)+O(1)+T(n-1)=2 T(n-1)+O(1)递归方程的求解递归方程的求解数据结构与算法17T(n)=2 T(n-1)+O(1)

9、=2(2T(n-2)+O(1)+O(1)=4T(n-2)+3O(1)=4(2T(n-3)+O(1)+3O(1)=8T(n-3)+7O(1)=8(2T(n-4)+O(1)+7O(1)=16T(n-4)+15O(1)T(n)=2kT(n-k)+(2k-1)O(1)数据结构与算法18T(n)=2kT(n-k)+(2k-1)O(1)n-k=1 k=n-1 T(n)=2n-1 T(1)+(2 n-1-1)O(1)=2n-1 O(1)+(2 n-1-1)O(1)=22n-1 O(1)-O(1)=(2n 1)O(1)T(n)=O(2n)数据结构与算法19常用算法模式常用算法模式 递归与分治算法递归与分治算法

10、 动态规划动态规划 贪心算法贪心算法 回溯算法回溯算法 分支限界算法分支限界算法 概率算法概率算法 遗传算法遗传算法数据结构与算法20递归算法递归算法数据结构与算法21 后置递归后置递归法法(Postponing the work)的设计思想为的设计思想为:假假如如某某个个问问题题的的求求解解过过程程可可以以分分成成若若干干步步进进行行，并并且且当当前前这这一一步步的的解解可可以以直直接接求求得得，则则先先求求出出当当前前这这一一步步的的解解，对对于于余余下下的的问问题题，若若问问题题的的性性质质和和原原问问题类似，则又可题类似，则又可递归求解递归求解。数据结构与算法22 递归的递归的终结状态

11、终结状态是，当前的问题可是，当前的问题可以以直接求解直接求解，对原问题而言，则是已走，对原问题而言，则是已走到了求解的到了求解的最后一步最后一步。链表是可以如此求解的一个典型例子。链表是可以如此求解的一个典型例子。例如例如:编写编写“删除单链表中所有值为删除单链表中所有值为x 的数的数据元素据元素”的算法。的算法。数据结构与算法23 1)单链表是一种顺序结构，必须从第一个单链表是一种顺序结构，必须从第一个结点起，逐个检查每个结点的数据元素结点起，逐个检查每个结点的数据元素;分析分析:2)从另一角度看，链表又是一个递归结构，从另一角度看，链表又是一个递归结构，若若 L 是线性链表是线性链表(a1

12、,a2,an)的头指针，的头指针，则则 L-next是线性链表是线性链表(a2,an)的头指针。的头指针。数据结构与算法24 a1 a2 a3 an L例如例如:a1 a2 a3 an L a1 a2 a3 an L已知下列链表已知下列链表1)“a1=x”,则则 L 仍为删除仍为删除 x 后的链表头指针后的链表头指针2)“a1x”,则余下问题是考虑以则余下问题是考虑以 L-next 为头指针的为头指针的链表链表 a1 L-nextL-next=p-nextp=L-next数据结构与算法25void delete_L(LinkList&L,ElemType x)/删除以删除以L L为头指针的带头

13、结点的单链表中为头指针的带头结点的单链表中 /所有值为所有值为x x的数据元素的数据元素 if(L-next)if(L-next-data=x)p=L-next;L-next=p-next;delete(p);delete_L(L,x);else delete_L(L-next,x);/delete数据结构与算法26void delete_L(LinkList&L,ElemType x)/L L为无头结点的单链表的头指针为无头结点的单链表的头指针 if(L)if(L-data=x)p=L;L=L-next;delete(p);delete_L(L,x);else delete_L(L-next

14、,x);4.递归函数中的递归函数中的尾递归尾递归容易消除。容易消除。数据结构与算法27void delete(LinkList&L,ElemType x)/L L为带头结点的单链表的头指针为带头结点的单链表的头指针 p=L-next;pre=L;while(p)if(p-data=x)pre-next=p-next;free(p);p=pre-next;else pre=p;p=p-next;上述递归算法可改写为迭代的形式上述递归算法可改写为迭代的形式数据结构与算法28递归与分治算法递归与分治算法数据结构与算法29 若求解问题的规模为若求解问题的规模为n 其次，逐步其次，逐步合并合并子问题的子

15、问题的解解，直到，直到获得原问题的解。获得原问题的解。首先，把问题首先，把问题分解分解为为k 个个性质相同性质相同、但规模但规模 较小的较小的子问题子问题（1 k n)，并，并求解这些子问题。（如果这些子问题求解这些子问题。（如果这些子问题的规模还不够的规模还不够“小小”，则可以，则可以进一步进一步分分解解，直到可以求解为止），直到可以求解为止）分治法的概念分治法的概念数据结构与算法30PP1P2PkT1(n)T2(n)Tk(n)T(n)时间复杂度：时间复杂度：T(n)=T1(n)+T2(n)+Tk(n)+C(n)C(n)数据结构与算法31void mergeSort(RcdType&SR,i

16、nt s,int t)/将将SRs.t 归并排序归并排序 if(s=t)return;int m=(s+t)/2;mergeSort(SR,s,m);mergeSort(SR,m+1,t);merge(SR,s,m,t);/mergeSort 例例 归并排序归并排序 数据结构与算法32T(n)T(n/2)T(n/2)Cn数据结构与算法33T(n)=T(n/2)+T(n/2)+Cn=2T(n/2)+Cn=2(2T(n/4)+C(n/2)+Cn=4T(n/4)+Cn+Cn=4T(n/4)+2Cn =8T(n/8)+3Cn =2kT(n/2k)+kCn 2k=n k=log2nT(n)=nT(1)+

17、log2nCn=Cnlog2n+d nT(n)=O(nlog2n)数据结构与算法34分治算法的设计模式分治算法的设计模式divide-and-conquer(P)if(|P|)=n0)adhocery(P);divide P into smaller subinstances P1,P2,Pk;for(i=1;i=k;i+)yi=divide-and-conquer(Pi);return merge(y1,yk);数据结构与算法35最接近点对问题最接近点对问题分析分析（直线上直线上n个点，假设只有一对符合条件）个点，假设只有一对符合条件）算出每两个点的距离算出每两个点的距离.若排序若排序,需需

18、O(n2),希望希望O(nlog2n)mS1S2p1p2p3q3q1q2d=min|p1-p2|,|q1-q2|数据结构与算法36public static double nearPair(S)n=|S|;if(n2)return ;m=S中各点坐标的中位数；中各点坐标的中位数；构造构造S1和和S2；/S1=x S|xm d1=nearPair(S1);d2=nearPair(S2);d=min(d1,d2,q-p);return d;T(n)=2T(n/2)+O(n)=O(nlog2n)数据结构与算法37贪心算法贪心算法数据结构与算法38贪心算法贪心算法的概念的概念 在解决某一问题的过程中，

19、贪心算在解决某一问题的过程中，贪心算法总是做出在法总是做出在当前看来当前看来最好的选择最好的选择。也就是说，贪心算法并不从整体最也就是说，贪心算法并不从整体最优考虑，它所做出的选择只是在某种意优考虑，它所做出的选择只是在某种意义上的义上的局部最优选择局部最优选择。（最终结果并不。（最终结果并不总是总是整体最优整体最优）贪心算法合理的称谓：贪心算法合理的称谓：就急算法就急算法数据结构与算法39四种硬币四种硬币 0.25 0.10 0.05 0.01 找顾客找顾客0.61 0.61-0.25=0.360.36-0.25=0.110.11-0.10=0.010.01-0.01=0.00整体最优（整体

20、最优（币数最少币数最少）本例的币值结构具有最优子结构性质本例的币值结构具有最优子结构性质找钱问题找钱问题数据结构与算法40若四种硬币若四种硬币 0.11 0.05 0.01 找顾客找顾客0.15 0.15-0.11=0.040.04-0.01=0.030.03-0.01=0.020.02-0.01=0.01一般可以得到整体一般可以得到整体近似近似最优解最优解0.01-0.01=0.000.15-3*0.05=0.00数据结构与算法41贪心算法的设计模式贪心算法的设计模式Greedy(inputSet,Solution,target)Solution=;target=;while(!findSo

21、lution)x=select(inputSet);if feasible(Solution,x)Solution=Solution x;change(target,x)return Solution;数据结构与算法42最小生成树问题最小生成树问题(ST G=(V,E)public static void prim(int n,floatc)T=;S=1;while(S!=V)(i,j)=min(cij)|i S&j V-S T=T (i,j);S=S j;数据结构与算法43abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和所得生成树权

22、值和=14+8+3+5+16+21=67数据结构与算法44回溯算法回溯算法数据结构与算法45数据结构与算法46 回溯算法术语 1.解向量解向量：问题解的向量表示形式。：问题解的向量表示形式。(x1,x2,xk)k n,n:问题的规模。问题的规模。2.约束条件约束条件 1）显式约束：对分量）显式约束：对分量xi的取值限定。的取值限定。2）隐式约束：为满足问题的解，）隐式约束：为满足问题的解，不同分不同分 量之间应遵守量之间应遵守的约束。的约束。3.解空间：对于问题的一个实例，解向量满足解空间：对于问题的一个实例，解向量满足 显式约束条件的所有多元组，构成了该显式约束条件的所有多元组，构成了该 实

23、例的一个实例的一个解空间解空间。数据结构与算法47v 状态空间树状态空间树 用于描述解空间的逻辑结构树用于描述解空间的逻辑结构树 v 目标函数与最优解目标函数与最优解 1.目标函数：衡量问题解目标函数：衡量问题解“优劣优劣”的标准的标准 2.最优解：使目标函数取极值的解最优解：使目标函数取极值的解 数据结构与算法48回溯算法的基本思想回溯算法的基本思想 回溯算法回溯算法有有“通用解题法通用解题法”之称，系统之称，系统搜索问题的所有解，从中筛出符合条件的解搜索问题的所有解，从中筛出符合条件的解 它在问题的解空间树中，按它在问题的解空间树中，按深度优先深度优先的的策略进行搜索。搜索至某一结点时，判

24、断其策略进行搜索。搜索至某一结点时，判断其是否包含问题的解。不包含，跳过对其子树是否包含问题的解。不包含，跳过对其子树的搜索，向其祖先的搜索，向其祖先回溯回溯；否则进入该子树，；否则进入该子树，继续按继续按深度优先深度优先的策略搜索的策略搜索 回溯算法可以求回溯算法可以求单一解单一解、所有解所有解，也可，也可以在所有解中求出以在所有解中求出最优解最优解数据结构与算法49 最佳分配问题最佳分配问题 假设有假设有n个人和个人和n项课题项课题.其中第其中第 i个人干第个人干第j项课题的经费消耗为项课题的经费消耗为COST(i,j).解决分配解决分配,使每使每个课题只有一个人来承担个课题只有一个人来承

25、担,一人一项一人一项,且完成这且完成这n项课题的总经费消耗最低项课题的总经费消耗最低.测试数据测试数据:123131625433493人人员员课课 题题COSTCOST(1,2)COST(2,3)COST(3,1)8数据结构与算法50数据结构与算法51void backtrack(int i,int n)/假设已求得满足约束条件的部分解假设已求得满足约束条件的部分解(x1,.,xi-1)，本函，本函 /数从数从 xi 起继续搜索，直到求得整个解起继续搜索，直到求得整个解(x1,x2,xn)。if(in)output(x);else while(!Empty(Si)从从 Si 中取中取 xi 的一个值的一个值 vi Si;if (x1,x2,xi)满足约束条件满足约束条件 backtrack(i+1,n);/继续求下一个部分解继续求下一个部分解 从从 Si 中删除值中删除值 vi;/backtrack数据结构与算法52数据结构与算法在整个软件工程中的全景地位数据结构与算法在整个软件工程中的全景地位D S+AlgorithmsC+/C#Java数据结构与算法53