算法设计与分析之分治法

算法设计与分析2020年3月1日讲授内容：分治法教师：胡学钢、吴共庆分而治之设计范例1.将问题分解成子问题(举例)2.递归的解决子问题3.组合子问题的答案3/1/2020算法设计与分析-分治法2举例：合并排序1.分解：显而易见。2.解决：递归的对两个子数组排序。3.组合：线性时间合并。#子问题数目子问题规模分解和组合工作3/1/2020算法设计与分析-分治法3主方法（复习）3/1/2020算法设计与分析-分治法4二分查找在排序的数组中查找元素1.分解：检查中间元素2.解决：递归查找一个子数组3.组合：显而易见例子：查找93/1/2020算法设计与分析-分治法5二分查找•在排序的数组中查找元素1.分解：检查中间元素2.解决：递归查找一个子数组3.组合：显而易见•例子：查找93/1/2020算法设计与分析-分治法6二分查找在排序的数组中查找元素1.分解：检查中间元素2.解决：递归查找一个子数组3.组合：显而易见例子：查找93/1/2020算法设计与分析-分治法7二分查找在排序的数组中查找元素1.分解：检查中间元素2.解决：递归查找一个子数组3.组合：显而易见例子：查找93/1/2020算法设计与分析-分治法8二分查找在排序的数组中查找元素1.分解：检查中间元素2.解决：递归查找一个子数组3.组合：显而易见例子：查找93/1/2020算法设计与分析-分治法9二分查找在排序的数组中查找元素1.分解：检查中间元素2.解决：递归查找一个子数组3.组合：显而易见例子：查找93/1/2020算法设计与分析-分治法10二分查找的递归nlogba=nlog21=n0=1⇒CASE2(k=0)⇒T(n)=Θ(lgn).#子问题数子问题大小分解和组合工作3/1/2020算法设计与分析-分治法11求幂问题：计算简单算法：分而治之算法：如果n是偶数;如果n是奇数3/1/2020算法设计与分析-分治法12斐波纳契数递归定义:简单的递归算法：（指数时间），是黄金分割3/1/2020算法设计与分析-分治法13计算斐波纳契数•简单递归的测量：•递归测量:•这个方法不可靠，因为浮点计算的取整容易出错从下到上：•按顺序计算，每个数由前面两个数计算而来。•运行时间：3/1/2020算法设计与分析-分治法14定理:算法:递归测量.时间=(lgn).定理证明.(对n进行归纳.)初始(n=1):递归测量3/1/2020算法设计与分析-分治法15递归步骤(n≥2):递归测量3/1/2020算法设计与分析-分治法16输入:输出:矩阵相乘3/1/2020算法设计与分析-分治法17fori←1tondoforj←1tondocij←0fork←1tondocij←cij+aik⋅bkj运行时间=(n3)标准算法3/1/2020算法设计与分析-分治法18思想:n×n矩阵=2×2个(n/2)×(n/2)子矩阵:r=ae+bgs=af+bht=ce+dgu=cf+dh8个(n/2)×(n/2)子矩阵相乘4个(n/2)×(n/2)子矩阵相加分而治之算法3/1/2020算法设计与分析-分治法19#子矩阵数目子矩阵范围子矩阵相加nlogba=nlog28=n3⇒CASE1⇒T(n)=(n3).比普通的算法没有什么改进.分而治之算法分析3/1/2020算法设计与分析-分治法20•仅用7个递归乘完成2×2矩阵相乘P1=a⋅(f–h)P2=(a+b)⋅hP3=(c+d)⋅eP4=d⋅(g–e)P5=(a+d)⋅(e+h)P6=(b–d)⋅(g+h)P7=(a–c)⋅(e+f)r=P5+P4–P2+P6s=P1+P2t=P3+P4u=P5+P1–P3–P77乘,18加/减.注意:不依赖于乘法的交换性!Strassen’s思想3/1/2020算法设计与分析-分治法21P1=a⋅(f–h)P2=(a+b)⋅hP3=(c+d)⋅eP4=d⋅(g–e)P5=(a+d)⋅(e+h)P6=(b–d)⋅(g+h)P7=(a–c)⋅(e+f)r=P5+P4–P2+P6=(a+d)(e+h)+d(g–e)–(a+b)h+(b–d)(g+h)=ae+ah+de+dh+dg–de–ah–bh+bg+bh–dg–dh=ae+bg•仅用7个递归乘完成2×2矩阵相乘Strassen’s思想3/1/2020算法设计与分析-分治法221.分解:将A和B划分成(n/2)×(n/2)的子矩阵.用+and–组合成结果.2.解决:递归的进行7个(n/2)×(n/2)子矩阵相乘.3.组合:对(n/2)×(n/2)子矩阵进行+和–运算得到C.T(n)=7T(n/2)+(n2)Strassen’s思想3/1/2020算法设计与分析-分治法23T(n)=7T(n/2)+(n2)nlogba=nlog27≈n2.81⇒CASE1⇒T(n)=(nlg7).2.81看起来和3差别不大,但是因为区别是在指数项，所以对运行时间的影响是很明显的。实际上，Strassen算法在今天普通的计算机上运行时，在n≥32超过普通的算法。至今为止最好的(仅仅是理论上):(n2.376...).Strassen算法分析3/1/2020算法设计与分析-分治法24问题:用最小的面积将一棵有n个叶子的完全二叉树嵌入网格。H(n)=H(n/2)+(1)=(lgn)W(n)=2W(n/2)+(1)=(n)面积=(nlgn)VLSI布局3/1/2020算法设计与分析-分治法25L(n/4)(1)L(n/4)L(n)=2L(n/4)+(1)=()面积=(n)nH-树嵌入3/1/2020算法设计与分析-分治法26•分而治之仅仅是算法设计中强大的设计技术之一。•分而治之算法可以用递归和主方法进行分析。•能得到更加高效的算法。结论3/1/2020算法设计与分析-分治法27