计算机算法导论_第4章

《计算机算法导论_第4章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoAlgorithms计算机算法导论2007~2008年第一学期HomeworkExercises3.2-4;3.2-7Problems3-4RecurrencesRecurrencesThreemethodsforsolvingrecurrencesSubstitutionmethodRecursion-treemethodMastermethodRecurrencesExampleSolvingrecurrencesTheanalysisofmergesortfromLec

2、ture1requiredustosolvearecurrence.Recurrencesarelikesolvingintegrals,differentialequations,etc.Lecture2:Applicationsofrecurrencestodivide-and-conqueralgorithms.TechnicalitiesAssumptionofintegerargumentsoffunctionsBoundaryconditionsFloorsandceils4.1Thesub

3、stitutionmethodSubstitutionmethodThemostgeneralmethod:1.Guesstheformofthesolution.2.Useinductiontofindtheconstantsandshowthatthesolutionworks.SubstitutionmethodGuess:T(n)=nlgn+nSubstitutionmethodMakingagoodguessT(n)=2T(n/2+17)+nSimilarsolutionisreasonabl

4、eProvelooseupperandlowerboundsandreducetherangeofuncertaintySubtletiesT(n)=2T(n/2)+1AvoidingpitfallsT(n)≦2c(n/2)+n=cn+n=O(n)Wrong!!!!ChangingvariablesAnexampleAnexampleAnexample4.2Therecursion-treemethodAnexampleT(n)=T(n/3)+T(2n/3)+Θ(n)AnexampleT(n)=T(n/

5、3)+T(2n/3)+Θ(n)AnexampleT(n)=T(n/3)+T(2n/3)+Θ(n)AnexampleT(n)=T(n/3)+T(2n/3)+Θ(n)4.3ThemastermethodHomeworkExercises4.1-2;4.1-54.2-44.3-1;4.3-2Problems4-1;4-4