算法导论 第四章 递归

Recurrence（递归）（一种算法分析技术）主要内容•Substitutionmethod替换法•Recursion-treemethod递归树•Mastermethod主方法Solvingrecurrences解递归式•TheanalysisofMergesortrequiredustosolvearecurrence需要解递归式•Recurrencesareamajortoolforanalysisofalgorithms三种解递归式的方法•Substitutionmethod•Recursion-treemethod•Mastermethod•DivideandConqueralgorithmswhichareanalyzablebyrecurrences处理技巧Technicality在求解递归方程时，通常会忽略一些技术细节，比如，假定自变量是整数，忽略上下取整符号通常会忽略递归方程的边界条件，对于足够小的n，将T(n)作是一个常数，令T(n)=Θ（1）在有些特殊情况下，技术细节非常重要，需要重视上下取整符合和边界条件，期望得到更好的结论Substitutionmethod替换法•Themostgeneralmethod:--Guesstheformofthesolution猜测解的形式--Verifybyinduction数学归纳法证明--Solveforconstants解出常数c,n0•ExampleT(n)=4T(n/2)+100n--AssumethatT(1)=Θ(1)--GuessO(n3)--AssumethatT(k)≤ck3forkn--ProveT(n)≤cn3byinductionExampleofsubstitution•T(n)=4T(n/2)+100n≤4c(n/2)3+100n=(c/2)n3+100n=cn3–((c/2)n3–100n)≤cn3•Whenever(c/2)n3–100n≥0,forexample,ifc≥200andn≥1desired-residualdesiredresidualMakeagoodguessExampleofsubstitution最后一步只需要c≥1时就成立--ConsiderT(n)=2T()+nn(0)0,(1)1(1)1lg10(2)2(1)242lg22,TTTcTTcc假定只要c2()lgAssumeTncnn如何获得好的猜测解熟能生巧，猜测需要经验通过构建递归树获得猜测解如果某个递归方程和以往的某方程相似，则有理由猜测其解也相似没有通用的有效方法获得递归方程正确的猜测解()2(/12)7TnTNn的上界O(nlgn)替代法中需要注意的问题Sometimes,youmakeacorrectguessofasymptoticboundonthesolutionofarecurrence,butthemathdoesn’tseemtoworkoutintheinduction有时，我们也许猜出递归式的正确渐进界，但却会在归纳证明时出现一些问题Usually,theproblemisthattheinductiveassumptionisn’tstrongenoughtoprovethedetailedbound归纳假设不够强，无法证明其准确的界替代法中需要注意的问题Whenyoufacesuchasituation,revisingtheguessbysubtractingalower-ordertermoftenpermitsthemathtogothrough通过去掉一个低阶项来修改所猜的界猜测解为T(n)=O(n)，在归纳推理时发现无法继续下去为了证明这一结论，我们修改原有结论，将其加强，T(n)≤cn-b,b0()/2/211TncncncnAvoidingPitfalls避免陷阱--Theerroristhatwehaven’tprovedtheexactformoftheinductivehypothesisT(n)≤cnc在随n变化，不对！•Becarefulnottomisuseasymptoticnotation.Forexample:--WecanfalselyproveT(n)=O(n)byguessingT(n)≤cnforT(n)=2T()+nT(n)≤2c+n≤cn+n=O(n)2/n2/nWrongChangingVariables改变变量•Usealgebraicmanipulationtomakeanunknownrecurrencesimilartowhatyouhaveseenbefore通对一个陌生的递归式作一些简单的代数变换变成我们熟悉的形式--ConsiderT(n)=2T()+lgn,n--Renamem=lgnandwehaveT(2m)=2T(2m/2)+m.--SetS(m)=T(2m)andwehaveS(m)=2S(m/2)+mS(m)=O(mlgm)--ChangingbackfromS(m)toT(n),wehaveT(n)=T(2m)=S(m)=O(mlgm)=O(lgnlglgn)Recursion-treemethod递归树•Arecursiontreemodelsthecosts(time)ofarecursiveexecutionofanalgorithm.递归树来模型化一个算法递归执行的代价•Therecursiontreemethodisgoodforgeneratingguessesforthesubstitutionmethod递归树有助于获得一个好的猜测，然后用替代法去证明•在递归树中，每个结点代表一个代价•递归树中每行节点的代价之和（每行代价）称为行和•对所有的行和求和，可得总的代价TheConstructionofaRecursionTree•SolveT(n)=3T(n/4)+Θ(n2),wehave•SolveT(n)=3T(n/4)+Θ(n2),wehaveTheConstructionofaRecursionTree•SolveT(n)=3T(n/4)+Θ(n2),wehaveTheConstructionofaRecursionTree•Thefullyexpandedtreehaslg4n+1levels,i.e.,ithasheightlg4nConstructionofRecursionTreelog4n+1cn22cn16322cn163)n(3log43lognlog44n3GeometricseriesTotal:O(n2)Example求解递归方程T(n)=T(n/4)+T(n/2)+n2递归树小结由于递归树方法通常用来获得好的猜测解，其解的正确性可以用替代法来证明。因此，在构造递归树时通常省略一些无关紧要的细节，例如上取整和下取整等如果在构造递归树以及求解和时就非常认真仔细，也可以直接用递归树方法来求解递归方程递归树小结在递归树方法中，关键是求出行和、总的代。为求得行和，一个有效的办法是根据递归方程本身，推导出下一行的和与上一行的和之间的关系，由此，可使得求和过程变得有章可循，从而也更为简单MasterMethod主方法•Itprovidesa“cookbook”methodforsolvingrecurrencesoftheform:解决如下形式的递归方程T(n)=aT(n/b)+f(n)a≥1andb1areconstantsf(n)isanasymptoticallypositivefunction渐进非负函数用n/b代替T(n)可以根据主定理来定界//nbnb或者Ideaofmastertheorem•Recursiontreea#leaves=ah=alogbn=nlogbaThreecommoncases•Comparef(n)withnlogba:--1.f(n)=O(nlogba-ε)forsomeconstantε0f(n)growspolynomiallyslowerthannlogba(byannεfactor)多项式小于--Solution:T(n)=Θ(nlogba)Ideaofmastertheorem•RecursiontreeCASE1:Theweightincreasesgeometricallyfromtheroottotheleaves.Theleavesholdaconstantfractionofthetotalweight.Threecommoncases•Comparef(n)withnlogba:--2.f(n)=Θ(nlogba)forsomeconstantk≥0f(n)andnlogbagrowatsimilarrates同样大--Solution:T(n)=Θ(nlogba)Ideaofmastertheorem•RecursiontreeCASE2:Theweightisapproximatelythesameoneachofthelogbnlevels.Threecommoncases•Comparef(n)withnlogba:--3.f(n)=Ω(nlogba+ε)forsomeconstantε0f(n)growspolynomiallyfasterthannlogba(byannεfactor)多项式大于--andf(n)satisfiestheregularityconditionthataf(n/b)≤cf(n)forsomeconstantc1--Solution:T(n)=Θ(f(n))Ideaofmastertheorem•RecursiontreeCASE3:Theweightdecreasesgeometricallyfromtheroottotheleaves.Therootholdsaconstantfractionofthetotalweight.ThreecommoncasesComparef(n)withnlogba:1.f(n)=O(nlogba-ε)forsomeconstantε0f(n)growspolynomiallyslowerthannlogba(byannεfactor),Solution:T(n)=Θ(nlogba)2.f(n)=Θ(nlogba)forsomeconstantk≥0f(n)andnlogbagrowatsimilarrates,Solution:T(n)=Θ(nlogbalgn)3.f(n)=Ω((nlogba+ε)forsomeconstantε0f(n)growspolynomiallyfasterthannlogba(byannεfactor),andf(n)satisfiestheregularityconditionthataf(n/b)≤cf(n)forsomeconstantc1Solution:T(n)=Θ(f(n))Mastertheorem-examplesT(n)=9T(n/3)+na=9,b=3,f(n)=nlogba=2,f(n)=O(nlogba–ε)whereε=1,case1T(n)=Θ(nlogba)=Θ(n2)T(n)=T(2n/3)+1a=1,b=3/2,f(n)=1logba=0,f(n)=Θ(nlogba),case2T(n)=Θ(nlogba)=Θ(lgn)T(n)=3T(n/4)+nlgna=3,b=4,f(n)=nlgnlogba=log43≈0.793,f(n)=Ω(nlogba+ε)whereε≈0.2af(n/b)=3f(n/4)=3(n/4)lg(n/4)≤(3/4)nlgn=cf(n)whe