第四章-分治法.ppt

* 折半查找的二元比较树 5 7 2 1 3 4 6 8 9 内结点,表示一次元素的比较,存放已个mid值 每一条路经表示一个元素的比较序列 9 -6 -15 0 54 7 23 82 101 外结点,表示不成功检索的一种情况 * 大整数乘法 问题描述 对超过100位的十进制整数进行乘法运算。 两位整数的案例： 23=2*101+3*100 14=1*101+4*100 23*14=(2*101+3*100 )*(1*101+4*100) =(2*1)102+(3*1+2*4) 101+(3*4)100 对于任何两位数a=a1a0和b=b1b0 c=a*b=(a1*b1)102+[(a1+a0)*(b1+b0)-(c2+c0)] 101+(a0*b0) 100 * 分治法求解大整数乘法 计算两个n位整数a和b的积，n是正的偶数 把a的前半部分记为a1，后半部分记为a0 把b的前半部分记为b1，后半部分记为b0 a=a110n/2+a0， b=b110n/2+b0 c=a*b=(a110n/2+a0)*(b110n/2+b0) =(a1*b1)10n+(a1*b0+a0*b1)10n/2+(a0*b0) =c210n+c110n/2+c0 c2=a1*b1 c0= a0*b0 c1=(a1+a0)*(b1+b0)-(c2+c1) * 分治法求解大整数乘法 该算法做乘法的次数： 当n1时，M(n)=3M(n/2) , M(1)=1 当n=2k时，有 M(2k)=3M(2k-1)=3[3M(2k-2)]=32M(2k-2) =...=3kM(2k-k)=3k 因为k=log2n M(2k)=M(n)=3logn=nlog3≈n1.585 * Strassen矩阵乘法 传统方法：O(n3) 分治法: 将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为： 由此可得： * Strassen矩阵乘法 为了降低时间复杂度，必须减少乘法的次数。 * Strassen矩阵乘法 时间的递推关系式 当n1时，M(n)=7M(n/2)，M(1)=1 因为n=2k，M(n)=7M(n/2)=72M(n/22)…… =7kM(1)=7K M(n)=7log2n=nlog27 ≈n2.807 Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究３×３或５×５矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376) 是否能找到O(n2)的算法？？？目前为止还没有结果。 * * * * The Convex Hull of a 2D Point Set or Polygon /Archive/algorithm_0109/algorithm_0109.htm Convex Hulls /~ah/alg_anim/version1/ConvexHull.html * * * * 算法分析与设计 Analysis and Design of Computer Algorithms 第四章 分治法  Divide and Conquer * 分治法 教学内容 分治法的一般方法 合并排序 快速排序 折半查找 二叉树遍历及其相关特性 大整数乘法和Strassen矩阵乘法 用分治法解最近对问题和凸包问题 要求 掌握分治法的原理、效率分析以及在常见问题中的应用。 * 合并排序 8 3 2 9 7 1 5 4 8 3 2 9 7 1 5 4 8 3 2 9 7 1 5 4 8 3 2 9 7 1 5 4 3 8 2 9 1 7 4 5 2 3 8 9 1 4 5 7 1 2 3 4 5 7 8 9 * 分治法的一般方法 原始问题(N个输入) 子问题1 子问题2 子问题k … 子问题1 子问题2 子问题k … 相同的 类型 不用再分就可求解 合并最小问题的解 原始问题的解 * 分治法的抽象化控制 算法 DANDC(int p,int q) int m,p,q; //1≤p≤q≤n// if SMALL(p,q) return(G(p,q))； else m?DIVIDE(p,q)； //p≤m≤q// return(COMBINE(