第三章Divide-and-Conquer技术邹权(博士)计算机科学系3.1Divide-and-Conquer原理3.2整数乘法3.3矩阵乘法3.4Findingtheclosestpairofpoints提要3.1Divide-and-Conquer原理•Divide-and-Conquer算法的设计•Divide-and-Conquer算法的分析•设计过程分为三个阶段–Divide:整个问题划分为多个子问题–Conquer:求解各子问题(递归调用正设计的算法)–Combine:合并子问题的解,形成原始问题的解Divide-and-Conquer算法的设计原始问题求解子问题子问题子问题子问题…求解子问题求解子问题子问题解子问题解子问题解…合并子解问题分解DivideConquerMerge原始问题的解Homework•云计算、Map-Reduce、Hadoop、Mahout•分析过程–建立递归方程–求解•递归方程的建立方法–设输入大小为n,T(n)为时间复杂性–当nc,T(n)=(1)Divide-and-Conquer算法的分析–Divide阶段的时间复杂性•划分问题为a个子问题。•每个子问题大小为n/b。•划分时间可直接得到=D(n)–Conquer阶段的时间复杂性•递归调用•Conquer时间=aT(n/b)–Combine阶段的时间复杂性•时间可以直接得到=C(n)–总之•T(n)=(1)ifnc•T(n)=aT(n/b)+D(n)+C(n)otherwise–求解递归方程T(n)•使用第二章的方法例1.Merge-sort算法DivideConquerCombine9486521371094865213710Merge-sortMerge-sort4568912371012345678910T(n)=2T(n/2)+O(n)T(n)=O(nlogn)例2.求一个集合中的最大数算法29,14,15,1,6,10,32,1229,14,15,16,10,32,1229,1415,132,126,1029151032293232T(n)=2T(n/2)+1T(n)=n-13.2整数乘法问题定义输入:n位二进制整数X和Y输出:X和Y的乘积通常,计算X*Y时间复杂性位O(n2),我们给出一个复杂性为O(n1.59)的算法。ABn/2位X=n/2位CDn/2位Y=n/2位XY=(A2n/2+B)(C2n/2+D)=AC2n+((A-B)(C-D)+AC+BD)2n/2+BD算法1.计算A-B和C-D;2.计算n/2位乘法AC、BD、(A-B)(C-D);3.计算(A-B)(C-D)+AC+BD;4.AC左移n位,((A-B)(C-D)+AC+BD)左移n/2位;5.计算XY。算法的数学基础•建立递归方程T(n)=(1)ifn=1T(n)=3T(n/2)+O(n)ifn1•使用Master定理T(n)=O(nlog3)=O(n1.59)算法的分析3.3矩阵乘法问题定义输入:两个nn矩阵A和A输出:X和Y的积通常,计算XY的时间复杂性位O(n3),我们给出一个复杂性为O(n2.81)的算法。算法的数学基础把C=AB中每个矩阵分成大小相同的4个子矩阵每个子矩阵都是一个n/2n/2矩阵于是22211211CCCC22211211AAAA22211211BBBB=展开并整理等式的右边,即得到计算的方法M1=A11(B12-B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A12)(B11+B12)•计算n/2n/2矩阵的10个加减和7个乘法算法C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1–M3–M7•计算n/2n/2矩阵的8个加减•18个n/2n/2矩阵加减法,每个需O(n2)•7个n/2n/2矩阵乘法•建立递归方程T(n)=O(1)n=2T(n)=7T(n/2)+O(n2)n2•使用Master定理求解T(n)T(n)=O(nlog7)O(n2.81)算法复杂性分析3.4Findingtheclosestpairofpoints问题定义输入:Euclidean空间上的n个点的集合Q输出:P1,P2Q,Dis(P1,P2)=Min{Dis(X,Y)|X,YQ}Dis(X,Y)是Euclidean距离:如果X=(x1,x2),Y=(y1,y2),则221221)()yyxxDis(X,Y)(一维空间算法•利用排序的算法–算法•把Q中的点排序•通过排序集合的线性扫描找出最近点对–时间复杂性•T(n)=O(nlogn)一维空间算法(续)•Divide-and-conquer算法Preprocessing:1.如果Q中仅包含2个点,则返回这个点对;2.求Q中点的中位数m。Divide:1.用Q中点坐标中位数m把Q划分为两个大小相等的子集合Q1={xQ|xm},Q2={xQ|xm}Q1Q2p1p2p3q3q2q1mConquer:1.递归地在Q1和Q2中找出最接近点对(p1,p2)和(q1,q2)Q1Q2p1p2p3q3q2q1m2.在(p1,p2)、(q1,q2)和某个(p3,q3)之间选择最接近点对(x,y),其中p3是Q1中最大点,q3是Q2中最小点,(x,y)是Q中最接近点。Merge:•时间复杂性–Divide阶段需要O(n)时间–Conquer阶段需要2T(n/2)时间–Merge阶段需要O(n)时间–递归方程T(n)=O(1)n=2T(n)=2T(n/2)+O(n)n3–用Master定理求解T(n)T(n)=O(nlogn)二维空间算法•Divide-and-conquer算法Divide:1.计算Q中各点x-坐标的中位数m;2.用垂线L:x=m把Q划分成两个大小相等的子集合QL和QR,QL中点在L左边,QR中点在L右边.Preprocessing:1.如果Q中仅包含一个点,则算法结束;2.把Q中点分别按x-坐标值和y-坐标值排序.Divide:1.递归地在SL、SR中找出最接近点对:(p1,p2)SL,(q1,q2)SR2.d=min{Dis(p1,p2),Dis(q1,q2)};p1p2q1q2L:x=mQLQRm-dm+d临界区Merge:1.在临界区查找距离小于d的点对(pl,qr),plQL,qrQR;2.如果找到,则(pl,qr)是Q中最接近点对,否则(p1,p2)和(q1,q2)中距离最小者为Q中最接近点对.关键是(pl,qr)的搜索方法及其搜索时间(pl,qr)的搜索方法:–如果(p,q)是最接近点对而且pQL,qQR,则dis(p,q)d,(p,q)只能在下图的区域D.–若p在分割线L上,包含(p,q)的区域D最大,嵌于d2d的矩形(p-右邻域)中,如下图所示.LpdddDLpddd2dDp-右邻域只包含6个点–对于任意p,我们只需在p-右邻域中点q,最多6个.–算法1.把临界区中所有点集合投影到分割线L上;2.对于左临界区的每个点p,考察p-右临界区的每个点(这样的点共有6个)q,如果Dis(p,q)d,则令d=Dis(p,q);3.如果d发生过变化,与最后的d对应的点对即为(pl,qr),否则不存在(pl,qr).•时间复杂性–Divide阶段需要O(n)时间–Conquer阶段需要2T(n/2)时间–Merge阶段需要O(n)时间–递归方程T(n)=O(1)n=2T(n)=2T(n/2)+O(n)n3–用Master定理求解T(n)T(n)=O(nlogn)•正确性分析定理1.对于左临界区中的每个点p,p-右邻域中仅包含6个点。证明:把p-右邻域划分为6个(d/2)(2d/3)的矩形。若p-右邻域中点数大于6,由鸽巢原理,至少有一个矩形中有两个点,设为u、v.(xu-xv)2+(yu-yv)2(d/2)2+(2d/3)2=25d2/36即Dis(u,v)5d/6d,与d的定义矛盾。2d/32d/32d/3d/2d/2uv