算法分析TheAnalysisofAlgorithms

算法分析与设计AnalysisandDesignofComputerAlgorithms第五章减治法DecreaseandConquer杨春明西南科学技大学计算机学院©SchoolofComputerScienceandTechnology,SWUST2教学内容减治法的一般方法及变种插入排序深度优先查找和广度优先查找生成组合对象的算法减常因子算法减可变规模算法要求掌握减治法的基本思想及在常见问题问题中的应用。©SchoolofComputerScienceandTechnology,SWUST3减治法减治技术利用了一种关系：一个问题给定实例的解和同样的问题较小实例的解之间的关系。一旦建立了这种关系，就可以从顶至下（递归），也可以从底至上（非递归）的来运用。减治法有三种变种：1)减去一个常量2)减去一个常数因子3)减去的规模是可变的©SchoolofComputerScienceandTechnology,SWUST4减（一）治技术规模为n的问题规模为n-1的子问题子问题的解原始问题的解f(n)=anf(n)=f(n-1)*an1f(n)=an=1©SchoolofComputerScienceandTechnology,SWUST5减（半）治技术规模为n的问题规模为n/2的子问题子问题的解原始问题的解an=(an/2)2n是偶数an=(a(n-1)/2)2*an是奇数an=an=1©SchoolofComputerScienceandTechnology,SWUST6插入排序Forj2tondo将A(j)放到已分类集合A(0..j-1)的正确位置上Repeat算法InsertionSort(A[0..n-1])//用插入排序对给定数组排序//输入：一个可排序数组//输出：非降序列数组Afori1ton-1do{vA[i];ji-1;while(j≥0andA[j]v){A[j+1}A[j];jj-1;}A[j+1]v;}89|4568902934174589|6890293417456889|9029341745688990|2934172945688990|3417293445688990|1717293445688990©SchoolofComputerScienceandTechnology,SWUST7深度优先查找邻接矩阵表示，该遍历算法的时间效率属于Θ(|V|2)邻接链表表示，该遍历算法的时间效率属于Θ(|V|+|E|)©SchoolofComputerScienceandTechnology,SWUST8©SchoolofComputerScienceandTechnology,SWUST9广度优先查找邻接矩阵表示，该遍历算法的时间效率属于Θ(|V|2)邻接链表表示，该遍历算法的时间效率属于Θ(|V|+|E|)©SchoolofComputerScienceandTechnology,SWUST10©SchoolofComputerScienceandTechnology,SWUST11广度优先查找©SchoolofComputerScienceandTechnology,SWUST12DFS与BFS的主要性质©SchoolofComputerScienceandTechnology,SWUST13拓扑排序(Topologicalsorting)有向图©SchoolofComputerScienceandTechnology,SWUST14拓扑排序(Topologicalsorting)©SchoolofComputerScienceandTechnology,SWUST15拓扑排序(Topologicalsorting)©SchoolofComputerScienceandTechnology,SWUST16生成排列(Permutations)生成由n个元素{a1,a2,...,an}的排列算法JohnsonTrotter(n)//生成n个数的排列//输入：一个正整数n//输出：{1,...,n}的所有的排列数将第一个排列初始化为12...nwhile存在一个移动整数kdo求最大的移动整数k把k和它箭头指向的相邻整数互换调转所有大于k的整数的方向课后思考：如何按照字典序生成a1a2...an后面的排列呢？©SchoolofComputerScienceandTechnology,SWUST17生成子集（Subset）•背包问题中如何穷举出给定物品集合的所有子集？A={a1,a2,...,an}={a1,a2,...,an-1}∪{an}©SchoolofComputerScienceandTechnology,SWUST18假币问题(Fake-Coin)当n1时，W(n)=W([n/2])+1,W(1)=0©SchoolofComputerScienceandTechnology,SWUST19俄式乘法(Multiplicationálarusse)两个大整数m和n乘法n*m=n—2*2*mn为偶数n*m=n-1——2*2*m+mn为奇数©SchoolofComputerScienceandTechnology,SWUST20约瑟夫斯问题(Josephus)在约瑟夫斯环中最后的幸存者是谁？偶数情况：J(2k)=2J(k)-1奇数情况：J(2k+1)=2J(k)+1二进制表示：J(6)=J(1102)=1012=5，J(7)=J(1112)=1112=7©SchoolofComputerScienceandTechnology,SWUST21约瑟夫斯问题(Josephus)？J(n,m)=(J(n-1,m)+m)modnJ(1,m)=0©SchoolofComputerScienceandTechnology,SWUST22选择问题(SelectionProblem)问题描述给定一个含有n个元素的(或叫关键字)的集合，确定集合中第k小的元素。A(0)A(1)…A(j-1)A(j)A(j+1)…A(n-2)A(n-1)V划分元素kj时，第k小元素所在的集合Kj时，第k小元素所在的集合K=j时，第k小元素就是划分元素©SchoolofComputerScienceandTechnology,SWUST23选择问题(SelectionProblem)ProcedureSELECT(A,n,k)integern,k,m,r,j;m1;rn+1;A(n+1)+∞;loopjrcallPARTITION(m,j)case:k=j:return:kj:rj:else:mj+1endcaserepeatEndSELECT调用划分函数两个新的子问题T(n)=T(n/2)+(n+1)©SchoolofComputerScienceandTechnology,SWUST24插值查找(Interpolationsearch)•有序数组查找的另一种方法由直线方程可得：键值比较次数小于log2log2n+1©SchoolofComputerScienceandTechnology,SWUST25二叉树的查找与插入最差效率Θ(n)，平均效率Θ(logn)©SchoolofComputerScienceandTechnology,SWUST26拈游戏(NimGame)有13根火柴棍，每次最少拿走1根，最多能拿走4根，拿走最后一根火柴的就是赢家。该如何拿走火柴？n=m+1实例是败局m+2≤n≤2m+1是胜局2m+2=2(m+1)另一个败局获胜策略每次拿走nmod(m+1)根火柴棍©SchoolofComputerScienceandTechnology,SWUST27拈游戏(NimGame)多堆拈游戏每堆火柴棍的数量不一致，每次拿走火柴棍时可以从任意一堆中拿走任意允许数量的火柴棍，甚至可以把一堆都拿光。拿走最后一根火柴的是赢家。1901年，哈佛大学数学教授C.L.Bouton发现了一个精巧解法：解是基于堆中数量的二进制表示的。b1,b2,...,bi分别是各堆数量的二进制表示；计算它们的二进制数位和（忽略进位）。当且仅当二进制数位和中包含至少一个1时，为胜局；只包含0时，为败局。©SchoolofComputerScienceandTechnology,SWUST28减治法小结减治技术利用了一种关系：一个问题给定实例的解和同样的问题较小实例的解之间的关系。一旦建立了这种关系，就可以从顶至下（递归），也可以从底至上（非递归）的来运用。减治法有三种变种：1)减去一个常量2)减去一个常数因子3)减去的规模是可变的用减治法解决的问题有：插入排序，DFS，BFS，俄式乘法，选择问题©SchoolofComputerScienceandTechnology,SWUST29referenceJosephusproblem=technologyNimGame=140