《算法导论CLRS》英文版第三版.pdf

ALGORITHMSINTRODUCTIONTOTHIRDEDITIONTHOMASHCHARLESERONALDLCLIFFORDSTEINRIVESTLEISERSONCORMENIntroductiontoAlgorithmsThirdEditionThomasHCormenCharlesELeisersonRonaldLRivestCliffordSteinIntroductiontoAlgorithmsThirdEditionTheMITPressCambridge,MassachusettsLondon,EnglandcMassachusettsInstituteofTechnologyAllrightsreservedNopartofthisbookmaybereproducedinanyformorbyanyelectronicormechanicalmeans(includingphotocopying,recording,orinformationstorageandretrieval)withoutpermissioninwritingfromthepublisherForinformationaboutspecialquantitydiscounts,pleaseemailspecialsalesmitpressmiteduThisbookwassetinTimesRomanandMathtimeProbytheauthorsPrintedandboundintheUnitedStatesofAmericaLibraryofCongressCataloginginPublicationDataIntroductiontoalgorithmsThomasHCormenetalrdedpcmIncludesbibliographicalreferencesandindexISBN(hardcover:alkpaper)ISBN(pbk:alkpaper)ComputerprogrammingComputeralgorithmsICormen,ThomasHQAIdcContentsPrefacexiiiIFoundationsIntroductionTheRoleofAlgorithmsinComputingAlgorithmsAlgorithmsasatechnologyGettingStartedInsertionsortAnalyzingalgorithmsDesigningalgorithmsGrowthofFunctionsAsymptoticnotationStandardnotationsandcommonfunctionsDivideandConquerThemaximumsubarrayproblemStrassen’salgorithmformatrixmultiplicationThesubstitutionmethodforsolvingrecurrencesTherecursiontreemethodforsolvingrecurrencesThemastermethodforsolvingrecurrencesProofofthemastertheoremProbabilisticAnalysisandRandomizedAlgorithmsThehiringproblemIndicatorrandomvariablesRandomizedalgorithmsProbabilisticanalysisandfurtherusesofindicatorrandomvariablesviContentsIISortingandOrderStatisticsIntroductionHeapsortHeapsMaintainingtheheappropertyBuildingaheapTheheapsortalgorithmPriorityqueuesQuicksortDescriptionofquicksortPerformanceofquicksortArandomizedversionofquicksortAnalysisofquicksortSortinginLinearTimeLowerboundsforsortingCountingsortRadixsortBucketsortMediansandOrderStatisticsMinimumandmaximumSelectioninexpectedlineartimeSelectioninworstcaselineartimeIIIDataStructuresIntroductionElementaryDataStructuresStacksandqueuesLinkedlistsImplementingpointersandobjectsRepresentingrootedtreesHashTablesDirectaddresstablesHashtablesHashfunctionsOpenaddressingPerfecthashingContentsviiBinarySearchTreesWhatisabinarysearchtreeQueryingabinarysearchtreeInsertionanddeletionRandomlybuiltbinarysearchtreesRedBlackTreesPropertiesofredblacktreesRotationsInsertionDeletionAugmentingDataStructuresDynamicorderstatisticsHowtoaugmentadatastructureIntervaltreesIVAdvancedDesignandAnalysisTechniquesIntroductionDynamicProgrammingRodcuttingMatrixchainmultiplicationElementsofdynamicprogrammingLongestcommonsubsequenceOptimalbinarysearchtreesGreedyAlgorithmsAnactivityselectionproblemElementsofthegreedystrategyHuffmancodesMatroidsandgreedymethodsAtaskschedulingproblemasamatroidAmortizedAnalysisAggregateanalysisTheaccountingmethodThepotentialmethodDynamictablesviiiContentsVAdvancedDataStructuresIntroductionBTreesDefinitionofBtreesBasicoperationsonBtreesDeletingakeyfromaBtreeFibonacciHeapsStructureofFibonacciheapsMergeableheapoperationsDecreasingakeyanddeletinganodeBoundingthemaximumdegreevanEmdeBoasTreesPreliminaryapproachesArecursivestructureThevanEmdeBoastreeDataStructuresforDisjointSetsDisjointsetoperationsLinkedlistrepresentationofdisjointsetsDisjointsetforestsAnalysisofunionbyrankwithpathcompressionVIGraphAlgorithmsIntroductionElementaryGraphAlgorithmsRepresentationsofgraphsBreadthfirstsearchDepthfirstsearchTopologicalsortStronglyconnectedcomponentsMinimumSpanningTreesGrowingaminimumspanningtreeThealgorithmsofKruskalandPrimContentsixSingleSourceShortestPathsTheBellmanFordalgorithmSinglesourceshortestpathsindirectedacyclicgraphsDijkstra’salgorithmDifferenceconstraintsandshortestpathsProofsofshortestpathspropertiesAllPairsShortestPathsShortestpathsandmatrixmultiplicationTheFloydWarshallalgorithmJohnson’salgorithmforsparsegraphsMaximumFlowFlownetworksTheFordFulkersonmethodMaximumbipartitematchingPushrelabelalgorithmsTherelabeltofrontalgorithmVIISelectedTopicsIntroductionMultithreadedAlgorithmsThebasicsofdynamicmultithreadingMultithreadedmatrixmultiplicationMultithreadedmergesortMatrixOperationsSolvingsystemsoflinearequationsInvertingmatricesSymmetricpositivedefinitematricesandleastsquaresapproximationLinearProgrammingStandardandslackformsFormulatingproblemsaslinearprogramsThesimplexalgorithmDualityTheinitialbasicfeasiblesolutionxContentsPolynomialsandtheFFTRepresentingpolynomialsTheDFTandFFTEfficientFFTimplementationsNumberTheoreticAlgorithmsElementarynumbertheoreticnotionsGreatestcommondivisorModulararithmeticSolvingmodularlinearequationsTheChineseremaindertheoremPowersofanelementTheRSApublickeycryptosystemPrimalitytestingIntegerfactorizationStringMatchingThenaivestringmatchingalgorithmTheRabinKarpalgorithmStringmatchingwithfiniteautomataTheKnuthMorrisPrattalgorithmComputationalGeometryLinesegmentpropertiesDeterminingwhetheranypairofsegmentsintersectsFindingtheconvexhullFindingtheclosestpairofpointsNPCompletenessPolynomialtimePolynomialtimeverificationNPcompletenessandreducibilityNPcompletenessproofsNPcompleteproblemsApproximationAlgorithmsThevertexcoverproblemThetravelingsalesmanproblemThesetcoveringproblemRandomizationandlinearprogrammingThesubsetsumproblemContentsxiVIIIAppendix:MathematicalBackgroundIntroductionASummationsASummationformulasandpropertiesABoundingsummationsBSets,EtcBSetsBRelationsBFunctionsBGraphsBTreesCCountingandProbabilityCCountingCProbabilityCDiscreterandomvariablesCThegeometricandbinomialdistributionsCThetailsofthebinomialdistributionDMatricesDMatricesandmatrixoperationsDBasicmatrixpropertiesBibliographyIndexPrefaceBeforetherewerecomputers,therewerealgorithmsButnowthattherearecomputers,thereareevenmorealgorithms,andalgorithmslieattheheartofcomputingThisbookprovidesacomprehensiveintroductiontothemodernstudyofcomputeralgorithmsItpresentsmanyalgorithmsandcoverstheminconsiderabledepth,yetmakestheirdesignandanalysisaccessibletoalllevelsofreadersWehavetriedtokeepexplanationselementarywithoutsacrificingdepthofcoverageormathematicalrigorEachchapterpresentsanalgorithm,adesigntechnique,anapplicationarea,orarelatedtopicAlgorithmsaredescribedinEnglishandinapseudocodedesignedtobereadablebyanyonewhohasdonealittleprogrammingThebookcontainsfiguresmanywithmultiplepartsillustratinghowthealgorithmsworkSinceweemphasizeefficiencyasadesigncriterion,weincludecarefulanalysesoftherunningtimesofallouralgorithmsThetextisintendedprimarilyforuseinundergraduateorgraduatecoursesinalgorithmsordatastructuresBecauseitdiscussesengineeringissuesinalgorithmdesign,aswellasmathematicalaspects,itisequallywellsuitedforselfstudybytechnicalprofessionalsInthis,thethirdedition,wehaveonceagainupdatedtheentirebookThechangescoverabroadspectrum,includingnewchapters,revisedpseudocode,andamoreactivewritingstyleTotheteacherWehavedesignedthisbooktobebothversatileandcompleteYoushouldfinditusefulforavarietyofcourses,fromanundergraduatecourseindatastructuresupthroughagraduatecourseinalgorithmsBecausewehaveprovidedconsiderablymorematerialthancanfitinatypicalonetermcourse,youcanconsiderthisbooktobea“buffet”or“smorgasbord”fromwhichyoucanpickandchoosethematerialthatbestsupportsthecourseyouwishtoteachxivPrefaceYoushouldfinditeasytoorganizeyourcoursearoundjustthechaptersyouneedWehavemadechaptersrelativelyselfcontained,sothatyouneednotworryaboutanunexpectedandunnecessarydependenceofonechapteronanotherEachchapterpresentstheeasiermaterialfirstandthemoredifficultmateriallater,withsectionboundariesmarkingnaturalstoppingpointsInanundergraduatecourse,youmightuseonlytheearliersectionsfromachapterinagraduatecourse,youmightcovertheentirechapterWehaveincludedexercisesandproblemsEachsectionendswithexercises,andeachchapterendswithproblemsTheexercisesaregenerallyshortquestionsthattestbasicmasteryofthematerialSomearesimpleselfcheckthoughtexercises,whereasothersaremoresubstantialandaresuitableasassignedhomeworkTheproblemsaremoreelaboratecasestudiesthatoftenintroducenewmaterialtheyoftenconsistofseveralquestionsthatleadthestudentthroughthestepsrequiredtoarriveatasolutionDepartingfromourpracticeinpreviouseditionsofthisbook,wehavemadepubliclyavailablesolutionstosome,butbynomeansall,oftheproblemsandexercisesOurWebsite,http:mitpressmitedualgorithms,linkstothesesolutionsYouwillwanttocheckthissitetomakesurethatitdoesnotcontainthesolutiontoanexerciseorproblemthatyouplantoassignWeexpectthesetofsolutionsthatweposttogrowslowlyovertime,soyouwillneedtocheckiteachtimeyouteachthecourseWehavestarred()thesectionsandexercisesthataremoresuitableforgraduatestudentsthanforundergraduatesAstarredsectionisnotnecessarilymoredifficultthananunstarredone,butitmayrequireanunderstandingofmoreadvancedmathematicsLikewise,starredexercisesmayrequireanadvancedbackgroundormorethanaveragecreativityTothestudentWehopethatthistextbookprovidesyouwithanenjoyableintroductiontothefieldofalgorithmsWehaveattemptedtomakeeveryalgorithmaccessibleandinterestingTohelpyouwhenyouencounterunfamiliarordifficultalgorithms,wedescribeeachoneinastepbystepmannerWealsoprovidecarefulexplanationsofthemathematicsneededtounderstandtheanalysisofthealgorithmsIfyoualreadyhavesomefamiliaritywithatopic,youwillfindthechaptersorganizedsothatyoucanskimintroductorysectionsandproceedquicklytothemoreadvancedmaterialThisisalargebook,andyourclasswillprobablycoveronlyaportionofitsmaterialWehavetried,however,tomakethisabookthatwillbeusefultoyounowasacoursetextbookandalsolaterinyourcareerasamathematicaldeskreferenceoranengineeringhandbookPrefacexvWhataretheprerequisitesforreadingthisbookYoushouldhavesomeprogrammingexperienceInparticular,youshouldunderstandrecursiveproceduresandsimpledatastructuressuchasarraysandlinkedlistsYoushouldhavesomefacilitywithmathematicalproofs,andespeciallyproofsbymathematicalinductionAfewportionsofthebookrelyonsomeknowledgeofelementarycalculusBeyondthat,PartsIandVIIIofthisbookteachyouallthemathematicaltechniquesyouwillneedWehaveheard,loudandclear,thecalltosupplysolutionstoproblemsandexercisesOurWebsite,http:mitpressmitedualgorithms,linkstosolutionsforafewoftheproblemsandexercisesFeelfreetocheckyoursolutionsagainstoursWeask,however,thatyoudonotsendyoursolutionstousTotheprofessionalThewiderangeoftopicsinthisbookmakesitanexcellenthandbookonalgorithmsBecauseeachchapterisrelativelyselfcontained,youcanfocusinonthetopicsthatmostinterestyouMostofthealgorithmswediscusshavegreatpracticalutilityWethereforeaddressimplementationconcernsandotherengineeringissuesWeoftenprovidepracticalalternativestothefewalgorithmsthatareprimarilyoftheoreticalinterestIfyouwishtoimplementanyofthealgorithms,youshouldfindthetranslationofourpseudocodeintoyourfavoriteprogramminglanguagetobeafairlystraightforwardtaskWehavedesignedthepseudocodetopresenteachalgorithmclearlyandsuccinctlyConsequently,wedonotaddresserrorhandlingandothersoftwareengineeringissuesthatrequirespecificassumptionsaboutyourprogrammingenvironmentWeattempttopresenteachalgorithmsimplyanddirectlywithoutallowingtheidiosyncrasiesofaparticularprogramminglanguagetoobscureitsessenceWeunderstandthatifyouareusingthisbookoutsideofacourse,thenyoumightbeunabletocheckyoursolutionstoproblemsandexercisesagainstsolutionsprovidedbyaninstructorOurWebsite,http:mitpressmitedualgorithms,linkstosolutionsforsomeoftheproblemsandexercisessothatyoucancheckyourworkPleasedonotsendyoursolutionstousToourcolleaguesWehavesuppliedanextensivebibliographyandpointerstothecurrentliteratureEachchapterendswithasetofchapternotesthatgivehistoricaldetailsandreferencesThechapternotesdonotprovideacompletereferencetothewholefieldxviPrefaceofalgorithms,howeverThoughitmaybehardtobelieveforabookofthissize,spaceconstraintspreventedusfromincludingmanyinterestingalgorithmsDespitemyriadrequestsfromstudentsforsolutionstoproblemsandexercises,wehavechosenasamatterofpolicynottosupplyreferencesforproblemsandexercises,toremovethetemptationforstudentstolookupasolutionratherthantofinditthemselvesChangesforthethirdeditionWhathaschangedbetweenthesecondandthirdeditionsofthisbookThemagnitudeofthechangesisonaparwiththechangesbetweenthefirstandsecondeditionsAswesaidaboutthesecondeditionchanges,dependingonhowyoulookatit,thebookchangedeithernotmuchorquiteabitAquicklookatthetableofcontentsshowsthatmostofthesecondeditionchaptersandsectionsappearinthethirdeditionWeremovedtwochaptersandonesection,butwehaveaddedthreenewchaptersandtwonewsectionsapartfromthesenewchaptersWekeptthehybridorganizationfromthefirsttwoeditionsRatherthanorganizingchaptersbyonlyproblemdomainsoraccordingonlytotechniques,thisbookhaselementsofbothItcontainstechniquebasedchaptersondivideandconquer,dynamicprogramming,greedyalgorithms,amortizedanalysis,NPCompleteness,andapproximationalgorithmsButitalsohasentirepartsonsorting,ondatastructuresfordynamicsets,andonalgorithmsforgraphproblemsWefindthatalthoughyouneedtoknowhowtoapplytechniquesfordesigningandanalyzingalgorithms,problemsseldomannouncetoyouwhichtechniquesaremostamenabletosolvingthemHereisasummaryofthemostsignificantchangesforthethirdedition:WeaddednewchaptersonvanEmdeBoastreesandmultithreadedalgorithms,andwehavebrokenoutmaterialonmatrixbasicsintoitsownappendixchapterWerevisedthechapteronrecurrencestomorebroadlycoverthedivideandconquertechnique,anditsfirsttwosectionsapplydivideandconquertosolvetwoproblemsThesecondsectionofthischapterpresentsStrassen’salgorithmformatrixmultiplication,whichwehavemovedfromthechapteronmatrixoperationsWeremovedtwochaptersthatwererarelytaught:binomialheapsandsortingnetworksOnekeyideainthesortingnetworkschapter,theprinciple,appearsinthiseditionwithinProblemasthesortinglemmaforcompareexchangealgorithmsThetreatmentofFibonacciheapsnolongerreliesonbinomialheapsasaprecursorPrefacexviiWerevisedourtreatmentofdynamicprogrammingandgreedyalgorithmsDynamicprogrammingnowleadsoffwithamoreinterestingproblem,rodcutting,thantheassemblylineschedulingproblemfromthesecondeditionFurthermore,weemphasizememoizationabitmorethanwedidinthesecondedition,andweintroducethenotionofthesubproblemgraphasawaytounderstandtherunningtimeofadynamicprogrammingalgorithmInouropeningexampleofgreedyalgorithms,theactivityselectionproblem,wegettothegreedyalgorithmmoredirectlythanwedidinthesecondeditionThewaywedeleteanodefrombinarysearchtrees(whichincludesredblacktrees)nowguaranteesthatthenoderequestedfordeletionisthenodethatisactuallydeletedInthefirsttwoeditions,incertaincases,someothernodewouldbedeleted,withitscontentsmovingintothenodepassedtothedeletionprocedureWithournewwaytodeletenodes,ifothercomponentsofaprogrammaintainpointerstonodesinthetree,theywillnotmistakenlyendupwithstalepointerstonodesthathavebeendeletedThematerialonflownetworksnowbasesflowsentirelyonedgesThisapproachismoreintuitivethanthenetflowusedinthefirsttwoeditionsWiththematerialonmatrixbasicsandStrassen’salgorithmmovedtootherchapters,thechapteronmatrixoperationsissmallerthaninthesecondeditionWehavemodifiedourtreatmentoftheKnuthMorrisPrattstringmatchingalgorithmWecorrectedseveralerrorsMostoftheseerrorswerepostedonourWebsiteofsecondeditionerrata,butafewwerenotBasedonmanyrequests,wechangedthesyntax(asitwere)ofourpseudocodeWenowuse“D”toindicateassi