[工学]第四章 递归与分治.ppt

第4章 递归和分治2 信工计算机系2008 分治法基本原理 简单例子 多项式乘积的分治算法 Strassen矩阵乘积 大整数乘法 第2讲学习内容 基本思想：是将一个规模为n的问题分解为k个规模 较小的子问题，这些子问题互相独立且与原问题相 同。递归地解这些子问题，然后将各子问题的解合 并得到原问题的解。 4.4 分治法的基本思想 分治法的一般设计步骤： divide_and_conquer(p(n) if(nAi ? max : Ai; min = min2，序列划分为两个长度基本相等的 子序列。 治理步：用分治法对两个子序列进行最大最小求解 组合步：对得到的数据比较，求到全序列的最大 最小。 最大最小问题分治法 void max_min(int A,int if(high-low)x2 ? x1:x2; min = y12，为降阶，将p(x)、q(x）分别划 分为两个多项式： 治理、组合步： 多项式乘积的分治算法 分治算法时间复杂度： 用换名，递推法解，有T(n)=O(n2)。 上述划分后分块直接乘的分治算法并未降低O(n2)的 时间复杂性，其原因是算法中的多项式乘积次数为 四次。有效的分治算法是设法降低多项式乘积次 数。 多项式乘积的分治算法 治理、组合步改进： 多项式乘积的分治算法改进 记： 多项式乘积的分治算法改进 改进后的分治算法乘积次数为三次。 改进分治算法时间复杂度： 用换名，递推法解，有T(n)=O(nlog3)。 多项式乘积的分治算法改进 改进分治算法的时间复杂性O(nlog3)，优于直接乘 积的O(n2)，其原因在于降低了低阶多项式乘积次 数。 该思想也被用于后续的矩阵乘积和大整数乘法分 治算法中，它们都是通过降低低阶乘积次数达到 改进时间复杂性的目的。 例4.11：设多项式 p(x) = 1+ x - x2 + 2x3 q(x) = 1- x + 2x2 3x3 用分治法计算这两个多项式的乘积。 多项式乘积的分治算法实例 解：n=4,n/2=2,划分多项式得： p(x) = (1+ x) +(-1 + 2x)x2 q(x) = (1- x) +(2 3x)x2 多项式乘积的分治算法实例 多项式乘积的分治算法实例 多项式乘积的分治算法实现 多项式p(x)、q(x)、p(x)q(x)均用数组存放。 输入：多项式系数个数n 含n个元素的数组pp(x)的系数 含n个元素的数组qq(x)的系数 输出：含2n-1个元素的数组r0p(x)q(x)的系数 多项式分治算法实现的关键在于计算过程中r0、r1 、r2元素存放位置及计算时p,q的起始位置和涉及的 元素个数。 多项式乘积的分治算法实现 下面以例4.11为例观察各数组变化。 初始:n=4,令k=n/2=2 11-12 多项式乘积的分治算法实现 p数组： q数组： 1-12-3 k p0p1 k q0q1 计算r0：r0(x)=p0(x)q0(x)=(1+x)(1-x) 10-1 多项式乘积的分治算法实现 r0数组： p、q从0开始，长度为k的元素组成的多项式的乘积 r0在p(x)q(x)中最低次为0，最高次2k-2。 计算r1：r1(x)=p1(x)q1(x)=(-1+2x)(2-3x) -27-6 多项式乘积的分治算法实现 r1数组： p、q从k开始，长度为k的元素组成的多项式的乘积 r1在p(x)q(x)最低次为n，最高次2n-2。 计算r2：r2(x)=(p0(x)+p1(x)(q0(x)+q1(x) 03 多项式乘积的分治算法实现 r3数组： r3(x) = p0(x)+p1(x) r4(x) = q0(x)+q1(x) 3-4 r4数组： r2(x) = r3(x)r4(x) r3、r4从0开始，长度为k的元素组成的多项式的乘积 r2在p(x)q(x)最低次为k，最高次3k-2。 多项式乘积的分治算法实现 09-12r2数组： r2(x)= r2(x) r0(x) r2 从k开始，r0从0开始，长度为2k-1的对应元素相减 多项式乘积的分治算法实现 09-12 r2数组： 10-1 r0数组： -19-11r2结果： r2(x)= r2(x) r1(x) r2 从k开始，r0从n开始，长度为2k-1的对应元素相减 多项式乘积的分治算法实现 -19-11r2数组： -27-6 r1数组： 12-5r2结果： r0(x) = r0(x) + r2(x)(计算r0(x) + r2(x)xk） r0 从k开始，r2从k开始，长度为2k-1的对应元素相加 多项式乘积的分治算法实现 10-1r0数组： 12-5 r2数组： 1002-5r0结果： r0(x) = r0(x) + r1(x)(计算p(x)q(x)） r0 从n开始，r1从n开始，长度为2k-1的对应元素相加 多项式乘积的分治算法实现 1002-5r0数组： -27-6 r1数组： 1002-77-6r0结果： 计算结果 多项式乘积的分治算法实现 根据上述数组变化，定义函数： void PolyAdd(int p,int ps, int q, int qs, int r,int rs,int k) /rrs+i = pps+i + qqs + i i=0,k-1 void PolyMinus(int p,int ps, int q, int qs, int k) /pps+i = pps+i qqs+i i=0,k-1 多项式乘积的分治算法实现 void PolyMulti (int p,int ps, int q, int qs, int r,int rs,int n) /p(x) = pps + pps+1x + + pps+k-1xn-1 /q(x) = qqs +qqs+1x + + qqs+k-1xn-1 /r(x) = p(x)q(x)xrs 计算多项式乘积c(x) = p(x)q(x)即调用： PolyMulti(p,0,q,0,c,0,n)，即 多项式乘积分治算法描述： void PolyMulti (int p,int ps, int q, int qs, int r,int rs,int n) 定义r1,r2,r3,r4为数组，大小为2*n-1。元素初始为0。 if(n=2) 直接计算rrs,rrs+1,rrs+2; else k = n/2; PolyMulti(p,0,q,0,r,rs,k); /r0 =p0*q0 PolyMulti(p,k,q,k,r1,n+rs,k); /r1 = p1*q1 PolyAdd(p,0,p,k,r3,0,k); /r3 = p0+p1 PolyAdd(q,0,q,k,r4,0,k); /r4 = q0+q1 PolyMulti(r3,0,r4,0,r2,k+rs,k); /r2 = r3*r4 PolyMinus(r2,k+rs,r0,rs,2*k-1); PolyMinus(r2,k+rs,r1,n+rs,2*k-1); PolyAdd(r,k+rs,r2,k+rs,r,k+rs,2*k-1); PolyAdd(r,n+rs,r1,n+rs,r,n+rs,2*k-1); 由于数组传递的特殊性，可省略ps,qs,rs，其实现见 P97 算法4.10。 n2k时：对p(x)、q(x)补系数0，使其系数个数为2k， 取计算结果的前2n-1项。 2个n阶矩阵A、B相乘，结果矩阵C是n阶矩阵，且 按公式直接计算，该算法的时间复杂性为(n3)。 4.7 Strassen矩阵乘积 矩阵乘积的分治策略： 直接解：n=2 划分步：n=2k,将各矩阵分解为4个n/2阶矩阵，即 治理步、组合步： C11 = A11*B11+A12*B21 C12 = A11*B12+A12*B22 C21 = A21*B11+A22*B21 C22 = A21*B21+A22*B22 D1 D2 5：C11 1 2 346 7 D1 8 9 D2 10:C12 矩阵乘积分治策略举例： C11=D1+D2 设T(n)为2个n阶矩阵乘积的乘法和加法运算次数。 根据分治策略描述，得递归方程为： 求解该方程： 矩阵乘积分治策略时间复杂性分析 时间复杂性未降低，同 多项式相乘，需设法降 低n/2矩阵的乘积次数。 矩阵乘积分治策略时间复杂性分析 上述矩阵乘积分治策略对n阶矩阵乘积计算了8个n/2 矩阵乘积，Stassen矩阵乘法改进了其中的治理步和 综合步，用如下方法进行： Strassen矩阵乘积 M1 = A11*(B12-B22) 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) C11 = M5+M4-M2+M6 C12 = M1+M2 C21 = M3+M4 C22 = M5+M1-M3-M7 共计算7个n/2阶矩阵乘积，18个n/2阶矩阵加减。 设T(n)为2个n阶矩阵乘积的乘法和加法运算次数。 根据Strassen矩阵乘法,得其递归方程为： 求解该方程： Strassen矩阵乘积时间复杂性分析 Strassen矩阵乘积时间复杂性分析 Hopcroft和Kerr已经证明(1971)，计算2个矩 阵的乘积，7次乘法是必要的。因此，要想进一步改 进矩阵乘法的时间复杂性，就不能再基于计算22矩 阵的7次乘法这样的方法了。或许应当研究33或 55矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算 时间复杂性。 目前最好的计算时间上界是(n2.376)。 目前知道的最好下界为(n2)。 关于矩阵乘积 4.8 大整数乘法 问题描述：设X、Y是n位十进制大整数，用软件 方法计算X*Y。 直接解：n=1 划分步：X、Y分别划分为两个n/2位整数。 n/2位 ABX= n/2位 CDY= X=A*10n/2+B Y=C*10n/2+D 大整数乘法的分治策略 治理步、组合步： 计算包括4次n/2个十进制整数乘积，2次移位，3 次加。 大整数乘法的分治策略 分治策略