(XXXX0518版第二讲_分治策略-不可更改

——《算法分析与设计》1第2讲分治与递归策略2.1分治算法的基本思想2.2递归概念2.3典型分治算法举例——《算法分析与设计》2算法总体思想将一个难以直接解决的规模较大的问题分解为若干个规模较小的子问题，并各个击破，分而治之。n/16nn/4n/4n/4n/4n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16——《算法分析与设计》3将求出的较小规模的问题解合并成一个较大规模的问题解，并自底向上地求出原问题的解。(1)1()()()1nTnaTnbfnn最顶层问题a为分解的子问题数量；n/b为每个子问题的数据规模；f(n)为合并子问题解所消耗的时间。——《算法分析与设计》42.1分治算法的基本思想分治算法的基本思想是将一个规模为n的问题分解为a个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。——《算法分析与设计》5分治算法所能解决问题一般具有以下几个特征：缩小问题规模可以降低解决问题的难度；可以将子问题的解合并为原问题解；问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。——《算法分析与设计》6分治算法的算法框架divide-and-conquer(P){if(|P|=n0)adhoc(P);//解决规模小的问题//将问题P分解为子问题P1,P2,...,Pa；for(i=1,i=a,i++)yi=divide-and-conquer(Pi);//递归的求解各子问题returnmerge(y1,...,ya);//合并为原问题的解}——《算法分析与设计》7一个分治算法将规模为n的问题分成a个规模为n／b的子问题。设分解阈值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为a个子问题以及用merge将a个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治算法解规模为|P|=n的问题所需的计算时间，则有下列递归方程：(1)1()()()1OnTnaTnbfnn通过求解递归方程得到递归算法的时间复杂性。分治算法的复杂性分析——《算法分析与设计》8替换方法递归树方法公式法求解递归方程的三种方法：——《算法分析与设计》9替换方法替换方法的主要思想是首先推测出递归方程的解，然后代入递归方程，查看是否满足条件。适用比较容易猜出递归解的情形。①猜测出递归解的形式②用数学归纳法找出使解真正有效的常数替换方法解递归方程的基本步骤：——《算法分析与设计》10例：T(n)=2T(n/2)+n（2路归并)假设解对n/2成立，即T(n/2)≤c(n/2)lg(n/2)将其对递归方程进行替换，得：T(n)=2T(n/2)+n≤2(c(n/2)lg(n/2))+n≤cnlg(n/2)+n≤cnlgn-cnlg2+n=cnlgn-cn+n当c≥1时，显然cnlgn-cn+n≤cnlgn根据O符号定义，证明猜测正确。数学归纳法：l猜测出解为T(n)=O(nlgn)l证明存在某个常数c，使得T(n)≤cnlgn——《算法分析与设计》11递归树方法构造递归树的方法就是展开递归方程，然后将树中每层的时间求和，最终获得算法的时间复杂性。用递归树方法求解递归方程的基本步骤:递归树可以方便地推测递归方程的解，是描述分治算法的运行时间复杂性的有效手段。①利用递归树推测出一个解②利用替换方法进行证明——《算法分析与设计》12例：T(n)=3T(n/4)+cn2T(n)→——《算法分析与设计》13log4n+1nlog43O(nlog43)——《算法分析与设计》现在，我们来计算一下，有多少个叶节点。第1层有3个节点，第2层有32个节点，依次类推，第k层有3k个节点，当k=log4n，即为叶节点，因此，叶节点的个数为，而每个叶节点需要的时间为T(1),因此，整个叶节点的时间为。14递归树总共有多少层？当递归树展开一层，其规模为n/4，当递归树展开到第2层时，其规模为n/16=n/42，依次类推，当展开到第k层时，其规模为n/4k=1时，不再展开，由此可以求得递归树的层数为k=log4n。3lognlog443n)1(n3log4T——《算法分析与设计》15将递归树每一层的时间累加，可得：)(16316311163163)(23log23log23log23log21log044444nOncnncnncnncnnTiinii=0所以，由递归树猜测T(n)=O(n2)随后，再利用数学归纳法证明。——《算法分析与设计》16其中，a≥1，b1是常数，f(n)是一个渐进函数，描述划分问题与合并解的时间复杂性。n/b可以是，也可以是(1)1()()()1OnTnaTnbfnnbn/bn/公式法上述方程描述了如下算法的运行时间：将一个规模为n的问题划分为a个规模为n/b的子问题，其中a和b为正常数。分别递归地解决a个子问题，解每个子问题所需时间为T(n/b)。划分原问题和合并子问题的解所需要的时间由f(n)决定——《算法分析与设计》17定理：上述递归方程含有三种情形的渐进界：（1）对于某个常数如果则（2）如果则（3）对某个常数如果且对某个常数c1以及任意足够大的n,有af(n/b)≤cf(n),则0)()(lognabOnf)()(lognabnT)()(lognabnf)lg()(lognnTnab))(()(nfnT0)log()(annfb——《算法分析与设计》18定理含义将f(n)与进行比较，当较大时，相等时当较小时，)()(lognabnT)lg()(lognnTnab))(()(nfnT结论：可以通过尽量减少子问题的个数或者减少f(n)的数量级来增强分治算法的有效性。从定理中可以看出，公式法只要记住三种情形，就可以很容易地确定许多递归方程的解。nablognablognablog——《算法分析与设计》19例1：T(n)=9T(n/3)+n由上式可知，a=9，b=3，f(n)=n,且又因为对于有满足定理（1），因此，)(229loglog3nOnnnab1)()(9log3nOnf)()(2nnT——《算法分析与设计》20例2：T(n)=T(2n/3)+1由上式可知a=1,b=3/2,f(n)=1，且又因为满足定理（2），因此)(lg)(nnT——《算法分析与设计》212.2递归概念分治算法递归技术直接或间接地调用自身的算法称为递归算法。在定义函数时调用到函数自身称为递归函数。分治算法递归技术分治与递归像一对孪生兄弟分治算法的特征：将较大规模的问题分解为若干个较小规模的子问题，每个子问题的求解过程与原问题一样，并利用自底向上的求解策略得到最终的解。——《算法分析与设计》22递归应用举例1:Fibonacci数列10()11(1)(2)1nFnnFnFnn边界条件递归方程边界条件与递归方程是递归函数的二要素。无穷2阶数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。递归定义为：——《算法分析与设计》23A(1,0)=2A(0,m)=1m≥0A(n,0)=n+2n≥2A(n,m)=A(A(n-1,m),m-1)n,m≥1递归应用举例2:Ackerman函数——《算法分析与设计》24m=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，A(1,2)=A(A(0,2),1)=A(1,1)=2可以得出A(n,2)=2n。m=3时，类似的可以推出A(1,0)=2A(0,m)=1m≥0A(n,0)=n+2n≥2A(n,m)=A(A(n-1,m),m-1)n,m≥1Ackerman函数的特征：A(n，m)的自变量m的每一个值都定义了一个单变量函数。m=0时，A(n,0)=n+2m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，A(1,1)=2可以得出A(n,1)=2*n——《算法分析与设计》25递归应用举例3:排列问题求解n个元素{r1,r2,…,rn}的全排列。n个元素的全排列有n!种可能。解题基本方法：（1）固定位置放元素（2）固定元素找位置——《算法分析与设计》26假设R={r1,r2,…,rn}是待排列的n个元素，Ri=R-{ri}。假设集合Ri中元素的全排列记为perm(Ri)。(ri)perm(Ri)表示在全排列perm(Ri)的每一个排列的第一个位置加前缀ri得到的排列。当n=1时，perm(R)=(r)其中r是集合R中唯一的元素；当n1时，perm(R)的全排列为：(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)方法1：固定位置找元素——《算法分析与设计》27递归公式——《算法分析与设计》28——《算法分析与设计》29将每个元素交换到固定位置上，并求解其余位置元素的全排列。举例，0~3共4个数值的全排列思路？——《算法分析与设计》30假设:要求P[m]、P[m+1]、…P[n]的全排列:5.值得注意的是，将P[m]和某个P[k]交换，求出剩余元素的所有排列后，为了避免重复，发生混乱，必须将P[m]和P[k]交换回去，然后才能继续P[m]和P[K+1]的交换。4.当问题规模降为求一个元素P[m]的全排列时，问题就极为简单，可作为递归出口。3.然后依次考虑P[m+3]，…,P[n]。2.然后考虑P[m+1]，通过交换P[m]和P[m+1]，这样我们仍然只要考虑求剩余元素P[m+1]、P[m+2],…P[n]的所有排列即可。1.需要先考虑P[m]，如果能够求出剩余元P[m+1]、P[m+2]、…，P[n]的所有排列，我们只需将P[m]放到每个排列的开头。——《算法分析与设计》31——《算法分析与设计》32voidperm(int[]r,inti,intn){//r存放R集合元素，r[0]~r[n]//i,n表示目前求解的全排列起始与终止位置if（只有一个元素）{//递归边界条件显示当前排列；}else{依次将i~n之间的每个元素交换//递归到第i个位置，并用同样的方法（递归）求解i+1~n之间的全排列}}——《算法分析与设计》33voidperm(intr[],inti,intn){if(i==n){//只有一个数值for(intj=0;j=n;j++){//输出结果coutr[j];}coutendl;}else{for(intj=i;j=n;j++){swap(r,i,j);//交换r[i]与r[j]perm(r,i+1,n);//计