《算法分析TheAnalysisofAlgorithms精编版》由会员分享，可在线阅读，更多相关《算法分析TheAnalysisofAlgorithms精编版（30页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计 Analysis and Design of Computer Algorithms第五章 减治法Decrease and Conquer, School of Computer Science and Technology, SWUST,2,教学内容,减治法的一般方法及变种 插入排序 深度优先查找和广度优先查找 生成组合对象的算法 减常因子算法 减可变规模算法 要求 掌握减治法的基本思想及在常见问题问题中的应用。, School of Computer Science and Technology, SWUST,3,减治法,减治技术利用了一种关系：一个问题给定实例的解和同样的
2、问题较小实例的解之间的关系。 一旦建立了这种关系，就可以从顶至下（递归），也可以从底至上（非递归）的来运用。 减治法有三种变种： 1)减去一个常量 2)减去一个常数因子 3)减去的规模是可变的, School of Computer Science and Technology, SWUST,4,减（一）治技术,规模为n 的问题,规模为n-1 的子问题,子问题的解,原始问题的解,f(n)=an f(n)=f(n-1)*a n1 f(n)=a n=1, School of Computer Science and Technology, SWUST,5,减（半）治技术,规模为n 的问题,规模为n
3、/2 的子问题,子问题的解,原始问题的解,an=(an/2)2 n是偶数 an=(a(n-1)/2)2 *a n是奇数 an =a n=1, School of Computer Science and Technology, SWUST,6,插入排序,For j2 to n do 将A(j)放到已分类集合A(0.j-1)的正确位置上 Repeat,算法 InsertionSort(A0.n-1) /用插入排序对给定数组排序 /输入：一个可排序数组 /输出：非降序列数组A for i1 to n-1 do vAi; ji-1; while (j0 and Ajv) Aj+1Aj; jj-1;
4、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, School of Computer Science and Technology, SWUST,7,深度优先查找,邻接矩阵表示，该遍历算法的时间效率属于(|V|2) 邻接链表表示，该遍历算法的时间效率属于(|V|+|E|), School of Computer
5、 Science and Technology, SWUST,8, School of Computer Science and Technology, SWUST,9,广度优先查找,邻接矩阵表示，该遍历算法的时间效率属于(|V|2) 邻接链表表示，该遍历算法的时间效率属于(|V|+|E|), School of Computer Science and Technology, SWUST,10, School of Computer Science and Technology, SWUST,11,广度优先查找, School of Computer Science and Technolo
6、gy, SWUST,12,DFS与BFS的主要性质, School of Computer Science and Technology, SWUST,13,拓扑排序(Topological sorting),有向图, School of Computer Science and Technology, SWUST,14,拓扑排序(Topological sorting), School of Computer Science and Technology, SWUST,15,拓扑排序(Topological sorting), School of Computer Science and T
7、echnology, SWUST,16,生成排列(Permutations),生成由n个元素 a1,a2,.,an的排列,算法 JohnsonTrotter(n) /生成n个数的排列 /输入：一个正整数n /输出：1,.,n的所有的排列数 将第一个排列初始化为12.n while 存在一个移动整数k do 求最大的移动整数k 把k和它箭头指向的相邻整数互换 调转所有大于k的整数的方向,课后思考：如何按照字典序生成a1a2.an后面的排列呢？, School of Computer Science and Technology, SWUST,17,生成子集（Subset）,背包问题中如何穷举出给
8、定物品集合的所有子集？,A=a1,a2,.,an=a1,a2,.,an-1 an, School of Computer Science and Technology, SWUST,18,假币问题(Fake-Coin),当n1时，W(n)=W(n/2)+1 , W(1)=0, School of Computer Science and Technology, SWUST,19,俄式乘法(Multiplication la russe),两个大整数m和n乘法, School of Computer Science and Technology, SWUST,20,约瑟夫斯问题(Josephus
9、),在约瑟夫斯环中最后的幸存者是谁？,偶数情况：J(2k)=2J(k)-1 奇数情况：J(2k+1)=2J(k)+1,二进制表示：J(6)=J(1102)=1012=5，J(7)=J(1112)=1112=7, School of Computer Science and Technology, SWUST,21,约瑟夫斯问题(Josephus),？,J(n,m)=(J(n-1,m)+m) mod nJ(1,m)=0, School of Computer Science and Technology, SWUST,22,选择问题(Selection Problem),问题描述 给定一个含有n
10、个元素的(或叫关键字)的集合，确定集合中第k小的元素。,V,划分元素,kj时，第k小元素所在的集合,Kj时，第k小元素所在的集合,K=j时，第k小元素就是划分元素, School of Computer Science and Technology, SWUST,23,选择问题(Selection Problem),Procedure SELECT(A,n,k) integer n,k,m,r,j; m1;rn+1;A(n+1)+; loop jr call PARTITION(m,j) case :k=j:return :kj:rj :else:mj+1 endcase repeat End
11、 SELECT,调用划分函数,两个新的子问题,T(n)=T(n/2)+(n+1), School of Computer Science and Technology, SWUST,24,插值查找(Interpolation search),有序数组查找的另一种方法,由直线方程可得：,键值比较次数小于 log2log2n+1, School of Computer Science and Technology, SWUST,25,二叉树的查找与插入,最差效率(n)，平均效率(logn), School of Computer Science and Technology, SWUST,26,拈
12、游戏(Nim Game),有13根火柴棍，每次最少拿走1根， 最多能拿走4根，拿走最后一根火 柴的就是赢家。该如何拿走火柴？,n=m+1实例是败局 m+2n 2m+1是胜局 2m+2=2(m+1)另一个败局,获胜策略每次拿走n mod (m+1)根火柴棍, School of Computer Science and Technology, SWUST,27,拈游戏(Nim Game),多堆拈游戏 每堆火柴棍的数量不一致，每次拿走火柴棍时可以从任意一堆中拿走任意允许数量的火柴棍，甚至可以把一堆都拿光。拿走最后一根火柴的是赢家。 1901年，哈佛大学数学教授C.L. Bouton发现了一个精巧解
13、法： 解是基于堆中数量的二进制表示的。 b1,b2,.,bi分别是各堆数量的二进制表示；计算它们的二进制数位和（忽略进位）。 当且仅当二进制数位和中包含至少一个1时，为胜局；只包含0时，为败局。, School of Computer Science and Technology, SWUST,28,减治法小结,减治技术利用了一种关系：一个问题给定实例的解和同样的问题较小实例的解之间的关系。一旦建立了这种关系，就可以从顶至下（递归），也可以从底至上（非递归）的来运用。 减治法有三种变种： 1)减去一个常量 2)减去一个常数因子 3)减去的规模是可变的 用减治法解决的问题有：插入排序，DFS，B
14、FS，俄式乘法，选择问题, School of Computer Science and Technology, SWUST,29,reference,Josephus problem Nim Game,1、有时候读书是一种巧妙地避开思考的方法。20.9.220.9.2Wednesday, September 2, 2020 2、阅读一切好书如同和过去最杰出的人谈话。07:50:3707:50:3707:509/2/2020 7:50:37 AM 3、越是没有本领的就越加自命不凡。20.9.207:50:3707:50Sep-202-Sep-20 4、越是无能的人，越喜欢挑剔别人的错儿。07:
15、50:3707:50:3707:50Wednesday, September 2, 2020 5、知人者智，自知者明。胜人者有力，自胜者强。20.9.220.9.207:50:3707:50:37September 2, 2020 6、意志坚强的人能把世界放在手中像泥块一样任意揉捏。2020年9月2日星期三上午7时50分37秒07:50:3720.9.2 7、最具挑战性的挑战莫过于提升自我。2020年9月上午7时50分20.9.207:50September 2, 2020 8、业余生活要有意义，不要越轨。2020年9月2日星期三7时50分37秒07:50:372 September 2020
16、 9、一个人即使已登上顶峰，也仍要自强不息。上午7时50分37秒上午7时50分07:50:3720.9.2 10、你要做多大的事情，就该承受多大的压力。9/2/2020 7:50:37 AM07:50:372020/9/2 11、自己要先看得起自己，别人才会看得起你。9/2/2020 7:50 AM9/2/2020 7:50 AM20.9.220.9.2 12、这一秒不放弃，下一秒就会有希望。2-Sep-202 September 202020.9.2 13、无论才能知识多么卓著，如果缺乏热情，则无异纸上画饼充饥，无补于事。Wednesday, September 2, 20202-Sep-2020.9.2 14、我只是自己不放过自己而已，现在我不会再逼自己眷恋了。20.9.207:50:372 September 202007:50,谢谢大家,
