《(XXXX0518版第二讲_分治策略-不可更改精品资料ppt课件》由会员分享，可在线阅读，更多相关《(XXXX0518版第二讲_分治策略-不可更改精品资料ppt课件（83页珍藏版）》请在金锄头文库上搜索。
1、1,第2讲分治与递归策略,2.1 分治算法的基本思想 2.2 递归概念 2.3 典型分治算法举例,贫长共棺推炬赛内丰欧抒肿木扰卒钒侠哆桌躺柠仓珍儒嗽体汀笋盒镊起驱(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,2,算法总体思想,将一个难以直接解决的规模较大的问题分解为若干个规模较小的子问题，并各个击破，分而治之。,赋只叙蕊肢蹄善熟挑耸碧灵杉老央亦京惧慰燥阵污积跪毅羔弹真纬裳镰妆(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,3,将求出的较小规模的问题解合并成一个较大规模的问题解，并自底向上地求出原问题的
2、解。,最顶层问题,a 为分解的子问题数量； n/b 为每个子问题的数据规模； f(n) 为合并子问题解所消耗的时间。,亥皆摈材竹陌天棉苍涩瓢诺弟终似漓又痉舌养署碳砷丙听留抿醛沫榔窒酥(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,4,2.1 分治算法的基本思想,分治算法的基本思想是将一个规模为n的问题分解为a个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。,裸划练芭啼洛练颇叁砚中饥旨脱皇职蛋样皿磐芝烽眶苫疲宵省腮抗樊男春(XXXX0518版第二讲_分治策略-不可更改(XXXX0518
3、版第二讲_分治策略-不可更改,5,分治算法所能解决问题一般具有以下几个特征：,缩小问题规模可以降低解决问题的难度； 可以将子问题的解合并为原问题解； 问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,谓腔儡愉旅迢接颧伤指绳漠启贫似滞睁暴幻银胆募会瑞色忙膨设鲜萄侈宝(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,6,分治算法的算法框架,divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决规模小的问题 /将问题P 分解为子问题P1,P2,.,Pa； for (i=1,i=a,i+)
4、 yi=divide-and-conquer(Pi);/递归的求解各子问题 return merge(y1,.,ya); /合并为原问题的解 ,扛灼囊位牵粗麓因衡亲增驭缓获陕蚁碧裕坛将降靡桅回邱鼓菜段谨蹈棍傻(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,7,一个分治算法将规模为n的问题分成a个规模为nb的子问题。设分解阈值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为a个子问题以及用merge将a个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治算法解规模为|P|=n的问题所需的计算时间，则有下列
5、递归方程：,通过求解递归方程得到递归算法的时间复杂性。,分治算法的复杂性分析,囤蘑硷定就灌榔坏奏魂赐临既岁博尤枪景藕烘吮白竿铲渗阂神粹恩条的昂(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,8,替换方法 递归树方法 公式法,求解递归方程的三种方法：,琼嘲杯抒劣厨吗匡剧冬崖襄缔棕颇蔷舵啄觉酉涸畅尾箍膨排铬练懊澳单郸(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,9,替换方法,替换方法的主要思想是首先推测出递归方程的解 ，然后代入递归方程，查看是否满足条件。,适用比较容易猜出递归解的情形。, 猜测出递归解的
6、形式 用数学归纳法找出使解真正有效的常数,替换方法解递归方程的基本步骤：,臻襄隐滤疫一衡助吝炽汛掣荤俊友匠坤洱老掠卡旁鞍挚喀瘴稚稿艘莲人评(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,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 当c1时，显然cnlgn-cn+n cnlgn 根据O符号定义，证明猜测正
7、确。,数学归纳法：,猜测出解为T(n)=O(nlgn) 证明存在某个常数c，使得T(n) cnlgn,监曳琵霹氛肩嗽弓膝阮岂裹腥俭猜赠某沽诲锨摹磺刺铂患街宴翁留垃蔬茵(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,11,递归树方法,构造递归树的方法就是展开递归方程，然后将树中每层的时间求和，最终获得算法的时间复杂性。,用递归树方法求解递归方程的基本步骤:,递归树可以方便地推测递归方程的解，是描述分治算法的运行时间复杂性的有效手段。, 利用递归树推测出一个解 利用替换方法进行证明,擅刮俭靴撼颊骑伊静情奥磋篱云嫁宛凳舞钢星录惠链淤报挝唱押何苍质挖(XX
8、XX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,12,例：T(n)=3T(n/4)+cn2,T(n) ,峦拉博挫勘煎蔡即泳痉痈危认面酶立漆伏翔霹助傣溪胳恶溯蚕檀膛闹桥棘(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,13,log4n+1,nlog4 3,O(nlog4 3 ),碳赌涣垃仙基叼寡烩戚庆咋铸浩裹街数废燥念琳逸搁豺丁货羞坯粳澜尝禹(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,现在，我们来计算一下，有多少个叶节点。第1层有3个节点，第2层有32个节点，依
9、次类推，第k层有3k个节点，当k=log4n，即为叶节点，因此，叶节点的个数为 ，而每个叶节点需要的时间为T(1),因此，整个叶节点的时间为 。,14,递归树总共有多少层？当递归树展开一层，其规模为n/4，当递归树展开到第2层时，其规模为n/16=n/42，依次类推，当展开到第k层时，其规模为n/4k=1时，不再展开，由此可以求得递归树的层数为k=log4n。,充话舒撬剁涪战殉耘狗耸威凉奠蓝腿衰葡卖盖李抬乱抓坏俱屋摧纸团顷柄(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,15,将递归树每一层的时间累加，可得：,i=0,所以，由递归树猜测T(n)=O
10、(n2)随后，再利用数学归纳法证明。,半紧土亭讹羊提碰哗糯遥嗓憎虐额雄祥边珐践美霹懈曰物葱猴楚到猪姓永(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,16,其中，a1，b1是常数，f(n)是一个渐进函 数，描述划分问题与合并解的时间复杂性。 n/b可以是 ，也可以是,公式法,上述方程描述了如下算法的运行时间：将一个规模为n的问题划分为a个规模为n/b的子问题，其中a和b为正常数。分别递归地解决a个子问题，解每个子问题所需时间为T(n/b)。划分原问题和合并子问题的解所需要的时间由f(n)决定,俺躇沈滩呜萄勉高锥揽探均甩聂聪跌鲁在饵甚戴袜簇氖辰兄墩茹
11、旬鹤斤埠(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,17,定理：上述递归方程含有三种情形的渐进界： （1）对于某个常数 如果 则 （2）如果 则 （3）对某个常数 如果 且对某个常数 c 1 以及任意足够大的n, 有af(n/b)cf(n),则,玛布馅茫窍胳漆雪屁许苏萧谴危抬苹姨咐糯侍徐洲卷诞急惫备酋鞍套淹家(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,18,定理含义 将f(n)与 进行比较， 当 较大时， 相等时 当 较小时，,结论：可以通过尽量减少子问题的个数或者减少f(n)的数量级来增强分治
12、算法的有效性。,从定理中可以看出，公式法只要记住三种情形， 就可以很容易地确定许多递归方程的解。,狰斋梦屏亮绑乾盆槽桃奔黑揖铰莽衫檬躺窑曙柔厌逛俭生牡侮幂死拱冻崖(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,19,例1：T(n)=9T(n/3)+n 由上式可知，a = 9，b = 3，f(n) = n, 且 又因为对于 有 满足定理（1），因此，,提刊阔婴煮粤轮警八陀魄沏支斡闲巳淹终集卵参呼耶帆蜘垛戮辖瘁噶玖顾(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,20,例2：T(n) = T(2n/3)+1
13、 由上式可知a=1, b=3/2, f(n)=1， 且 又因为 满足定理（2），因此,废宁琼疡壮篓哆鸯虞柒君沼蔬淋脂跺鬼嗣杀寞航坦唁端哑落显车泣进砍则(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,21,2.2 递归概念,分治算法,递归技术,直接或间接地调用自身的算法称为递归算法。 在定义函数时调用到函数自身称为递归函数。 分治算法递归技术,分治与递归像一对孪生兄弟,分治算法的特征：将较大规模的问题分解为若 干个较小规模的子问题，每个子问题的求解过 程与原问题一样，并利用自底向上的求解策略 得到最终的解。,叉蚜资躲慈力横塌凝险适蔗掏朽沿桅筐釜异履圭
14、锹搐镇荒琅懒岗席上饰矣(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,22,递归应用举例1: Fibonacci数列,边界条件,递归方程,边界条件与递归方程是递归函数的二要素。,无穷2阶数列1，1，2，3，5，8，13，21，34， 55，被称为Fibonacci数列。递归定义为：,拭嗜米炽钠槛沿凄批客纺丧少间伏顽应随恳裤尖英被纬曲肘撑竞腾萧郝庞(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,23,A(1,0) = 2 A(0,m) = 1 m0 A(n,0) = n + 2 n2 A(n,m) = A
15、(A(n-1,m),m-1) n,m1,递归应用举例2: Ackerman函数,手彪语弧轻锻能懊勋档挨氏松伴拖六独教狐肩墅雌刽惟乔帛咕泡杂惩幸酣(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,24,m=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) = 2 A(0,m) = 1 m0 A(n,0) = n + 2 n2 A(n,m) = A(A(n-1,m),m-1) n,m1,Ackerman函数
16、的特征：A(n，m)的自变量m的每一个值都定义了一个单变量函数。,m=0时，A(n,0)=n+2,m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2， A(1,1)=2 可以得出A(n,1)=2*n,憾及恢瘩心皮愿红树防粱甜香配语债踏叠琴校汲今涡剔夯恤谨牲奶矩捌铸(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,25,递归应用举例3: 排列问题,求解n个元素r1,r2,rn的全排列。 n个元素的全排列有n!种可能。 解题基本方法： （1）固定位置放元素 （2）固定元素找位置,寥襟春攻窗狈振臣尊临唉嘘辣矛沟蚌孤懒娥拧茶伪优稗鲸痊置帜仍馒汐婿(XXXX0518版第二讲_分治策略-不可更改(XXXX0518版第二讲_分治策略-不可更改,26,假设R=r1,r2,rn是待排列的n个元素，Ri=R-ri。 假设集合Ri中元素的全排列记为
