资源描述:
《everything you wanted to know about the running time of mergesort but were afraid to ask》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、EverythingYouWantedtoKnowAbouttheRunningTimeofMergesortButWereAfraidtoAskyIanParberryDepartmentofComputerSciencesUniversityofNorthTexasFebruary3,1998AbstractAlthoughmergesortisanalgorithmthatisfrequentlyglossedoverintextbooks,itprovidesfertilegroundforplantingideasaboutalgorithmanalysis
2、inthemindsofstudents.Alltooeasilywecanfallintothetrapofassumingnisapowerof2inouranalyses,whichcanbefuddlebeginningstudentsintothinkingthatourresultsareuselessinpractice.Herethenisanexcruciatinglydetailedanalysisofmergesortforthestudentwhoseenquiringmindtrulywantstoknow.1IntroductionMerge
3、sortisasortingalgorithmthatrunsinO(nlogn)timeintheworstcase.Wewillanalyzetherunningtimeandnumberofcomparisonsusedbymergesort,demonstratingseveraltechniquesthatcanbeusedtondgoodapproximatesolutionstorecurrencerelationsthathave
oorsandceilingsinthem.Theremainderofthismanuscriptisdividedin
4、tofoursections.InSection2wemeetthealgorithm,andthefundamentaloperation"methodofanalysis:insteadofusingbig-Osallthroughtheanalysis,ndthefundamentaloperationwhichisdenedinformallytobethepartofthealgorithmwheretheactualworkisdone,meaningthattherunningtimeofthealgorithmisbig-Oofthenumbero
5、ffundamentaloperationsused.InSection3wemeetthestandardassumenisapowerof2"analysisofthenumberofcomparisonsusedbymergesort,andconsiderhowcloseitcomestoapproximatingtherealsolution.Then,inSection4wetakeotheglovesandattackthemergesortrecurrencerelationwith
oorsandceilings,endingupwithabett
6、erapproximation.FinallySection5givesaclosedformsolutionforthenumberofcomparisonsusedbymergesort,andwecanseeinretrospecthowclosewecamewithourvariousapproximations.2TheAlgorithmConsiderthefollowingalgorithmforsortingalistLofelementsfromatotallyorderedset:dividethelistasevenlyaspossibleinto
7、twosublistsLandL,sorteachofLandLrecursively,and1212thenmergethemtogether.c1998,IanParberry.yAuthor'saddress:Dept.ofComputerSciences,Univ.ofNorthTexas,P.O.Box13886,Denton,TX76203{1366,U.S.A.Email:ian@cs.unt.edu.URL:http://hercule.csci.unt.edu/ian.1functionmergesort(L;n)co