《算法设计技巧与分析》第6章 分治（英文）-教学课件（非AI生成）.ppt

Chapter6DivideandConquer

ContentsofcurrentchapterBasicconceptsonDivideandConquerIntroductionTwosimpleexamplesBinarysearchMergesortTheDivideandConquerparadigmSomeproblemssolvedinDivideandConquerstrategySelectionQuicksortMultiplicationofLargeIntegersMatrixMultiplicationTheclosestpairproblem

6.1Introduction Whatistheformofadivide-andconqueralgorithm?Dividestheprobleminstanceintoanumberofsubinstances(inmostcases2);Recursivelysolveseachsubinstanceseparatelyandthen,Combinesthesolutionstothesubinstancestoobtainthesolutiontotheoriginalprobleminstance.

FindingthemaximumandminimumProblemdescriptionFindingboththeminimumandmaximuminanarrayofintegersA[1..n]andassumeforsimplicitythatnisapowerof2.Astraightforwardmethod1.x?A[1];y?A[1]2.fori?2ton3.ifA[i]xthenx?A[i]4.ifA[i]ytheny?A[i]5.endfor6.return(x,y)Clearlythenumberofelementcomparisonsperformedbythismethodis2n-2.Muchmoreefficientmethod?

DivideandConquerMethodBasicideaDividetheinputarrayintotwohalvesA[1..n/2]andA[(n/2)+1..n];Findtheminimumandmaximumineachhalfand;Returntheminimumofthetwominimaandthemaximumofthetwomaxima.

Algorithm6.1MINMAXInput:AnarrayA[1..n]ofnintegers,wherenisapowerof2.Output:(x,y):theminimumandmaximumintegersinA.1.minmax(1,n)Procedureminmax(low,high)1.ifhigh-low=1then2.ifA[low]A[high]thenreturn(A[low],A[high])3.elsereturn(A[high],A[low])4.endif5.else6.mid??(low+high)/2?7.(x1,y1)?minmax(low,mid)8.(x2,y2)?minmax(mid+1,high)9.x?min(x1,x2)10.y?max(y1,y2)11.return(x,y)12.endif

AlgorithmanalysisLetC(n)denotethenumberofelementcomparisons,wherenisapowerof2.Theorem6.1GivenanarrayA[1..n]ofnelements,wherenisapowerof2,itispossibletofindb