DIVIDE-AND-CONQUER.ppt

4 1 Chapter4 TheDivide and ConquerStrategy 4 2 Asimpleexample findingthemaximumofasetSofnnumbers 4 3 Timecomplexity T n ofcomparisonsCalculationofT n Assumen 2k T n 2T n 2 1 2 2T n 4 1 1 4T n 4 2 1 2k 1T 2 2k 2 4 2 1 2k 1 2k 2 4 2 1 2k 1 n 1 Timecomplexity 4 4 Ageneraldivide and conqueralgorithm Step1 Iftheproblemsizeissmall solvethisproblemdirectly otherwise splittheoriginalprobleminto2sub problemswithequalsizes Step2 Recursivelysolvethese2sub problemsbyapplyingthisalgorithm Step3 Mergethesolutionsofthe2sub problemsintoasolutionoftheoriginalproblem 4 5 Timecomplexityofthegeneralalgorithm Timecomplexity whereS n timeforsplittingM n timeformergingb aconstantc aconstant 4 6 Binarysearch e g 2456789 search7 needs3comparisonstime O logn Thebinarysearchcanbeusedonlyiftheelementsaresortedandstoredinanarray 4 7 Algorithmbinary search Input Asortedsequenceofnelementsstoredinanarray Output Thepositionofx tobesearched Step1 Ifonlyoneelementremainsinthearray solveitdirectly Step2 Comparexwiththemiddleelementofthearray Step2 1 Ifx middleelement thenoutputitandstop Step2 2 Ifxmiddleelement thenrecursivelysolvetheproblemwithxandtherighthalfarray 4 8 AlgorithmBinSearch a low high x a sortedsequenceinnondecreasingorder low high theboundsforsearchingina x theelementtobesearched Ifx a j forsomej thenreturnjelsereturn 1if low high thenreturn 1 invalidrangeif low high then ifsmallPif x a i thenreturnielsereturn 1else dividePintotwosmallersubproblemsmid low high 2if x a mid thenreturnmidelseif x a mid thenreturnBinSearch a low mid 1 x elsereturnBinSearch a mid 1 high x 4 9 Quicksort Sortintonondecreasingorder 265371611159154819 265191611159154837 265191151159614837 11519115 26 59614837 11511915 26 59614837 15 11 1915 26 59614837 1511151926 59614837 1511151926 59374861 1511151926 4837 59 61 151115192637485961 4 10 AlgorithmQuicksort Input AsetSofnelements Output Thesortedsequenceoftheinputsinnondecreasingorder Step1 If S 2 solveitdirectly Step2 Partitionstep UseapivottoscanallelementsinS PutthesmallerelementsinS1 andthelargerelementsinS2 Step3 RecursivelysolveS1andS2 4 11 TimecomplexityofQuicksort timeintheworstcase n 1 n 2 1 n n 1 2 O n2 timeinthebestcase Ineachpartition theproblemisalwaysdividedintotwosubproblemswithalmostequalsize 4 12 Timecomplexityofthebestcase T n timerequiredforsortingnelementsT n cn 2T n 2 forsomeconstantc cn 2 c n 2 2T n 4 2cn 4T n 4 cnlog2n nT 1 O nlogn 4 13 Mergetwosortedsequencesintoasingleone timecomplexity O m n mandn lengthsofthetwosortedlists Two waymerge 4 14 Sortintonondecreasingorderlog2npassesarerequired timecomplexity O nlogn Mergesort 4 15 AlgorithmMerge Sort Input AsetSofnelements Output Thesortedsequenceoftheinputsinnondecreasingorder Step1 If S 2 solveitdirectly Step2 RecursivelyapplythisalgorithmtosolvethelefthalfpartandrighthalfpartofS andtheresultsarestoredinS1andS2 respectively Step3 Performthetwo waymergeschemeonS1andS2 4 16 2 Dmaximafindingproblem Def Apoint x1 y1 dominates x2 y2 ifx1 x2andy1 y2 ApointiscalledamaximumifnootherpointdominatesitStraightforwardmethod Compareeverypairofpoints Timecomplexity O n2 4 17 Divide and conquerformaximafinding ThemaximalpointsofSLandSR 4 18 Thealgorithm Input AsetSofnplanarpoints Output ThemaximalpointsofS Step1 IfScontainsonlyonepoint returnitasthemaxima Otherwise findalineLperpendiculartotheX axiswhichseparatesSintoSLandSR withequalsizes Step2 RecursivelyfindthemaximalpointsofSLandSR Step3 Findthelargesty valueofSR denotedasyR DiscardeachofthemaximalpointsofSLifitsy valueislessthanyR 4 19 Timecomplexity T n Step1 O n Step2 2T n 2 Step3 O n Assumen 2kT n O nlogn 4 20 Theclosestpairproblem GivenasetSofnpoints findapairofpointswhichareclosesttogether 1 Dversion SolvedbysortingTimecomplexity O nlogn 2 Dversion 4 21 atmost6pointsinareaA 4 22 Thealgorithm Input AsetSofnplanarpoints Output Thedistancebetweentwoclosestpoints Step1 SortpointsinSaccordingtotheiry values Step2 IfScontainsonlyonepoint returninfinityasitsdistance Step3 FindamedianlineLperpendiculartotheX axistodivideSintoSLandSR withequalsizes Step4 RecursivelyapplySteps2and3tosolvetheclosestpairproblemsofSLandSR LetdL dR denotethedistancebetweentheclosestpairinSL SR Letd min dL dR 4 23 Step5 ForapointPinthehalf slabboundedbyL dandL letitsy valuebedenotedasyP ForeachsuchP findallpointsinthehalf slabboundedbyLandL dwhosey valuefallwithinyP dandyP d Ifthedistanced betweenPandapointintheotherhalf slabislessthand letd d Thefinalvalueofdistheanswer Timecomplexity O nlogn Step1 O nlogn Steps2 5 T n O nlogn 4 24 Theconvexhullproblem Theconvexhullofasetofplanarpointsisthesmallestconvexpolygoncontainingallofthepoints 4 25 Thedivide and conquerstrategytosolvetheproblem 4 26 Themergingprocedure Selectaninteriorpointp Thereare3sequencesofpointswhichhaveincreasingpolarangleswithrespecttop 1 g h i j k 2 a b c d 3 f eMergethese3sequencesinto1sequence g h a b f c e d i j k ApplyGrahamscantoexaminethepointsonebyoneandeliminatethepointswhichcausereflexiveangles Seetheexampleonthenextpage 4 27 e g pointsbandfneedtobedeleted Finalresult 4 28 Divide and conquerforconvexhull Input AsetSofplanarpointsOutput AconvexhullforSStep1 IfScontainsnomorethanfivepoints useexhaustivesearchingtofindtheconvexhullandreturn Step2 FindamedianlineperpendiculartotheX axiswhichdividesSintoSLandSR withequalsizes Step3 RecursivelyconstructconvexhullsforSLandSR denotedasHull SL andHull SR respectively 4 29 Step4 ApplythemergingproceduretomergeHull SL andHull SR togethertoformaconvexhull Timecomplexity T n 2T n 2 O n O nlogn 4 30 Matrixmultiplication LetA BandCben nmatricesC ABC i j A i k B k j ThestraightforwardmethodtoperformamatrixmultiplicationrequiresO n3 time 4 31 Divide and conquerapproach C ABC11 A11B11 A12B21C12 A11B12 A12B22C21 A21B11 A22B21C22 A21B12 A22B22Timecomplexity ofadditions n2 WegetT n O n3 4 32 P A11 A22 B11 B22 Q A21 A22 B11R A11 B12 B22 S A22 B21 B11 T A11 A12 B22U A21 A11 B11 B12 V A12 A22 B21 B22 C11 P S T VC12 R TC21 Q SC22 P R Q U Strassen smatrixmultiplicaiton C11 A11B11 A12B21C12 A11B12 A12B22C21 A21B11 A22B21C22 A21B12 A22B22 4 33 Timecomplexity 7multiplicationsand18additionsorsubtractionsTimecomplexity 4 34 FastFouriertransform FFT FouriertransformInverseFouriertransformDiscreteFouriertransform DFT Givena0 a1 an 1 compute 4 35 DFTandwaveform 1 Anyperiodicwaveformcanbedecomposedintothelinearsumofsinusoidfunctions sineorcosine 4 36 Thewaveformofamusicsignalof1second ThefrequencyspectrumofthemusicsignalwithDFT DFTandwaveform 2 4 37 InverseDFT DFTcanbecomputedinO n2 timebyastraightforwardmethod DFTcanbesolvedbythedivide and conquerstrategy FFT inO nlogn time FFTalgorithm 4 38 FFTalgorithmwhenn 4 n 4 w ei2 4 w4 1 w2 1b0 a0 a1 a2 a3b1 a0 a1w a2w2 a3w3b2 a0 a1w2 a2w4 a3w6b3 a0 a1w3 a2w6 a3w9anotherform b0 a0 a2 a1 a3 b2 a0 a2w4 a1w2 a3w6 a0 a2 a1 a3 Whenwecalculateb0 weshallcalculate a0 a2 and a1 a3 Later b2vanbeeasilycalculated Similarly b1 a0 a2w2 a1w a3w3 a0 a2 w a1 a3 b3 a0 a2w6 a1w3 a3w9 a0 a2 w a1 a3 4 39 n 8 w ei2 8 w8 1 w4 1b0 a0 a1 a2 a3 a4 a5 a6 a7b1 a0 a1w a2w2 a3w3 a4w4 a5w5 a6w6 a7w7b2 a0 a1w2 a2w4 a3w6 a4w8 a5w10 a6w12 a7w14b3 a0 a1w3 a2w6 a3w9 a4w12 a5w15 a6w18 a7w21b4 a0 a1w4 a2w8 a3w12 a4w16 a5w20 a6w24 a7w28b5 a0 a1w5 a2w10 a3w15 a4w20 a5w25 a6w30 a7w35b6 a0 a1w6 a2w12 a3w18 a4w24 a5w30 a6w36 a7w42b7 a0 a1w7 a2w14 a3w21 a4w28 a5w35 a6w42 a7w49 FFTalgorithmwhenn 8 4 40 Afterreordering wehaveb0 a0 a2 a4 a6 a1 a3 a5 a7 b1 a0 a2w2 a4w4 a6w6 w a1 a3w2 a5w4 a7w6 b2 a0 a2w4 a4w8 a6w12 w2 a1 a3w4 a5w8 a7w12 b3 a0 a2w6 a4w12 a6w18 w3 a1 a3w6 a5w12 a7w18 b4 a0 a2 a4 a6 a1 a3 a5 a7 b5 a0 a2w2 a4w4 a6w6 w a1 a3w2 a5w4 a7w6 b6 a0 a2w4 a4w8 a6w12 w2 a1 a3w4 a5w8 a7w12 b7 a0 a2w6 a4w12 a6w18 w3 a1 a3w6 a5w12 a7w18 Rewriteasb0 c0 d0b4 c0 d0 c0 w4d0b1 c1 wd1b5 c1 wd1 c1 w5d1b2 c2 w2d2b6 c2 w2d2 c2 w6d2b3 c3 w3d3b7 c3 w3d3 c3 w7d3 4 41 c0 a0 a2 a4 a6c1 a0