《算法导论第四章递归ppt课件》由会员分享，可在线阅读，更多相关《算法导论第四章递归ppt课件（33页珍藏版）》请在金锄头文库上搜索。
1、矗Recurrence递归)一祈峡版孕形袁求/鹦“主要内容Substituti0nmeth0d替换法。Recursion-treemeth0d递归树.Mastermeth0d主方法Solvingrecurrences解递归式。TheanalysisofMergesortrequiredustosolveaTecurrence需要解递归式sRecurrencesareamajortoolforanalysisofalgorithms三种解递归式的方法*Substitutionmethod*Recursion-treemethod“Mastermethod。DivideandConqueralgo
2、rithmswhichareanalyzablebyTeCUIreniceS员。在节整通小s在要更处理技巧Technicality求解递归方程时,通常会忽略一些技术细,比如,假定自变量是整数,忽略上下取符号常会忽略递归方程的边界条件,对于足够的,将九刀作是一个常数,后7刀=9(1)有些特殊情况下,技术细节非常重要,需重视上下取整符合和边界条件,期望得到好的结论霾Substitutionmethod替换法Themostgeneralmethod:-Guesstheformofthesolution猜测解的形式-Verifybyinduction数学归纳法证明-Solveforconstants解
3、出常数c,o。ExampleTIj277h2+700D1-AssumethatT厂=8(1)-GuessO(ma)-AssumethatTfA)c3for一71-ProveT7fm)Scnibyinduction霾Exampleofsubstitution。T(n)=4T(n/2)+100n4c(n/2)3+100n=(c/2)n3+100n=cn3-(c/2)n3-100n)-一desired-residual0,forexample,ifC么200and之工residualMakeagoodguess霾Exampleofsubstitution-ConsiderT刀=2酉|)+nAhsgt
4、meT(10)三cnlgnTmJ2(cLa/2Jl8(Ln/21)Hn一cnlg(n/2)+n一cn18n-cn1g2+n二cn8-en+n1时就成立假定7(0)=0,.7(D=17(D5Sc.1.1g81=07(2)=27(D+2=42伟0们获得好的猜测解。熟能生巧,猜测需要经验。通过构建递归树获得猜测解。如果某个递归方程和以往的某方程相似,则有理由猜测其解也相似700=27(LN12|+17)+n的上界0lgn)。没有通用的有效方法获得递归方程正确的猜测解禹芸f法中需要注意的问题。Sometimes,youmakeacorrectguessofasymptoticboundonthesol
5、utionofarecurrence,butthemathdoesntseemtoworkoutintheinduction有时,我们也许猜出递归式的正确渐进界,但却会在归纳证明时出现一些问题s。Usually,theproblemisthattheinductiveassumptionisntstrongenoughtoprovethedetailedbound归纳假设不够强,无法证明其准确的界禹“芸f法中需要注意的问题。Whenyoufacesuchasituation,revisingtheguessbysubtractingalower-ordertermoftenpermitsthemathtogothrough通过去掉一个低阶项来修改所猜的界Z=Z(Lz/2卫+Z(z/2飞+1*猜测解为7刀=O(八,在归纳推理肖发现无法绍续下去7000Ta)(cln/21-bH(cn/21-bH1二cn-2b+1一cn-b
