《算法设计与分析》-第二章-递归与分治讲课教案

《算法设计与分析》-第二章-递归与分治2.1分治法（divide-and-conquer）的基本思想为求解大问题，可以：分割成k个更小规模的子问题。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。将要求解的较大规模的问题分割成k个更小规模的子问题。2.1分治法的基本思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=

对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.1分治法的基本思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.1分治法的基本思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)2.1分治法的基本思想将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

2.1分治法的基本思想2.1分治法的基本思想2.2分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。2.3分治法的基本步骤divide-and-conquer(P){

if(|P|<=n0)adhoc(P);//解决小规模的问题

dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题

for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//递归的解各子问题

returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解}

大量实践证明：在用分治法设计算法时，将一个问题分成大小相等的k个子问题的处理方法是行之有效的复杂性分析： 设一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。则有：通过迭代法求得方程的解：2.3分治法的基本步骤2.4分治法的应用分治算法通常采用递归操作实现。但并非所有的递归函数都是分治算法。2.4分治法的应用例1阶乘函数 阶乘函数可递归地定义为：边界条件递归方程2.4分治法的应用例2Fibonacci数列

无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为：2.4分治法的应用例2Fibonacci数列

无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为：例3排列问题

设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：

当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。

2.4分治法的应用全排列算法voidperm(intlist[],intk,intm){//产生list[k..m]的所有排列//其中list[0..k-1]是前缀，后缀是list[k..m]//调用perm(list,0,n-1)则产生list[0..n-1]的全排列if(k==m){For(i=0;i<=m;i++)Printf(“%d”,list[i]);Printf(“\n”);}elseFor(i=k;i<=m;i++){Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}例3二分搜索技术给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。2.4分治法的应用二分搜索算法：intbinarySearch(inta[],intx,intn){left=0;right=n-1;

while(left<=right){intmiddle=(left+right)/2;

if(x==a[middle])returnmiddle;

if(x>a[middle])left=middle+1;

elseright=middle-1;}

return-1;//未找到x}思考题：写出二分搜索的递归算法。例3二分搜索技术2.4分治法的应用A和B的乘积矩阵C中的元素C[i,j]定义为:

传统方法：O(n3)例4Strassen矩阵乘法2.4分治法的应用Strassen矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：分治法:由此可得：复杂度分析T(n)=O(n3)

没有改进Strassen矩阵乘法改进:为了降低时间复杂度，必须减少乘法的次数。复杂度分析T(n)=O(nlog7)=O(n2.81)

较大的改进例5

棋盘覆盖在一个2k×2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。2.4分治法的应用棋盘覆盖当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

棋盘覆盖voidchessBoard(inttr,inttc,intdr,intdc,intsize){

if(size==1)return;intt=tile++,//L型骨牌号s=size/2;//分割棋盘//覆盖左上角子棋盘

if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盘中

chessBoard(tr,tc,dr,dc,s);

else{//此棋盘中无特殊方格//用t号L型骨牌覆盖右下角board[tr+s-1][tc+s-1]=t;//覆盖其余方格

chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上角子棋盘

if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盘中

chessBoard(tr,tc+s,dr,dc,s);

else{//此棋盘中无特殊方格//用t号L型骨牌覆盖左下角

board[tr+s-1][tc+s]=t;//覆盖其余方格

chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘

if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盘中

chessBoard(tr+s,tc,dr,dc,s);

else{//用t号L型骨牌覆盖右上角board[tr+s][tc+s-1]=t;//覆盖其余方格

chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆盖右下角子棋盘

if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盘中

chessBoard(tr+s,tc+s,dr,dc,s);

else{//用t号L型骨牌覆盖左上角board[tr+s][tc+s]=t;//覆盖其余方格

chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}复杂度分析T(n)=O(4k)渐进意义下的最优算法例6合并排序voidmergeSort(inta[],intleft,intright){if(left<right){//至少有2个元素inti=(left+right)/2;//取中点

mergeSort(a,left,i);

mergeSort(a,i+1,right);

merge(a,b,left,i,right);//合并到数组b

copy(a,b,left,right);//复制回数组a}}复杂度分析T(n)=O(nlogn)渐进意义下的最优算法2.4分治法的应用合并排序算法mergeSort的递归过程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]非递归的归并排序算法voidMergeSort(inta[],intn){s=1;while(s<n){MergePass(a,b,s,n);s+=s;MergePass(b,a,s,n);s+=s;}}voidMergePass(intx[],inty[],ints,intn){i=0;while(i<=n-2*s){Merge(x,y,i,i+s-1,i+2*s-1);i=i+2*s;}if(i+s<n)Merge(x,y,i,i+s-1,n-1);elsefor(j=i;j<=n-1;j++)y[j]=x[j];}非递归的归并排序算法(续)voidMerge(intc[],intd[],intl,intm,intr){i=l;j=m+1;k=l;while(i<=m&&j<=r){if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];}if(i>m)for(q=j;q<=r;q++)d[k++]=c[q];elsefor(q=i;q<=m;q++)d[k++]=c[q];}合并排序最坏时间复杂度：O(nlogn)平均时间复杂度：O(nlogn)辅助空间：O(n)稳定性：稳定2.4分治法的应用2.4分治法的应用

给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素例7元素选择问题快速排序中的划分intpartition(inta[],intp,intr){pivot=a[p];low=p;high=r;while(low<high){

while(low<high&&a[high]>=pivot)--high;a[low]=a[high];

while(low<high&&a[low]<=pivot);

++low;

a[high]=a[low];}a[low]=pivot;returnlow;}随机划分：intrandomizedPartition(inta[],intp,intr){i=random(p,r);swap(a[i],a[p]);

return

partition(a,p,r);}快速排序中的划分(续)元素选择给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素randomizedSelect(inta[],intp,intr,intk){//在a[p..r]中找第k小的元素

if(p==r)returna[p];i=randomizedpartition(p,r),j=i-p+1;

if(k<=j)return

randomizedSelect(a,p,i,k);

else

return

randomizedSelect(a,i+1,r,k-j);}调用randomizedSelect(a,0,n-1,k)即可求得数组a中的第k小元素2.8分治法求最大、最小问题[金块问题]一老板有一袋金块，每月两名雇员因成绩优异被奖励，排名第一的雇员得最重的金块，排名第二的雇员得到最轻的金块。如有新的金块周