算法设计与分析解析第三版PPTch05.ppt

《算法设计与分析解析第三版PPTch05.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Divide-and-ConquerThemost-wellknownalgorithmdesignstrategy:DivideinstanceofproblemintotwoormoresmallerinstancesSolvesmallerinstancesrecursivelyObtainsolutiontooriginal(larger)instancebycombiningthesesolutions1A.Levitin“IntroductiontotheDesign&AnalysisofAlgorithms,”3rded.,Ch.5©201

2、2PearsonEducation,Inc.UpperSaddleRiver,NJ.AllRightsReserved.Divide-and-ConquerTechnique(cont.)subproblem2ofsizen/2subproblem1ofsizen/2asolutiontosubproblem1asolutiontotheoriginalproblemasolutiontosubproblem2aproblemofsizen2A.Levitin“IntroductiontotheDesign&AnalysisofAlgorithms,”3

3、rded.,Ch.5©2012PearsonEducation,Inc.UpperSaddleRiver,NJ.AllRightsReserved.Divide-and-ConquerExamplesSorting:mergesortandquicksortBinarytreetraversalsMultiplicationoflargeintegersMatrixmultiplication:Strassen’salgorithmClosest-pairandconvex-hullalgorithmsBinarysearch:decrease-by-h

4、alf(ordegeneratedivide&conq.)3A.Levitin“IntroductiontotheDesign&AnalysisofAlgorithms,”3rded.,Ch.5©2012PearsonEducation,Inc.UpperSaddleRiver,NJ.AllRightsReserved.GeneralDivide-and-ConquerRecurrenceT(n)=aT(n/b)+f(n)wheref(n)(nd),d0MasterTheorem:Ifa

5、ogn)Ifa>bd,T(n)(nlogba)Note:ThesameresultsholdwithOinsteadof.Examples:T(n)=4T(n/2)+nT(n)?T(n)=4T(n/2)+n2T(n)?T(n)=4T(n/2)+n3T(n)?4A.Levitin“IntroductiontotheDesign&AnalysisofAlgorithms,”3rded.,Ch.5©2012PearsonEducation,Inc.UpperSaddleRiver,NJ.AllRightsReserved.MergesortS

6、plitarrayA[0..n-1]intwoaboutequalhalvesandmakecopiesofeachhalfinarraysBandCSortarraysBandCrecursivelyMergesortedarraysBandCintoarrayAasfollows:Repeatthefollowinguntilnoelementsremaininoneofthearrays:comparethefirstelementsintheremainingunprocessedportionsofthearrayscopythesmaller

7、ofthetwointoA,whileincrementingtheindexindicatingtheunprocessedportionofthatarrayOnceallelementsinoneofthearraysareprocessed,copytheremainingunprocessedelementsfromtheotherarrayintoA.5A.Levitin“IntroductiontotheDesign&AnalysisofAlgorithms,”3rded.,Ch.5©2012PearsonEducation,Inc.Upp

8、erSaddleRiver,NJ.AllRightsReserved.Pseud