算法设计与分析双语课Chapter 3 Divide and conquer

算法设计与分析NorthChinaElectricPowerUniversityAlgorithmsDesign&Analysis华北电力大学计算机科学与技术学院SchoolofComputerScience&TechnologyofNorthChinaElectricPowerUniversityChapter3DivideandConquerNorthChinaElectricPowerUniversity1.Introduction2.Thedivideandconquerparadigm3.Binarysearch4.Mergesort5.Multiplicationoflargeintegers6.Matrixmultiplication7.Linear-timeselectionproblem§1IntroductionNorthChinaElectricPowerUniversityThenameof“divideandconquer”hasbeengiventoapowerfulalgorithmdesigntechniquethatisusedtosolveavarietyofproblems.Initssimplestform,adivide-and-conqueralgorithmdividestheprobleminstanceintoanumberofsubinstance,recursivelysolveseachsubinstanceseparately,andthencombinesthesolutionstothesubinstancestoobtaintheoriginalprobleminstance.Themostappealingmeritsofdivide-and-conqueralgorithmsare:conciseness,easeofcomprehensionandimplementation,andthemostimportantlythesimpleinductiveproofsforthecorrectness.Example:ConsidertheproblemoffindingboththeminimumandmaximuminanarrayofintegersA[1..n]andassumeforsimplicitythatnisapowerof2.Analysis:Astraightforwardalgorithmmightlookliketheonebelow.Itreturnsapair(x,y)wherexistheminimumandyisthemaximum.ProcedureMaxmin1(A;n;varx:integer;vary:integer);Beginx:=A[1];y:=A[1];fori:=2tondo[ifA[i]xthenx:=A[i];ifA[i]ytheny:=A[i];]End;NorthChinaElectricPowerUniversity2(n-1)Divide-and-conqueralgorithm:DividetheinputarrayintotwohalvesA[1..n/2]andA[n/2+1..n],findtheminimumandmaximumineachhalfandreturntheminimumofthetwominimaandthethemaximumofthetwomaxima.ProcedureMaxmin2(A;l,r:integer;varx:integer;vary:integer);Beginifl=rthen[x:=A[l];y:=A[r];return;]ifr-l=1then[ifA[l]A[r]then[x:=A[l];y:=A[r]]else[x:=A[r];y:=A[l];]return;]else[mid:=(l+r)div2;Maxmin2(A,l,mid,x1,y1);Maxmin2(A,mid+1,r,x2,y2);x:=min(x1,x2);y:=max(y1,y2);]End;NorthChinaElectricPowerUniversityTimecomplexityanalysis:LetC(n)denotethenumberofcomparisonsperformedbythealgorithmonanarrayofnelements,wherenisapowerof2.Thefollowingistherecurrencerelationforthenumberofcomparisonsdonebythealgorithm2nif2)2/(22nif1)(nCnCSolvingthisrecurrencebyexpansionasfollows(k=logn)2)2/3(22)2/(2)2(222...22)2/(2...24)4/(42)2)4/(2(22)2/(2)(11122111nnCnCnCnCnCnCkkjjkkkkkNorthChinaElectricPowerUniversity§2ThedivideandconquerparadigmFromapracticalpointofview,theredoesnotseemtobeanyreasontofavorarecursivealgorithmonitsequivalentiterativeversion.However,fromatheoreticalpointofview,recursivealgorithmssharethemeritsofbeingeasytostate,graspandanalyze.Thissuggeststhatadesignerofanalgorithmmightbebetterstartingwithanoutlineofarecursivedescription,ifpossible,whichmayafterwardsberefinedandconvertedintoanalgorithmwhichfunctionsinexactlythesamewayoneveryinstanceoftheproblem.Ingeneral,thedivideandconquerparadigmconsistsofthefollowingSteps.a)Thedividestep.Inthisstepofthealgorithm,theinputispartitionedintop≥1parts,eachofsizestrictlylessthann,thesizeoftheoriginalinstance.NorthChinaElectricPowerUniversityb)TheconquerstepThisstepconsistsofperformingprecursivecallsiftheproblemsizeisgreaterthansomepredefinedthresholdn0.Thisthresholdisderivedbymathematicalanalysisofthealgorithm.Onceitisfound,itcanbeincreasedbyanyconstantamountwithoutaffectingthetimecomplexityofthealgorithm.Thisisbecausethetimecomplexity,bydefinition,isconcernedwiththebehaviorofthealgorithmwhennapproachesinfinity.NorthChinaElectricPowerUniversityc)ThecombinestepInthisstep,thesolutiontotheprecursivecallsarecombinedtoobtainthedesiredoutput.Thecombinestepinadivide-and-conqueralgorithmmayconsistofmerging,sorting,searching,findingthemaximumorminimum,matrixaddition,etc.Ingeneral,adivide-and-conqueralgorithmhasthefollowingformat.1)IfthesizeoftheinstanceIis“small”,thensolvetheproblemusingastraightforwardmethodandreturntheanswer.Otherwise,Continuetothenextstep.Notation:1.Thecombinestepisverycrucialtotheperformanceofvirtuallyalldivide-and-conqueralgorithms,astheefficiencyofthealgorithmislargelydependentonhowjudiciouslythisstepisimplemented.2.Ontheotherhand,thedividestepisinvariantinalmostalldivide-and-conqueralgorithms:Partitiontheinputdataintopparts,andproceedtotheconquerstep.Inmanydivide-and-conqueralgorithms,ittakesO(n)timeorevenonlyO(1)time.NorthChinaElectricPowerUniversity2)DividetheinstanceIintopsubinstanceI1,I2,…,Ipofapproximatelythesamesize.NorthChinaElectricPowerUniversity3)RecursivelycallthealgorithmoneachsubinstanceIj,1≤j≤p,toobtainppartialsolutions.4)CombinetheresultsoftheppartialsolutionstoobtainthesolutiontotheoriginalinstanceI.ReturnthesolutionofinstanceI.Theoverallperformanceofadivide-and-conqueralgorithmisverysensitivetochangesinthesesteps.Inthefirststep,thethresholdshouldbechosencarefully.Inthesecondstep,thenumberofpartitionsshouldbeselectedappropriatelysoastoachievetheasymptoticallyminimumrunningtime.Finally,thecombinestepshouldbeasefficientaspossible.§3BinarysearchInbinarysearch,wetestagivenelementxagainstthemiddleelementinasortedarrayA[low..high].IfxA[mid],wheremid=(low+high)div2,thenwediscardA[mid..high]andthesameprocedureisrepeatedonA[low..mid-1].Similarly,ifxA[mid],