lec3 Divide-and-Conquer Strassen, Fibonacci -- Polynomial Multiplicatio

《lec3 Divide-and-Conquer Strassen, Fibonacci -- Polynomial Multiplicatio》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、IntroductiontoAlgorithms6.046J/18.401JLECTURE3DivideandConquer•Binarysearch•Poweringanumber•Fibonaccinumbers•Matrixmultiplication•Strassen’salgorithm•VLSItreelayoutProf.ErikD.DemaineSeptember14,2005Copyright©2001-5ErikD.DemaineandCharlesE.LeisersonL2.1Thedivide-and-conquerdesignparadigm1.Divid

2、etheproblem(instance)intosubproblems.2.Conquerthesubproblemsbysolvingthemrecursively.3.Combinesubproblemsolutions.September14,2005Copyright©2001-5ErikD.DemaineandCharlesE.LeisersonL2.2Mergesort1.Divide:Trivial.2.Conquer:Recursivelysort2subarrays.3.Combine:Linear-timemerge.September14,2005Copyr

3、ight©2001-5ErikD.DemaineandCharlesE.LeisersonL2.3Mergesort1.Divide:Trivial.2.Conquer:Recursivelysort2subarrays.3.Combine:Linear-timemerge.T(n)=2T(n/2)+Θ(n)#subproblemsworkdividingandcombiningsubproblemsizeSeptember14,2005Copyright©2001-5ErikD.DemaineandCharlesE.LeisersonL2.4Mastertheorem(repri

4、se)T(n)=aT(n/b)+f(n)CASE1:f(n)=O(nlogba–ε),constantε>0⇒T(n)=Θ(nlogba).CASE2:f(n)=Θ(nlogbalgkn),constantk≥0⇒T(n)=Θ(nlogbalgk+1n).CASE3:f(n)=Ω(nlogba+ε),constantε>0,andregularitycondition⇒T(n)=Θ(f(n)).September14,2005Copyright©2001-5ErikD.DemaineandCharlesE.LeisersonL2.5Mastertheorem(reprise)T(n

5、)=aT(n/b)+f(n)CASE1:f(n)=O(nlogba–ε),constantε>0⇒T(n)=Θ(nlogba).CASE2:f(n)=Θ(nlogbalgkn),constantk≥0⇒T(n)=Θ(nlogbalgk+1n).CASE3:f(n)=Ω(nlogba+ε),constantε>0,andregularitycondition⇒T(n)=Θ(f(n)).Mergesort:a=2,b=2⇒nlogba=nlog22=n⇒CASE2(k=0)⇒T(n)=Θ(nlgn).September14,2005Copyright©2001-5ErikD.Demai

6、neandCharlesE.LeisersonL2.6BinarysearchFindanelementinasortedarray:1.Divide:Checkmiddleelement.2.Conquer:Recursivelysearch1subarray.3.Combine:Trivial.September14,2005Copyright©2001-5ErikD.DemaineandCharlesE.LeisersonL2.7BinarysearchFindanelementinasortedarray:1.Divide:Checkmiddleelement.2.Conq

7、uer:Recursivelysearch1subarray.3.Combine:Trivial.Example:Find9357891215September14,2005Copyright©2001-5ErikD.DemaineandCharlesE.LeisersonL2.8BinarysearchFindanelementinasortedarray:1.Divide:Checkmiddleelement.2.Conquer:Recursivelysearch