电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

算法设计与分析Chapter2Veron

73页
  • 卖家[上传人]:E****
  • 文档编号:91095457
  • 上传时间:2019-06-21
  • 文档格式:PPT
  • 文档大小:785.50KB
  • / 73 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、1,递归与分治策略,张可佳,2,理解递归的概念 掌握设计有效算法的分治策略 通过下面的范例学习分治策略设计技巧 二分搜索技术; 大整数乘法; Strassen矩阵乘法; 合并排序和快速排序; 线性时间选择; 最接近点对问题;,学习要点,3,递归的概念,递归,递归的概念 直接或间接调用自身的算法称为递归算法 用函数自身给出定义的函数称为递归函数,4,递归函数(阶乘函数),阶乘函数,5,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。,int fractorial (int n) If(n=0) return 1; return n*fractorial(n-1); ,递归函数(Fibonacci函数),Fibonacci数列 无穷数列1,1,2,3,5,8,13,21,34,55, 递归定义为,6,边界条件,递归方程,int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); ,整数划分问题,定义 将正整数n表示成一系列

      2、正整数之和 n=n1+n2+nk, 其中n1n2nk1,k1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。,7,例如正整数6有如下不同的划分: 6; 5+1; 4+2,4+1+1; 3+3,3+2+1,3+1+1+1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1。,整数划分问题,如果设p(n)为正整数n的划分数,则难以找到递归关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系,8,(1) q(n,1)=1,n1; 最大加数n1不大于1,任何正整数n只有一种划分形式,即,(2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此,q(1,m)=1,(3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1n-1的划分组成。,(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1 的划分组成。,整数划分问题,如果设p(n)为正整数n的划分数,则难以找到递归

      3、关系,因此考虑增加一个自变量:将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系,9,正整数n的划分数p(n)=q(n,n),整数划分问题,例子,10,q(6,3) = q(6,2) + q(3,3),= q(6,1) + q(4,2),+ 1 + q(3,2),= q(6,1) +,+ 1 +,1 + q(2,1),= q(6,1) + q(4,1) +,= 1 + 1 + 1 + 1 + 1 + 1 + 1 = 7,q(4,1) + q(2,2),q(3,1) + q(1,2),+ 1 + q(3,1) + q(1,2),3+3,3+2+1,3+1+1+1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1,Hanoi塔问题,设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上,并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则: 规则1:每次只能移动1个圆盘; 规则2:任何时刻都不允许将较大的圆盘压在较小的

      4、圆盘之上; 规则3:在满足移动规则1和2的前提下,可将圆盘移至a,b,c中任一塔座上。,11,Hanoi塔问题,要将n个圆盘按规则从A移动到C,只需 将n1个较小圆盘按规则从A移动到B 将最大的圆盘从A移动到C 将n-1个较小圆盘从B移动到C n个圆盘的移动问题可以转换为 两次n-1个圆盘移动的问题一个单一圆盘移动,12,Hanoi塔问题,void hanoi(int n, int A, int B, int C) if (n 0) hanoi(n-1, A, C, B); move(A, B); hanoi(n-1, C, B, A); hanoi(n, A, B, C)表示将n个圆盘按规则从A移动到B,移动的过程中用C最辅助塔座 move(A, B)表示将A上剩余的单一圆盘从A移动到B,13,函数调用的处理过程,函数A调用函数B时 保存A的所有运行状态 将实参指针、返回地址等信息传递给B 为B中的变量分配存储区 将控制转移到B的入口 从函数B返回到函数A时 保存B的计算结果 释放分配给B的存储区 依照返回地址将控制转移到A,14,递归的处理过程,函数A调用自身 分层:A0, A1,

      5、 A2, A0调用A1 A1调用A2 A2调用A3 A3返回给A2 A2返回给A1 A1返回给A0,15,A0的运行状态,A1的运行状态,A2的运行状态,A0,A1,A2,A3,递归的特点,优点 结构清晰可读性强 容易用数学归纳法来证明算法的正确性 缺点 递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多,16,消除递归,采用一个用户定义的栈来模拟系统的递归调用工作栈 机械地模拟与递归算法效果相同 根据程序特点对递归调用的工作栈进行简化,减少栈操作,17,18,分治策略,分治策略,分 将要求解的较大规模的问题分割成k个更小规模的子问题。 如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。 治 求解各个子问题 合 将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。,19,原始问题,求解子问题,子问题,子问题,子问题,求解子问题,求解子问题,子问题解,子问题解,子问题解,合并子解,问题分解,分,治,合,原始问题的解,分治策略,如何分? 应该把原问题划分为多少个子问题?

      6、 每个子问题的规模是否相同? 从大量实践中发现,最好使子问题的规模大致相同 许多问题可以取k=2,21,合并排序算法,输入:a1, , n 输出:a1, , n 满足 a0 a1 an 基本思想: 将待排序元素分为大小相等的两个子集合 分别对两个子集合排序 将排好序的子集合合并为最终结果,22,合并排序算法,23,void MergeSort(Type a, int left, int right) if (leftright) /至少有2个元素 int i=(left+right)/2; /取中点 MergeSort(a, left, i); MergeSort(a, i+1, right); Merge(a, b, left, i, right); /合并到数组b Copy(a, b, left, right); /复制回数组a ,Merge(a, b, left, i, right): 将排好序的aleft, , i和ai+1, , right按顺序合并到数组b中,合并排序算法,时间复杂性T(n) Merge和Copy可以在O(n)时间内完成,24,合并排序算法,消除递归 首先将

      7、a中相邻的元素两两配对 用合并算法将它们排序,构成n/2个长度为2的排好序的数组 再用合并算法将它们排序成n/4个长度4的排好序数组,25,void MergeSort(Type a, int n) int i=1; while(in) 对a进行一边扫描,将a中大小为i的相邻数组合并; ,合并排序算法,运行例子,26,分治策略的时间复杂性,假设分治方法将原问题分解为k个规模为n/m的子问题来求解,则 其中,f (n)为将原问题分解为k个子问题及将k个子问题的解合并为原问题的解所需要的时间,27,二分搜索算法,解决查找元素问题 输入:已经按升序排好序的数组a0,n-1, 某个元素x 输出:x在a中的位置,28,该问题的规模缩小到一定的程度就可以容易地解决; 该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解; 分解出的各个子问题是相互独立的。,二分搜索算法,29,比较x和a的中间元素amid 若x=amid,则x在L中的位置就是mid; 如果xai,同理我们只要在amid的后面查找x即可。 无论是在前面还是后面查找x,其方法都和在a中查找x一样,只不过是查

      8、找的规模缩小了。,二分搜索算法,30,据此容易设计出二分搜索算法: int BinarySearch(Type a, const Type ,算法复杂度分析: 每执行一次算法的while循环, 待搜索数组的大小减少一半。因此,在最坏情况下,while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间,因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。,大整数乘法,计算两个n位整数的乘积,31,小学生方法:O(n2) 效率太低 分治法1:,X =,a,b,c,d,X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd,Y =,复杂度分析 T(n)=O(n2) 没有改进,大整数乘法,为了降低时间复杂度,必须减少乘法的次数。 分治法2 XY = ac 2n + (ad+bc) 2n/2 + bd ac 2n + (a-c)(b-d)+ac+bd) 2n/2 + bd,32,复杂度分析 T(n)=O(nlog3) =O(n1.59)较大的改进,大整数乘法,33,小学生方法:O(n2) 效率太低 分治法: O

      9、(n1.59) 较大的改进 更快的方法?,如果将大整数分成更多段,用更复杂的方式把它们组合起来,将有可能得到更优的算法。,Strassen矩阵乘法,问题 输入:nn的矩阵A和B 输出:C=AB 简单方法 复杂性O(n3),34,Strassen矩阵乘法,简单分治 使用与上例类似的技术,将矩阵A,B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为:,35,复杂度分析 T(n)=O(n3),Strassen矩阵乘法,为了降低时间复杂度,必须减少乘法的次数。 Strassen分治,36,复杂度分析 T(n)=O(nlog7) =O(n2.81)较大的改进,Strassen矩阵乘法,37,传统方法:O(n3) 分治法: O(n2.81) 更快的方法?,Hopcroft和Kerr已经证明(1971),计算2个矩阵的乘积,7次乘法是必要的。因此,要想进一步改进矩阵乘法的时间复杂性,就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376) 是否能找到O(n2)的算法?,快速排序,对数组ap : r进行排序 分:以ap=x为基准将ap : r划分为3段 ap : q-1, aq, aq+1 : r aq=x ap : q-1中的元素小于等于aq aq+1 : r中的元素大于等于aq 治:递归调用快速排序算法对ap : q-1和aq+1 : r排序 合:,38,快速排序,39,void QuickSort (Type a, int p, int r) if (pr) int q = Partition(a,p,r); QuickSort (a,p,q-1); /对左半段排序 QuickSort (a,q+1,r); /对右半段排序

      《算法设计与分析Chapter2Veron》由会员E****分享,可在线阅读,更多相关《算法设计与分析Chapter2Veron》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.