- 1、本文档共54页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
计算机算法设计与分析(第4版)第2章资料
第2章 递归与分治策略 学习要点: 理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 (1)二分有哪些信誉好的足球投注网站技术; (2)大整数乘法; (3)Strassen矩阵乘法; (4)棋盘覆盖; (5)合并排序和快速排序; (6)线性时间选择; (7)最接近点对问题; (8)循环赛日程表。 算法总体思想 将要求解的较大规模的问题分割成k个更小规模的子问题。 2.1 递归的概念 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。 2.1 递归的概念 例3 Ackerman函数 A(n,m)的自变量m的每一个值都定义了一个单变量函数: M=0时,A(n,0)=n+2 M=1时,A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2,和A(1,1)=2故A(n,1)=2*n M=2时,A(n,2)=A(A(n-1,2),1)=2A(n-1,2),和A(1,2)=A(A(0,2),1)=A(1,1)=2,故A(n,2)= 2^n 。 M=3时,类似的可以推出 M=4时,A(n,4)的增长速度非常快,以至于没有适当的数学式子来表示这一函数。 例3 Ackerman函数 定义单变量的Ackerman函数A(n)为,A(n)=A(n,n)。 定义其拟逆函数α(n)为:α(n)=min{k|A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。 α(n)在复杂度分析中常遇到。对于通常所见到的正整数n,有α(n)≤4。但在理论上α(n)没有上界,随着n的增加,它以难以想象的慢速度趋向正无穷大。 分治法的适用条件 分治法所能解决的问题一般具有以下几个特征: 该问题的规模缩小到一定的程度就可以容易地解决; 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解; 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 Strassen矩阵乘法 使用与上例类似的技术,将矩阵A,B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为: 传统方法:O(n3) 分治法: 由此可得: 复杂度分析 T(n)=O(n3) Strassen矩阵乘法 传统方法:O(n3) 分治法: 为了降低时间复杂度,必须减少乘法的次数。 复杂度分析 T(n)=O(nlog7) =O(n2.81)?较大的改进 Strassen矩阵乘法 传统方法:O(n3) 分治法: O(n2.81) 更快的方法?? Hopcroft和Kerr已经证明(1971),计算2个2×2矩阵的乘积,7次乘法是必要的。因此,要想进一步改进矩阵乘法的时间复杂性,就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究3×3或5×5矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376) 是否能找到O(n2)的算法? 棋盘覆盖 在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 棋盘覆盖 当k0时,将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。 特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如 (b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为棋盘1×1。 棋盘覆盖 void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; int t = tile++, // L型骨牌号 s = size/2; // 分割棋盘 // 覆盖左上角子棋盘 if (dr tr + s dc tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc, dr, d
您可能关注的文档
- 计算机新技术.ppt
- 计算机病毒的历史.ppt
- 计算机病毒的发展过程.ppt
- 计算机病毒基础知识资料.ppt
- 液压模块三课题8.ppt
- 计算机病毒知多少.ppt
- 计算机的体系结构.ppt
- 计算机病毒virus_4讲.ppt
- 计算机病毒的基本概念.ppt
- 液压模块二课题6.ppt
- 七章货物的保险.pptx
- 三章国际间接投资.pptx
- 人性假设理论.pptx
- 外研高一英语必修三ModuleIntroduction汇总市公开课获奖课件省名师示范课获奖课件.pptx
- 月相成因优质获奖课件.pptx
- 小学二年级语文课件《狐假虎威》省名师优质课赛课获奖课件市赛课一等奖课件.pptx
- 养羊业概况专题知识讲座.pptx
- 微生物的实验室培养市公开课获奖课件省名师示范课获奖课件.pptx
- 人教版六年级下册式与方程整理与复习市公开课获奖课件省名师示范课获奖课件.pptx
- 必威体育精装版高中精品语文教学:第二单元-第7课-诗三首:涉江采芙蓉、-短歌行、归园田居市公开课获奖课件省名师.pptx
文档评论(0)