算法分析TheAnalysisofAlgorithms

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法分析与设计,Analysis and Design of Computer Algorithms,第五章 减治法,Decrease and Conquer,1,教学内容,减治法的一般方法及变种,插入排序,深度优先查找和广度优先查找,生成组合对象的算法,减常因子算法,减可变规模算法,要求,掌握减治法的基本思想及在常见问题问题中的应用。,2,减治法,减治技术利用了一种关系：一个问题给定实例的解和同样的问题较小实例的解之间的关系。,一旦建立了这种关系，就可以从顶至下（递归），也可以从底至上（非递归）的来运用。,减治法有三种变种：,1),减去一个常量,2),减去一个常数因子,3),减去的规模是可变的,3,减（一）治技术,规模为,n,的问题,规模为,n-1,的子问题,子问题的解,原始问题的解,f(n)=a,n,f(n)=f(n-1)*a n1,f(n)=a n=1,4,减（半）治技术,规模为,n,的问题,规模为,n/2,的子问题,子问题的解,原始问题的解,a,n,=(a,n/2,),2,n,是偶数,a,n,=(a,(n-1)/2,),2,*a n,是奇数,a,n,=a n=1,5,插入排序,For j,2 to n do,将,A(j),放到已分类集合,A(0.j-1),的正确位置上,Repeat,算法,InsertionSort(A0.n-1),/,用插入排序对给定数组排序,/,输入：一个可排序数组,/,输出：非降序列数组,A,for i,1 to n-1 do,vAi;,ji-1;,while (j0 and Ajv),Aj+1Aj;,jj-1;,Aj+1v;,89 |,45,68 90 29 34 17,45 89 |,68,90 29 34 17,45 68 89 |,90,29 34 17,45 68 89 90 |,29,34 17,29 45 68 89 90 |,34,17,29 34 45 68 89 90 |,17,17 29 34 45 68 89 90,6,深度优先查找,邻接矩阵表示，该遍历算法的时间效率属于,(|V|,2,),邻接链表表示，该遍历算法的时间效率属于,(|V|+|E|),7,8,广度优先查找,邻接矩阵表示，该遍历算法的时间效率属于,(|V|,2,),邻接链表表示，该遍历算法的时间效率属于,(|V|+|E|),9,10,广度优先查找,11,DFS,与,BFS,的主要性质,12,拓扑排序,(Topological sorting),有向图,13,拓扑排序,(Topological sorting),14,拓扑排序,(Topological sorting),15,生成排列,(Permutations),生成由,n,个元素,a,1,a,2,.,a,n,的排列,算法,JohnsonTrotter(n),/,生成,n,个数的排列,/,输入：一个正整数,n,/,输出：,1,.,n,的所有的排列数,将第一个排列初始化为,12.n,while,存在一个移动整数,k do,求最大的移动整数,k,把,k,和它箭头指向的相邻整数互换,调转所有大于,k,的整数的方向,课后思考：如何按照,字典序,生成,a,1,a,2,.a,n,后面的排列呢？,16,生成子集（,Subset,）,背包问题中如何穷举出给定物品集合的所有子集？,A=a,1,a,2,.,a,n,=a,1,a,2,.,a,n-1,a,n,17,假币问题,(Fake-Coin),当,n1,时，,W(n)=W(n/2)+1 , W(1)=0,18,俄式乘法,(Multiplication la russe),两个大整数,m,和,n,乘法,n * m=,n,2,* 2 * m,n,为偶数,n * m=,n -1,2,* 2 * m + m,n,为奇数,19,约瑟夫斯问题,(Josephus),在约瑟夫斯环中最后的幸存者是谁？,偶数情况：,J(2k)=2J(k)-1,奇数情况：,J(2k+1)=2J(k)+1,二进制表示：,J(6)=J(110,2,)=101,2,=5,，,J(7)=J(111,2,)=111,2,=7,20,约瑟夫斯问题,(Josephus),？,J(n,m)=(J(n-1,m)+m) mod nJ(1,m)=0,21,选择问题,(Selection Problem),问题描述,给定一个含有,n,个元素的,(,或叫关键字,),的集合，确定集合中第,k,小的元素。,A(0),A(1),A(j-1),A(j),A(j+1),A(n-2),A(n-1),V,划分元素,kj,时，第,k,小元素所在的集合,K=j,时，第,k,小元素就是划分元素,22,选择问题,(Selection Problem),Procedure SELECT(A,n,k),integer n,k,m,r,j;,m,1;rn+1;A(n+1)+;,loop,j,r,call PARTITION(m,j),case,:k=j:return,:kj:rj,:else:mj+1,endcase,repeat,End SELECT,调用划分函数,两个新的子问题,T(n)=T(n/2)+(n+1),23,插值查找,(Interpolation search),有序数组查找的另一种方法,由直线方程可得：,键值比较次数小于,log,2,log,2,n+1,24,二叉树的查找与插入,最差效率,(n),，平均效率,(logn),25,拈游戏,(Nim Game),有,13,根火柴棍，每次最少拿走,1,根，,最多能拿走,4,根，拿走最后一根火,柴的就是赢家。该如何拿走火柴？,n=m+1,实例是败局,m+2,n,2m+1,是胜局,2m+2=2(m+1),另一个败局,获胜策略每次拿走,n mod (m+1),根火柴棍,26,拈游戏,(Nim Game),多堆拈游戏,每堆火柴棍的数量不一致，每次拿走火柴棍时可以从任意一堆中拿走任意允许数量的火柴棍，甚至可以把一堆都拿光。拿走最后一根火柴的是赢家。,1901,年，哈佛大学数学教授,C.L. Bouton,发现了一个精巧解法：,解是基于堆中数量的二进制表示的。,b1,b2,.,bi,分别是各堆数量的二进制表示；计算它们的,二进制数位和,（忽略进位）。,当且仅当二进制数位和中包含至少一个,1,时，为胜局；只包含,0,时，为败局。,27,减治法小结,减治技术利用了一种关系：一个问题给定实例的解和同样的问题较小实例的解之间的关系。一旦建立了这种关系，就可以从顶至下（递归），也可以从底至上（非递归）的来运用。,减治法有三种变种：,1),减去一个常量,2),减去一个常数因子,3),减去的规模是可变的,用减治法解决的问题有：插入排序，,DFS,，,BFS,，俄式乘法，选择问题,28,reference,Josephus problem,Nim Game,29,