算法分析TheAnalysisofAlgorithms.pptx
- 文档编号:18825360
- 上传时间:2023-12-20
- 格式:PPTX
- 页数:29
- 大小:2.24MB
算法分析TheAnalysisofAlgorithms.pptx
《算法分析TheAnalysisofAlgorithms.pptx》由会员分享,可在线阅读,更多相关《算法分析TheAnalysisofAlgorithms.pptx(29页珍藏版)》请在冰点文库上搜索。
算法分析与设计AnalysisandDesignofComputerAlgorithms第五章减治法DecreaseandConquer,杨春明西南科学技大学计算机学院,SchoolofComputerScienceandTechnology,SWUST,2,教学内容,减治法的一般方法及变种插入排序深度优先查找和广度优先查找生成组合对象的算法减常因子算法减可变规模算法要求掌握减治法的基本思想及在常见问题问题中的应用。
SchoolofComputerScienceandTechnology,SWUST,3,减治法,减治技术利用了一种关系:
一个问题给定实例的解和同样的问题较小实例的解之间的关系。
一旦建立了这种关系,就可以从顶至下(递归),也可以从底至上(非递归)的来运用。
减治法有三种变种:
1)减去一个常量2)减去一个常数因子3)减去的规模是可变的,SchoolofComputerScienceandTechnology,SWUST,4,减
(一)治技术,规模为n的问题,规模为n-1的子问题,子问题的解,原始问题的解,f(n)=anf(n)=f(n-1)*an1f(n)=an=1,SchoolofComputerScienceandTechnology,SWUST,5,减(半)治技术,规模为n的问题,规模为n/2的子问题,子问题的解,原始问题的解,an=(an/2)2n是偶数an=(a(n-1)/2)2*an是奇数an=an=1,SchoolofComputerScienceandTechnology,SWUST,6,插入排序,Forj2tondo将A(j)放到已分类集合A(0.j-1)的正确位置上Repeat,算法InsertionSort(A0.n-1)/用插入排序对给定数组排序/输入:
一个可排序数组/输出:
非降序列数组Afori1ton-1dovAi;ji-1;while(j0andAjv)Aj+1Aj;jj-1;Aj+1v;,89|456890293417,4589|6890293417,456889|90293417,45688990|293417,2945688990|3417,293445688990|17,17293445688990,SchoolofComputerScienceandTechnology,SWUST,7,深度优先查找,邻接矩阵表示,该遍历算法的时间效率属于(|V|2)邻接链表表示,该遍历算法的时间效率属于(|V|+|E|),SchoolofComputerScienceandTechnology,SWUST,8,SchoolofComputerScienceandTechnology,SWUST,9,广度优先查找,邻接矩阵表示,该遍历算法的时间效率属于(|V|2)邻接链表表示,该遍历算法的时间效率属于(|V|+|E|),SchoolofComputerScienceandTechnology,SWUST,10,SchoolofComputerScienceandTechnology,SWUST,11,广度优先查找,SchoolofComputerScienceandTechnology,SWUST,12,DFS与BFS的主要性质,SchoolofComputerScienceandTechnology,SWUST,13,拓扑排序(Topologicalsorting),有向图,SchoolofComputerScienceandTechnology,SWUST,14,拓扑排序(Topologicalsorting),SchoolofComputerScienceandTechnology,SWUST,15,拓扑排序(Topologicalsorting),SchoolofComputerScienceandTechnology,SWUST,16,生成排列(Permutations),生成由n个元素a1,a2,.,an的排列,算法JohnsonTrotter(n)/生成n个数的排列/输入:
一个正整数n/输出:
1,.,n的所有的排列数将第一个排列初始化为12.nwhile存在一个移动整数kdo求最大的移动整数k把k和它箭头指向的相邻整数互换调转所有大于k的整数的方向,课后思考:
如何按照字典序生成a1a2.an后面的排列呢?
SchoolofComputerScienceandTechnology,SWUST,17,生成子集(Subset),背包问题中如何穷举出给定物品集合的所有子集?
A=a1,a2,.,an=a1,a2,.,an-1an,SchoolofComputerScienceandTechnology,SWUST,18,假币问题(Fake-Coin),当n1时,W(n)=W(n/2)+1,W
(1)=0,SchoolofComputerScienceandTechnology,SWUST,19,俄式乘法(Multiplicationlarusse),两个大整数m和n乘法,SchoolofComputerScienceandTechnology,SWUST,20,约瑟夫斯问题(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,SWUST,21,约瑟夫斯问题(Josephus),?
J(n,m)=(J(n-1,m)+m)modnJ(1,m)=0,SchoolofComputerScienceandTechnology,SWUST,22,选择问题(SelectionProblem),问题描述给定一个含有n个元素的(或叫关键字)的集合,确定集合中第k小的元素。
V,划分元素,kj时,第k小元素所在的集合,Kj时,第k小元素所在的集合,K=j时,第k小元素就是划分元素,SchoolofComputerScienceandTechnology,SWUST,23,选择问题(SelectionProblem),ProcedureSELECT(A,n,k)integern,k,m,r,j;m1;rn+1;A(n+1)+;loopjrcallPARTITION(m,j)case:
k=j:
return:
kj:
rj:
else:
mj+1endcaserepeatEndSELECT,调用划分函数,两个新的子问题,T(n)=T(n/2)+(n+1),SchoolofComputerScienceandTechnology,SWUST,24,插值查找(Interpolationsearch),有序数组查找的另一种方法,由直线方程可得:
键值比较次数小于log2log2n+1,SchoolofComputerScienceandTechnology,SWUST,25,二叉树的查找与插入,最差效率(n),平均效率(logn),SchoolofComputerScienceandTechnology,SWUST,26,拈游戏(NimGame),有13根火柴棍,每次最少拿走1根,最多能拿走4根,拿走最后一根火柴的就是赢家。
该如何拿走火柴?
n=m+1实例是败局m+2n2m+1是胜局2m+2=2(m+1)另一个败局,获胜策略每次拿走nmod(m+1)根火柴棍,SchoolofComputerScienceandTechnology,SWUST,27,拈游戏(NimGame),多堆拈游戏每堆火柴棍的数量不一致,每次拿走火柴棍时可以从任意一堆中拿走任意允许数量的火柴棍,甚至可以把一堆都拿光。
拿走最后一根火柴的是赢家。
1901年,哈佛大学数学教授C.L.Bouton发现了一个精巧解法:
解是基于堆中数量的二进制表示的。
b1,b2,.,bi分别是各堆数量的二进制表示;计算它们的二进制数位和(忽略进位)。
当且仅当二进制数位和中包含至少一个1时,为胜局;只包含0时,为败局。
SchoolofComputerScienceandTechnology,SWUST,28,减治法小结,减治技术利用了一种关系:
一个问题给定实例的解和同样的问题较小实例的解之间的关系。
一旦建立了这种关系,就可以从顶至下(递归),也可以从底至上(非递归)的来运用。
减治法有三种变种:
1)减去一个常量2)减去一个常数因子3)减去的规模是可变的用减治法解决的问题有:
插入排序,DFS,BFS,俄式乘法,选择问题,SchoolofComputerScienceandTechnology,SWUST,29,reference,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 TheAnalysisofAlgorithms