算法设计与分析基础第三版PPTch06PPT课件VIP

.,1,TransformandConquer,Thisgroupoftechniquessolvesaproblembyatransformationtoasimpler/moreconvenientinstanceofthesameproblem(instancesimplification)adifferentrepresentationofthesameinstance(representationchange)adifferentproblemforwhichanalgorithmisalreadyavailable(problemreduction),.,2,Instancesimplification-Presorting,Solveaproblemsinstancebytransformingitintoanothersimpler/easierinstanceofthesameproblemPresortingManyproblemsinvolvinglistsareeasierwhenlistissorted,e.g.searchingcomputingthemedian(selectionproblem)checkingifallelementsaredistinct(elementuniqueness)Also:Topologicalsortinghelpssolvingsomeproblemsfordags.Presortingisusedinmanygeometricalgorithms.,.,3,Howfastcanwesort?,Efficiencyofalgorithmsinvolvingsortingdependsonefficiencyofsorting.Theorem(seeSec.11.2):log2n!nlog2ncomparisonsarenecessaryintheworstcasetosortalistofsizenbyanycomparison-basedalgorithm.Note:Aboutnlog2ncomparisonsarealsosufficienttosortarrayofsizen(bymergesort).,.,4,Searchingwithpresorting,Problem:SearchforagivenKinA0.n-1Presorting-basedalgorithm:Stage1SortthearraybyanefficientsortingalgorithmStage2ApplybinarysearchEfficiency:(nlogn)+O(logn)=(nlogn)Goodorbad?Whydowehaveourdictionaries,telephonedirectories,etc.sorted?,.,5,ElementUniquenesswithpresorting,Presorting-basedalgorithmStage1:sortbyefficientsortingalgorithm(e.g.mergesort)Stage2:scanarraytocheckpairsofadjacentelementsEfficiency:(nlogn)+O(n)=(nlogn)BruteforcealgorithmCompareallpairsofelementsEfficiency:O(n2)Anotheralgorithm?Hashing,.,InstancesimplificationGaussianElimination,Given:Asystemofnlinearequationsinnunknownswithanarbitrarycoefficientmatrix.Transformto:Anequivalentsystemofnlinearequationsinnunknownswithanuppertriangularcoefficientmatrix.Solvethelatterbysubstitutionsstartingwiththelastequationandmovinguptothefirstone.a11x1+a12x2+a1nxn=b1a1,1x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2a22x2+a2nxn=b2an1x1+an2x2+annxn=bnannxn=bn,.,GaussianElimination(cont.),Thetransformationisaccomplishedbyasequenceofelementaryoperationsonthesystemscoefficientmatrix(whichdontchangethesystemssolution):fori1ton-1doreplaceeachofthesubsequentrows(i.e.,rowsi+1,n)byadifferencebetweenthatrowandanappropriatemultipleofthei-throwtomakethenewcoefficientinthei-thcolumnofthatrow0,.,ExampleofGaussianElimination,Solve2x1-4x2+x3=63x1-x2+x3=11x1+x2-x3=-3Gaussianelimination2-4162-4163-1111row2(3/2)*row105-1/2211-1-3row3(1/2)*row103-3/2-6row3(3/5)*row22-41605-1/2200-6/5-36/5Backwardsubstitutionx3=(-36/5)/(-6/5)=6x2=(2+(1/2)*6)/5=1x1=(66+4*1)/2=2,.,PseudocodeandEfficiencyofGaussianElimination,Stage1:Reductiontoanupper-triangularmatrixfori1ton-1doforji+1tondoforkiton+1doAj,kAj,k-Ai,k*Aj,i/Ai,i/improve!Stage2:Backsubstitutionsforjndownto1dot0forkj+1tondott+Aj,k*xkxj(Aj,n+1-t)/Aj,jEfficiency:(n3)+(n2)=(n3),.,10,SearchingProblem,Problem:Givena(multi)setSofkeysandasearchkeyK,findanoccurrenceofKinS,ifanySearchingmustbeconsideredinthecontextof:filesize(internalvs.external)dynamicsofdata(staticvs.dynamic)Dictionaryoperations(dynamicdata):find(search)insertdelete,.,11,TaxonomyofSearchingAlgorithms,ListsearchingsequentialsearchbinarysearchinterpolationsearchTreesearchingbinarysearchtreebinarybalancedtrees:AVLtrees,red-blacktreesmultiwaybalancedtrees:2-3trees,2-3-4trees,BtreesHashingopenhashing(separatechaining)closedhashing(openaddressing),.,12,BinarySearchTree,Arrangekeysinabinarytreewiththebinarysearchtreeproperty:,K,K,Example:5,3,1,10,12,7,9,.,13,DictionaryOperationsonBinarySearchTrees,SearchingstraightforwardInsertionsearchforkey,insertatleafwheresearchterminatedDeletion3cases:deletingkeyataleafdeletingkeyatnodewithsinglechilddeletingkeyatnodewithtwochildrenEfficiencydependsofthetreesheight:log2nhn-1,withheightaverage(randomfiles)beabout3log2nThusallthreeoperationshaveworstcaseefficiency:(n)averagecaseefficiency:(logn)Bonus:inordertraversalproducessortedlist,.,14,BalancedSearchTrees,Attractivenessofbinarysearchtreeismarredbythebad(linear)worst-caseefficiency.Twoideastoovercomeitare:torebalancebinarysearchtreewhenanewinsertionmakesthetree“toounbalanced”AVLtreesred-blacktreestoallowmorethanonekeypernodeofasearchtree2-3trees2-3-4treesB-trees,.,15,Balancedtrees:AVLtrees,DefinitionAnAVLtreeisabinarysearchtreeinwhich,foreverynode,thedifferencebetweentheheightsofitsleftandrightsubtrees,calledthebalancefactor,isatmost1(withtheheightofanemptytreedefinedas-1),Tree(a)isanAVLtree;tree(b)isnotanAVLtree,.,16,Rotations,Ifakeyinsertionviolatesthebalancerequirementatsomenode,thesubtreerootedatthatnodeistransformedviaoneofthefourrotations.(Therotationisalwaysperformedforasubtreerootedatan“unbalanced”nodeclosesttothenewleaf.),SingleR-rotation,DoubleLR-rotation,.,17,Generalcase:SingleR-rotation,.,18,Generalcase:DoubleLR-rotation,.,19,AVLtreeconstruction-anexample,ConstructanAVLtreeforthelist5,6,8,3,2,4,7,.,20,AVLtreeconstruction-anexample(cont.),.,21,AnalysisofAVLtrees,h1.4404log2(n+2)-1.3277averageheight:1.01log2n+0.1forlargen(foundempirically)SearchandinsertionareO(logn)DeletionismorecomplicatedbutisalsoO(logn)Disadvantages:frequentrotationscomplexityAsimilaridea:red-blacktrees(heightofsubtreesisallowedtodifferbyuptoafactorof2),.,22,MultiwaySearchTrees,DefinitionAmultiwaysearchtreeisasearchtreethatallowsmorethanonekeyinthesamenodeofthetree.DefinitionAnodeofasearchtreeiscalledann-nodeifitcontainsn-1orderedkeys(whichdividetheentirekeyrangeintonintervalspointedtobythenodesnlinkstoitschildren):Note:Everynodeinaclassicalbinarysearchtreeisa2-node,k1k2kn-1,k1,k1,k2),kn-1,.,23,2-3Tree,DefinitionA2-3treeisasearchtreethatmayhave2-nodesand3-nodesheight-balanced(allleavesareonthesamelevel)A2-3treeisconstructedbysuccessiveinsertionsofkeysgiven,withanewkeyalwaysinsertedintoaleafofthetree.Iftheleafisa3-node,itssplitintotwowiththemiddlekeypromotedtotheparent.,.,24,2-3treeconstructionanexample,Constructa2-3treethelist9,5,8,3,2,4,7,.,25,Analysisof2-3trees,log3(n+1)-1hlog2(n+1)-1Search,insertion,anddeletionarein(logn)Theideaof2-3treecanbegeneralizedbyallowingmorekeyspernode2-3-4treesB-trees,.,26,HeapsandHeapsort,DefinitionAheapisabinarytreewithkeysatitsnodes(onekeypernode)suchthat:Itisessentiallycomplete,i.e.,allitslevelsarefullexceptpossiblythelastlevel,whereonlysomerightmostkeysmaybemissingThekeyateachnodeiskeysatitschildren,.,27,Illustrationoftheheapsdefinition,aheap,notaheap,notaheap,Note:Heapselementsareorderedtopdown(alonganypathdownfromitsroot),buttheyarenotorderedlefttoright,.,28,SomeImportantPropertiesofaHeap,Givenn,thereexistsauniquebinarytreewithnnodesthatisessentiallycomplete,withh=log2nTherootcontainsthelargestkeyThesubtreerootedatanynodeofaheapisalsoaheapAheapcanberepresentedasanarray,.,29,HeapsArrayRepresentation,Storeheapselementsinanarray(whoseelementsindexed,forconvenience,1ton)intop-downleft-to-rightorderExample:Leftchildofnodejisat2jRightchildofnodejisat2j+1Parentofnodejisatj/2Parentalnodesarerepresentedinthefirstn/2locations,9,1,5,3,4,2,.,30,Step0:InitializethestructurewithkeysintheordergivenStep1:Startingwiththelast(rightmost)parentalnode,fixtheheaprootedatit,ifitdoesntsatisfytheheapcondition:keepexchangingitwithitslargestchilduntiltheheapconditionholdsStep2:RepeatStep1fortheprecedingparentalnode,HeapConstruction(bottom-up),.,31,ExampleofHeapConstruction,Constructaheapforthelist2,9,7,6,5,8,.,32,Pseudopodiaofbottom-upheapconstruction,.,33,Stage1:ConstructaheapforagivenlistofnkeysStage2:Repeatoperationofrootremovaln-1times:Exchangekeysintherootandinthelast(rightmost)leafDecreaseheapsizeby1Ifnecessary,swapnewrootwithlargerchilduntiltheheapconditionholds,Heapsort,.,34,Sortthelist2,9,7,6,5,8byheapsortStage1(heapconstruction)Stage2(root/maxremoval)19765896825729865776825|929865786725|99286575672|899682577652|89265|789625|78952|678952|67892|56789,ExampleofSortingbyHeapsort,.,35,Stage1:Buildheapforagivenlistofnkeysworst-caseC(n)=Stage2:Repeatoperationofrootremovaln-1times(fixheap)worst-caseC(n)=Bothworst-caseandaverage-caseefficiency:(nlogn)In-place:yesStability:no(e.g.,11),2(h-i)2i=2(nlog2(n+1)(n),i=0,h-1,#nodesatleveli,i=1,n-1,2log2i(nlogn),AnalysisofHeapsort,.,36,ApriorityqueueistheADTofasetofelementswithnumericalprioritieswiththefollowingoperations:findelementwithhighestprioritydeleteelementwithhighestpriorityinsertelementwithassignedpriority(seebelow)HeapisaveryefficientwayforimplementingpriorityqueuesTwowaystohandlepriorityqueueinwhichhighestpriority=smallestnumber,PriorityQueue,.,37,InsertionofaNewElementintoaHeap,Insertthenewelementatlastpositioninheap.Compareitwithitsparentand,ifitviolatesheapcondition,exchangethemContinuecomparingthenewelementwithnodesupthetreeuntiltheheapconditionissatisfiedExample:Insertkey10Efficiency:O(logn),.,38,HornersRuleForPolynomialEvaluation,Givenapolynomialofdegreenp(x)=anxn+an-1xn-1+a1x+a0andaspecificvalueofx,findthevalueofpatthatpoint.Twobrute-forcealgorithms:p0pa0;power1forindownto0dofori1tondopower1powerpower*xforj1toidopp+ai*powerpowerpower*xreturnppp+ai*powerreturnp,.,39,HornersRule,Example:p(x)=2x4-x3+3x2+x-5=x(2x3-x2+3x+1)-5=x(x(2x2-x+3)+1)-5=x(x(x(2x-1)+3)+1)-5SubstitutionintothelastformulaleadstoafasteralgorithmSamesequenceofcomputationsareobtainedbysimplyarrangingthecoefficientinatableandproceedingasfollows:coefficients2-131-5x=3,.,40,HornersRulepseudocode,EfficiencyofHornersRule:#multiplications=#additions=nSyntheticdivisionofofp(x)by(x-x0)Example:Letp(x)=2x4-x3+3x2+x-5.Findp(x):(x-3),.,41,Computingan(revisited),Left-to-rightbinaryexponentiationInitializeproductaccumulatorby1.Scannsbinaryexpansionfromlefttorightanddothefollowing:Ifthecurrentbinarydigitis0,squaretheaccumulator(S);ifthebinarydigitis1,squaretheaccumulatorandmultiplyitbya(SM).Example:Computea13.Here,n=13=11012binaryrep.of13:1101SMSMSSMaccumula