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

第4章 递归和分治2 信工计算机系2008 第2讲学习内容 分治法基本原理 简单例子 多项式乘积的分治算法 Strassen矩阵乘积 大整数乘法 基本思想：是将一个规模为n的问题分解为k个规模 较小的子问题，这些子问题互相独立且与原问题相 同。递归地解这些子问题，然后将各子问题的解合 并得到原问题的解。 分治法的一般设计步骤： divide_and_conquer(p(n)) { if(n=n0) return adhoc(p(n)); //直接解 else { divide p into smaller subinstances p1,p2,…,pk; //划分步 for(i=1; i=k; i++) //治理步 yi = divide_and_conquer(pi); return merge(y1,y2,…,yk); } //组合步 } 划分步：把输入的问题实例划分为k个子问题。 应尽量使k个子问题的规模大致相同。通常， k=2 治理步：指当问题规模大于某个预定义的阀值n0时，解子问题的k个递归调用。 组合步：将各个子问题的解组合起来。 分治法的时间复杂性分析 对上述一般设计步骤进行。设T(n)为分治算法的计算时间。 直接解：设n0=1,计算时间为O(1) 划分步：划分为k个问题规模为n/k的子问题 组合步：计算时间为f(n) 得T(n)的递归方程为： 4.5 分治法的简单实例 例4.8 最大最小问题—在n个整数中选出最大值、 最小值。 最大最小问题直接解 解：一般求解算法： void max_min(int A[],int max,int min,int n) { int x; max = A[0]; min = A[0]; for(i=1; in; i++) { max = maxA[i] ? max : A[i]; min = minA[i] ? min : A[i];} } 例4.9：二分有哪些信誉好的足球投注网站：在n个有序元素a[0],…,a[n-1]中 查找特定元素x。 解： 直接解：n=1 划分步、治理步： mid =(0+n-1)/2; if(x==a[mid]) 找到 else if(xa[mid]) 在a[0],…,a[mid-1]中找 else 在a[mid+1],…,a[n-1]中找 无组合步 设n个元素的比较次数为T(n),根据二分有哪些信誉好的足球投注网站算法： 例4.10 对n个元素a[0],…,a[n-1]进行归并排序。 直接解：n=1 划分步：划分为2个n/2子序列 治理步：对2个n/2子序列分别进行归并排序 组合步：对2个排好序的子序列排序 问题描述：已知多项式 直接解：n=2，多项式只有两个系数，直接乘 治理、组合步： 上述划分后分块直接乘的分治算法并未降低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 初始:n=4,令k=n/2=2 计算r0：r0(x)=p0(x)q0(x)=(1+x)(1-x) 计算r1：r1(x)=p1(x)q1(x)=(-1+2x)(2-3x) 计算r2：r2(x)=(p0(x)+p1(x))(q0(x)+q1(x)) PolyMinus(r2,k+rs,r0,rs,2*k-1); PolyMinus(r2,k+rs,r1,n+rs,2*k-