分治与递归策略课件.ppt

《分治与递归策略课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、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/163将求出的较小规模的问题解合并成一个较大规模的问题解，并自底向上地求出原问题的解。最顶层问题a为分解的子问题数量；n/b为每个子问题的数据规模；f(n)为合并子问题解所消耗的时间。42.1分治算法的基本思想分治算法的基本思想是将一个规模为n的问题分

2、解为a个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。5分治算法所能解决问题一般具有以下几个特征：缩小问题规模可以降低解决问题的难度；可以将子问题的解合并为原问题解；问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。6分治算法的算法框架divide-and-conquer(P){if(

3、P

4、<=n0)adhoc(P);//解决规模小的问题//将问题P分解为子问题P1,P2,...,Pa；for(i=1,i<=a,i++)yi=divide-and-conquer(Pi);//递归的求解各子问题r

5、eturnmerge(y1,...,ya);//合并为原问题的解}7一个分治算法将规模为n的问题分成a个规模为n／b的子问题。设分解阈值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为a个子问题以及用merge将a个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治算法解规模为

6、P

7、=n的问题所需的计算时间，则有下列递归方程：通过求解递归方程得到递归算法的时间复杂性。分治算法的复杂性分析8替换方法递归树方法公式法求解递归方程的三种方法：9替换方法替换方法的主要思想是首先推测出递归方程的解，然后代入递归方程，查看是否满足条件。适用比较

8、容易猜出递归解的情形。①猜测出递归解的形式②用数学归纳法找出使解真正有效的常数替换方法解递归方程的基本步骤：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符号定义，证明猜测正确。数学归纳法：猜测出解为T(n)=O(nlgn)证明存在某个常数c，使得T(n)≤cnlgn11递归树方法构造递归树的方法

9、就是展开递归方程，然后将树中每层的时间求和，最终获得算法的时间复杂性。用递归树方法求解递归方程的基本步骤:递归树可以方便地推测递归方程的解，是描述分治算法的运行时间复杂性的有效手段。①利用递归树推测出一个解②利用替换方法进行证明12例：T(n)=3T(n/4)+cn2T(n)→13log4n+1nlog43O(nlog43)现在，我们来计算一下，有多少个叶节点。第1层有3个节点，第2层有32个节点，依次类推，第k层有3k个节点，当k=log4n，即为叶节点，因此，叶节点的个数为，而每个叶节点需要的时间为T(1),因此，整个叶节点的时间为。14递归树总共有多少层？当递归树展开一层

10、，其规模为n/4，当递归树展开到第2层时，其规模为n/16=n/42，依次类推，当展开到第k层时，其规模为n/4k=1时，不再展开，由此可以求得递归树的层数为k=log4n。15将递归树每一层的时间累加，可得：i=0所以，由递归树猜测T(n)=O(n2)随后，再利用数学归纳法证明。16其中，a≥1，b>1是常数，f(n)是一个渐进函数，描述划分问题与合并解的时间复杂性。n/b可以是，也可以是公式法上述方程描述了如下算法的运行时间：将一个规模为n的问题划分为a个规模为n/b的子问题，其中a和b为正常数。分别递归地解决a个子问题，解每个子问题所需时间为T(n/b)。划分原问题和合并

11、子问题的解所需要的时间由f(n)决定17定理：上述递归方程含有三种情形的渐进界：（1）对于某个常数如果则（2）如果则（3）对某个常数如果且对某个常数c<1以及任意足够大的n,有af(n/b)≤cf(n),则18定理含义将f(n)与进行比较，当较大时，相等时当较小时，结论：可以通过尽量减少子问题的个数或者减少f(n)的数量级来增强分治算法的有效性。从定理中可以看出，公式法只要记住三种情形，就可以很容易地确定许多递归方程的解。19例1：T(n)=9T(n/3)+n由上式可知，a=9，b=3，f(