算法設(shè)計(jì)與分析遞歸式

算法設(shè)計(jì)與分析遞歸式第一頁(yè)，共二十五頁(yè)，2022年，8月28日第四章遞歸式4.1假設(shè)歸納法4.2迭代方法4.3主方法第二頁(yè)，共二十五頁(yè)，2022年，8月28日概念及求解方法概念：T(n)=f(T(g(n)))(一般g(n)<n)三種求解方法假設(shè)歸納法迭代方法主方法求解方式—忽略細(xì)節(jié)假定式中n為整數(shù)（略去底、頂函數(shù)）假定對(duì)小的n值T(n)為常量（略去邊界條件）求解后再檢查這些忽略的細(xì)節(jié)是否會(huì)影響結(jié)果第三頁(yè)，共二十五頁(yè)，2022年，8月28日4.1假設(shè)歸納法先猜測(cè)解的形式，再用歸納法證明。猜測(cè)技巧：類(lèi)比猜測(cè)如：T(n)=2T(n/2+17)+n逐步求精猜測(cè)O(1)<O(lgn)<O(n)<O(nlgn)<O(n2)<O(2n)第四頁(yè)，共二十五頁(yè)，2022年，8月28日4.1假設(shè)歸納法歸納法證明時(shí)的技巧：根據(jù)界的形式定義，邊界條件n0可選大一點(diǎn)的值。例：求T(n)=2T(n/2)+n的界猜測(cè)為O(nlgn)，即證明存在c>0的常數(shù)，滿(mǎn)足T(n)≤cnlgn。證明：設(shè)對(duì)n/2滿(mǎn)足，則T(n)≤2(cn/21g(n/2))+n≤cnlg(n/2)+n=cnlgn-cnlg2+n=cnlgn-cn+n≤cnlgn,只需c≥1

即可。但該解對(duì)邊界條件T(1)=1不成立，但可選n0=2第五頁(yè)，共二十五頁(yè)，2022年，8月28日4.1假設(shè)歸納法歸納法證明時(shí)的技巧（續(xù)）：解中減一個(gè)低階項(xiàng)（做一個(gè)更強(qiáng)的假設(shè)）。例：求T(n)=T(n/2)+T(n/2)+1的界猜測(cè)為O(n)，即證明存在c>0的常數(shù)，滿(mǎn)足T(n)≤cn。證明：設(shè)對(duì)n/2滿(mǎn)足，則T(n)≤cn/2+cn/2+1=cn+1得不到滿(mǎn)足條件的c。但猜測(cè)為T(mén)(n)≤cn–b，有T(n)≤(cn/2-b)+(cn/2-b)+1=cn-2b+1≤cn-b(只要b≥1)對(duì)小的值作更強(qiáng)的假設(shè)，可證明給定值更強(qiáng)的結(jié)論第六頁(yè)，共二十五頁(yè)，2022年，8月28日4.1假設(shè)歸納法歸納法證明時(shí)的技巧（續(xù)）：變量代換。例：變量代換：m=1gn，得：

T(2m)=2T(2m/2)+m再次變量代換：S(m)=T(2m)，得： S(m)=2S(m/2)+m則得S(m)=O(mlgm)得：T(n)=T(2m)=S(m)=O(mlgm)=O(lgnlglgn).第七頁(yè)，共二十五頁(yè)，2022年，8月28日4.1假設(shè)歸納法避免陷阱：例：T(n)≤2(cn/2)+n ≤cn+n =O(n)--錯(cuò)誤此處未證明歸納假設(shè)的準(zhǔn)確形式：T(n)≤cn第八頁(yè)，共二十五頁(yè)，2022年，8月28日4.2迭代方法擴(kuò)展遞歸式，然后進(jìn)行和式求解(計(jì)算復(fù)雜)。例：T(n)=3T(n/4)+n.T(n)=n+3T(n/4)=n+3(n/4+3T(n/16))=n+3(n/4+3(n/16+3T(n/64)))=n+3n/4+9n/16+27T(n/64)當(dāng)n/4i=1即i超過(guò)log4n時(shí)，擴(kuò)展達(dá)到邊界。故：第九頁(yè)，共二十五頁(yè)，2022年，8月28日4.2迭代方法要點(diǎn)：什么時(shí)候達(dá)到邊界;迭代過(guò)程的每一層中各項(xiàng)的和;若迭代過(guò)程中已能估計(jì)出界的形式，則可以改用假設(shè)歸納法。第十頁(yè)，共二十五頁(yè)，2022年，8月28日4.2迭代方法圖解法—遞歸樹(shù)：例：T(n)=2T(n/2)+n2第十一頁(yè)，共二十五頁(yè)，2022年，8月28日4.2迭代方法圖解法—遞歸樹(shù)：例：T(n)=2T(n/2)+n2（續(xù)）

第十二頁(yè)，共二十五頁(yè)，2022年，8月28日4.2迭代方法圖解法—遞歸樹(shù)：例2：T(n)=T(n/3)+T(2n/3)+n第十三頁(yè)，共二十五頁(yè)，2022年，8月28日4.3主方法用于解如下形式的遞歸式： T(n)=aT(n/b)+f(n) 其中a≥1，b>1是常數(shù)，f(n)是一個(gè)漸近正函數(shù)。 （式中使用頂、底函數(shù)并不影響結(jié)果）第十四頁(yè)，共二十五頁(yè)，2022年，8月28日4.3主方法主定理： 設(shè)a≥1和b>1是常數(shù)，f(n)為一函數(shù)，T(n)是由下面的遞歸式定義： T(n)=aT(n/b)+f(n)(n/b指n/b或n/b)。 則T(n)可有如下漸近界：若對(duì)某常數(shù)>0，有f(n)=，則有T(n)=；若f(n)=，則T(n)=；若對(duì)某常量，有f(n)=，且對(duì)常量c<1與足夠大的n，有af(n/b)≤cf(n)，則T(n)=(f(n))。第十五頁(yè)，共二十五頁(yè)，2022年，8月28日4.3主方法主定理解讀第十六頁(yè)，共二十五頁(yè)，2022年，8月28日4.3主方法主定理解讀（續(xù)）：界由f(n)和中大的那個(gè)決定；第一種情況為：f(n)多項(xiàng)式小于時(shí)，解為第三種情況為：f(n)多項(xiàng)式大于，并滿(mǎn)足條件af(n/b)≤cf(n)時(shí)，解為(f(n))第二種情況為：兩者漸近相等時(shí)，解為第十七頁(yè)，共二十五頁(yè)，2022年，8月28日4.3主方法主定理應(yīng)用：例1：T(n)=9T(n/3)+n其中a=9，b=3，f(n)=n，則因?yàn)閒(n)=，其中=1。這對(duì)應(yīng)于主定理的第一種情況，故解為：T(n)=(n2)例2：T(n)=T(2n/3)+1其中a=1，b=3/2，f(n)=1，則即滿(mǎn)足第二種情況，故解為：T(n)=(lgn)第十八頁(yè)，共二十五頁(yè)，2022年，8月28日4.3主方法主定理應(yīng)用(續(xù))：例3：T(n)=3T(n/4)+nlgn其中a=3，b=4，f(n)=nlgn，則因?yàn)閒(n)=，其中≈0.2。若證明條件af(n/b)≤cf(n)，則該問(wèn)題對(duì)應(yīng)于主定理的第三種情況。對(duì)足夠大的n，af(n/b)=3(n/4)lg(n/4)≤(3/4)nlgn=cf(n)，即c=3/4。故解為：T(n)=(nlgn)例4：T(n)=2T(n/2)+n1gn其中a=2，b=2，f(n)=n1gn，看似滿(mǎn)足第三種情況，但f(n)=n1gn漸近大于，不是多項(xiàng)式大于(對(duì)任意正常數(shù)，比值=(nlgn)/n=lgn漸近小于n)第十九頁(yè)，共二十五頁(yè)，2022年，8月28日4.3主方法主定理證明第二十頁(yè)，共二十五頁(yè)，2022年，8月28日4.3主方法主定理證明（情況一）f(n)=，有則：第二十一頁(yè)，共二十五頁(yè)，2022年，8月28日4.3主方法主定理證明（情況二）f(n)=，有則：第二十二頁(yè)，共二十五頁(yè)，2022年，8月28日4.3主方法主定理證明（情況三）af(n/b)≤cf(n)，有ajf(n/bj)≤cjf(n)，則：