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

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

即可。但該解對邊界條件T(1)=1不成立，但可選n0=2第五頁，共二十五頁，編輯于2023年，星期三4.1假設(shè)歸納法歸納法證明時的技巧（續(xù)）：解中減一個低階項（做一個更強的假設(shè)）。例：求T(n)=T(n/2)+T(n/2)+1的界猜測為O(n)，即證明存在c>0的常數(shù)，滿足T(n)≤cn。證明：設(shè)對n/2滿足，則T(n)≤cn/2+cn/2+1=cn+1得不到滿足條件的c。但猜測為T(n)≤cn–b，有T(n)≤(cn/2-b)+(cn/2-b)+1=cn-2b+1≤cn-b(只要b≥1)對小的值作更強的假設(shè)，可證明給定值更強的結(jié)論第六頁，共二十五頁，編輯于2023年，星期三4.1假設(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).第七頁，共二十五頁，編輯于2023年，星期三4.1假設(shè)歸納法避免陷阱：例：T(n)≤2(cn/2)+n ≤cn+n =O(n)--錯誤此處未證明歸納假設(shè)的準(zhǔn)確形式：T(n)≤cn第八頁，共二十五頁，編輯于2023年，星期三4.2迭代方法擴展遞歸式，然后進行和式求解(計算復(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超過log4n時，擴展達到邊界。故：第九頁，共二十五頁，編輯于2023年，星期三4.2迭代方法要點：什么時候達到邊界;迭代過程的每一層中各項的和;若迭代過程中已能估計出界的形式，則可以改用假設(shè)歸納法。第十頁，共二十五頁，編輯于2023年，星期三4.2迭代方法圖解法—遞歸樹：例：T(n)=2T(n/2)+n2第十一頁，共二十五頁，編輯于2023年，星期三4.2迭代方法圖解法—遞歸樹：例：T(n)=2T(n/2)+n2（續(xù)）

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