算法导论第三版答案

SelectedSolutionsforChapter2:GettingStartedSolutiontoExercise2.2-2SELECTION-SORT.A/nDA:lengthforjD1ton1smallestDjforiDjC1tonifAŒiAŒsmallestsmallestDiexchangeAŒjwithAŒsmallestThealgorithmmaintainstheloopinvariantthatatthestartofeachiterationoftheouterforloop,thesubarrayAŒ1::j1consistsofthej1smallestelementsinthearrayAŒ1::n,andthissubarrayisinsortedorder.Afterthefirstn1elements,thesubarrayAŒ1::n1containsthesmallestn1elements,sorted,andthereforeelementAŒnmustbethelargestelement.Therunningtimeofthealgorithmis‚.n2/forallcases.SolutiontoExercise2.2-4Modifythealgorithmsoittestswhethertheinputsatisfiessomespecial-casecon-ditionand,ifitdoes,outputapre-computedanswer.Thebest-caserunningtimeisgenerallynotagoodmeasureofanalgorithm.SolutiontoExercise2.3-5ProcedureBINARY-SEARCHtakesasortedarrayA,avalue,andarangeŒlow::highofthearray,inwhichwesearchforthevalue.Theprocedurecom-parestothearrayentryatthemidpointoftherangeanddecidestoeliminatehalftherangefromfurtherconsideration.Wegivebothiterativeandrecursiveversions,eachofwhichreturnseitheranindexisuchthatAŒiD,orNILifnoentryof2-2SelectedSolutionsforChapter2:GettingStartedAŒlow::highcontainsthevalue.TheinitialcalltoeitherversionshouldhavetheparametersA;;1;n.ITERATIVE-BINARY-SEARCH.A;;low;high/whilelowhighmidDb.lowChigh/=2cif==AŒmidreturnmidelseifAŒmidlowDmidC1elsehighDmid1returnNILRECURSIVE-BINARY-SEARCH.A;;low;high/iflowhighreturnNILmidDb.lowChigh/=2cif==AŒmidreturnmidelseifAŒmidreturnRECURSIVE-BINARY-SEARCH.A;;midC1;high/elsereturnRECURSIVE-BINARY-SEARCH.A;;low;mid1/Bothproceduresterminatethesearchunsuccessfullywhentherangeisempty(i.e.,lowhigh)andterminateitsuccessfullyifthevaluehasbeenfound.Basedonthecomparisonoftothemiddleelementinthesearchedrange,thesearchcontinueswiththerangehalved.TherecurrencefortheseproceduresisthereforeT.n/DT.n=2/C‚.1/,whosesolutionisT.n/D‚.lgn/.SolutiontoProblem2-4a.Theinversionsare.1;5/;.2;5/;.3;4/;.3;5/;.4;5/.(Rememberthatinversionsarespecifiedbyindicesratherthanbythevaluesinthearray.)b.Thearraywithelementsfromf1;2;:::;ngwiththemostinversionsishn;n1;n2;:::;2;1i.Forall1ijn,thereisaninversion.i;j/.Thenumberofsuchinversionsisn2
Dn.n1/=2.c.SupposethatthearrayAstartsoutwithaninversion.k;j/.ThenkjandAŒkAŒj.Atthetimethattheouterforloopoflines1–8setskeyDAŒj,thevaluethatstartedinAŒkisstillsomewheretotheleftofAŒj.Thatis,it’sinAŒi,where1ij,andsotheinversionhasbecome.i;j/.Someiterationofthewhileloopoflines5–7movesAŒionepositiontotheright.Line8willeventuallydropkeytotheleftofthiselement,thuseliminatingtheinversion.Becauseline5movesonlyelementsthatarelessthankey,itmovesonlyelementsthatcorrespondtoinversions.Inotherwords,eachiterationofthewhileloopoflines5–7correspondstotheeliminationofoneinversion.SelectedSolutionsforChapter2:GettingStarted2-3d.Wefollowthehintandmodifymergesorttocountthenumberofinversionsin‚.nlgn/time.Tostart,letusdefineamerge-inversionasasituationwithintheexecutionofmergesortinwhichtheMERGEprocedure,aftercopyingAŒp::qtoLandAŒqC1::rtoR,hasvaluesxinLandyinRsuchthatxy.Consideraninversion.i;j/,andletxDAŒiandyDAŒj,sothatijandxy.Weclaimthatifweweretorunmergesort,therewouldbeexactlyonemerge-inversioninvolvingxandy.Toseewhy,observethattheonlywayinwhicharrayelementschangetheirpositionsiswithintheMERGEprocedure.More-over,sinceMERGEkeepselementswithinLinthesamerelativeordertoeachother,andcorrespondinglyforR,theonlywayinwhichtwoelementscanchangetheirorderingrelativetoeachotherisforthegreateronetoappearinLandthelesseronetoappearinR.Thus,thereisatleastonemerge-inversioninvolvingxandy.Toseethatthereisexactlyonesuchmerge-inversion,ob-servethatafteranycallofMERGEthatinvolvesbothxandy,theyareinthesamesortedsubarrayandwillthereforebothappearinLorbothappearinRinanygivencallthereafter.Thus,wehaveproventheclaim.Wehaveshownthateveryinversionimpliesonemerge-inversion.Infact,thecorrespondencebetweeninversionsandmerge-inversionsisone-to-one.Sup-posewehaveamerge-inversioninvolvingvaluesxandy,wherexoriginallywasAŒiandywasoriginallyAŒj.Sincewehaveamerge-inversion,xy.AndsincexisinLandyisinR,xmustbewithinasubarrayprecedingthesubarraycontainingy.Thereforexstartedoutinapositioniprecedingy’soriginalpositionj,andso.i;j/isaninversion.Havingshownaone-to-onecorrespondencebetweeninversionsandmerge-inversions,itsufficesforustocountmerge-inversions.Consideramerge-inversioninvolvingyinR.Let´bethesmallestvalueinLthatisgreaterthany.Atsomepointduringthemergingprocess,´andywillbethe“exposed”valuesinLandR,i.e.,wewillhave´DLŒiandyDRŒjinline13ofMERGE.Atthattime,therewillbemerge-inversionsinvolvingyandLŒi;LŒiC1;LŒiC2;:::;LŒn1,andthesen1iC1merge-inversionswillbetheonlyonesinvolvingy.Therefore,weneedtodetectthefirsttimethat´andybecomeexposedduringtheMERGEprocedureandaddthevalueofn1iC1atthattimetoourtotalcountofmerge-inversions.Thefollowingpseudocode,modeledonmergesort,worksaswehavejustde-scribed.ItalsosortsthearrayA.COUNT-INVERSIONS.A;p;r/inersionsD0ifprqDb.pCr/=2cinersionsDinersionsCCOUNT-INVERSIONS.A;p;q/inersion