(算法分析与设计)1.引论-递归与分治.ppt

算法设计与分析 递归与分治 问题: 设X,Y是两个n位二进制数,求XY. 分治算法思路:若两个1位数相乘或相加看作1步运算,按传统乘法需 O(n2)次运算.将每个n(n=2K)位的二进制整数分为2段,每段的长为n/2位 计算XY须3次n/2位整数的乘法,6次加.减和2次移位 X=A 2n/2 +B y= C 2n/2 +D。 XY＝(A 2n/2 +B) (C 2n/2 +D) ＝AC2n+(AD+CB)2n/2 +BD T(n)= T(1)= O(1) T(n)= 4T(n/2)+ O(n) 计算XY须4次n/2位整数的乘法,3次不超过2n位的整数加法,2次 移位(乘2n 和乘2n/2 ).XY的 T(n)满足 解得 T(n) =O(n2) T(n)= T(1)= O(1) T(n)= 3T(n/2)+ O(n) 解得 T(n) =O(nlog3) 2.4 大整数的乘法 没有改善 改进: XY＝AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD 算法 算法设计与分析 递归与分治 { S=SIGN(X)*SIGN(Y)； X:=ABS(X)；Y:=ABS(Y)； if n=l then if (X=1) and (Y=1) then return(S) else return(0) else { A:=X的左边n/2位； B:=X的右边n/2位； C:=Y的左边n/2位； D:=Y的右边n/2位； m1:=MULT(A，C，n/2)； m2:=MULT(A-B,D-C，n/2)； m3:=MULT(B，D，n/2)； S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3)； return (S) }} { X,Y为2个小于2n的二进制整数，返回结果为X和Y的乘积XY} function MULT(X,Y,n) 大数相乘的分治递归算法 二进制大整数乘法同样可应用于十进制大整数的乘法 存放XY的符号 存放三个乘积 算法 2.5 矩阵相乘的Strassen法 常规算法:设矩阵A=(aij)n?n,B=(bij)n?n, C=A?B=(cij)n?n 计算C共需n?n2个乘法,n2(n-1)个加法. 分治算法:划分A,B为四个n/2(n=2K )阶方阵,则: C11=A11B11+A12B21 C12=A11B11+A12B21 C21=A11B11+A12B21 C22=A11B11+A12B21 若 n=2,可直接计算C; 若n2,C需8个n/2阶方阵的乘法和4个加法. T(n)= T(2)= O(1) T(n)= 8T(n/2)+O(n2) 得: T(n)=O(n3) T(n)=O(n3) 改进 C11 =M5+ M4 - M2+M6 C12 = M1+M2 C21 = M3+M4 C22 = M5+M1 - M3 - M7 M1=A11 (B12-B21) M2= (A11+A12) B22 M3= (A21+A22) B11 M4= A22 (B21-B11) M5= (A11+A22)(B11+B22) M6= (A12+A22)(B21+B22) M7 = (A11 - A21)(B11+B12) 验证:C22 = M5+M1-M3-M7 = (A11+A22)(B11+B22) +A11 (B12-B21) -(A21+A22) B11 - (A11-A21)(B11+B12) =A11B11+A11B22+A22B11+A22B22+A11B12 -A11B22- A21B11 - A22B11 - A11B11 - A11B12+A21B11+A21B12 =A21B12+A22B22 算法设计与分析 递归与分治 算法 算法设计与分析 procedure STRASSEN(n,A,B,C)； { if n=2 then MATRIX_MULTIPLY(A,B,C) else { 将矩阵A和B分块； STRASSEN( n/2，A11，B12-B22，M1)； STRASSEN( n/2，A11+A12，B22，M2)； STRASSEN( n/2，A21+A22，B11，M3