Chapter7
MichelleBodnar,AndrewLohr
April12,2016
Exercise7.1-1
13131399999999991991991991913513513585858585858585555191919777777121212121212121244444888888131313132227777777191919196644444444121212121121221221221221221221221221221221132113211366666666666191911111111111111111111111112Exercise7.1-2
Ifallelementsinthearrayhavethesamevalue,PARTITIONreturnsr.TomakePARTITIONreturnq=??(p+r)/2??whenallelementshavethesamevalue,modifyline4ofthealgorithmtosaythis:ifA[j]≤xandj(mod2)=(p+1)(mod2).Thiscausesthealgorithmtotreathalfoftheinstancesofthesamevaluetocountaslessthan,andtheotherhalftocountasgreaterthan.Exercise7.1-3
Theforloopmakesexactlyr?piterations,eachofwhichtakesatmostconstanttime.Thepartoutsidetheforlooptakesatmostconstanttime.Sincer?pisthesizeofthesubarray,PARTITIONtakesatmosttimeproportionaltothesizeofthesubarrayitiscalledon.Exercise7.1-4
TomodifyQUICKSORTtoruninnon-increasingorderweneedonlymodifyline4ofPARTITION,changing≤to≥.
1
Exercise7.2-1
Byde?nitionofΘ,weknowthatthereexistsc1,c2sothattheΘ(n)termisbetweenc1nandc2n.Wemakethatinductivehypothesisbethatc1m2≤T(m)≤c2m2forallm c1n2≤c1(n?1)2+c1n≤T(n?1)+Θ(n)=T(n)=T(n?1)+Θ(n)≤c2(n?1)2+c2n≤c2n2 Exercise7.2-2 TherunningtimeofQUICKSORTonanarrayinwhicheveyelementhasthesamevalueisn2.Thisisbecausethepartitionwillalwaysoccuratthelastpo-sitionofthearray(Exercise7.1-2)sothealgorithmexhibitsworst-casebehavior.Exercise7.2-3 Ifthearrayisalreadysortedindecreasingorder,then,thepivotelementislessthanalltheotherelements.ThepartitionsteptakesΘ(n)time,andthenleavesyouwithasubproblemofsizen?1andasubproblemofsize0.Thisgivesustherecurrenceconsideredin7.2-1.WhichweshowedhasasolutionthatisΘ(n2).Exercise7.2-4 Let’ssaythatby“almostsorted”wemeanthatA[i]isatmostcpositionsfromitscorrectplaceinthesortedarray,forsomeconstantc.ForINSERTION-SORT,weruntheinner-whileloopatmostctimesbeforewe?ndwheretoinsertA[j]foranyparticulariterationoftheouterforloop.ThustherunningtimetimeisO(cn)=O(n),sincecis?xedinadvance.NowsupposewerunQUICK-SORT.ThesplitofPARTITIONwillbeatbestn?ctoc,whichleadstoO(n2)runningtime.Exercise7.2-5 Theminimumdepthcorrespondstorepeatedlytakingthesmallersubprob-lem,thatis,thebranchwhosesizeisproportionaltoα.Then,thiswillfallto lg(n) 1inkstepswhere1≈(α)kn.So,k≈logα(1/n)=?lg(α).Thelongestdepthcorrespondstoalwaystakingthelargersubproblem.wethenhaveandidenticalexpression,replacingαwith1?α.Exercise7.2-6 2 Withoutlossofgenerality,assumethattheentriesoftheinputarrayaredistinct.Sinceonlytherelativesizesoftheentriesmatter,wemayassumethatAcontainsarandompermutationofthenumbers1throughn.Now?x0<α≤1/2.LetkdenotethenumberofentriesofAwhicharelessthanA[n].PARTITIONproducesasplitmorebalancedthan1?αtoαifand ?αn+1 =onlyifαn≤k≤(1?α)n.Thishappenswithprobability(1?α)nn1?2α+1/n≈1?2α.Exercise7.3-1 Weanalyzetheexpectedruntimebecauseitrepresentsthemoretypicaltimecost.Also,wearedoingtheexpectedruntimeoverthepossiblerandom-nessusedduringcomputationbecauseitcan’tbeproducedadversarially,unlikewhendoingexpectedruntimeoverallpossibleinputstothealgorithm.Exercise7.3-2 Intheworstcase,RANDOMreturnstheindexofthelargestelementeachtimeit’scalled,soΘ(n)callsaremade.Inthebestcase,RANDOMreturnstheindexoftheelementinthemiddleofthearrayandthearrayhasdistinctelements,soΘ(lgn)callsaremade.Exercise7.4-1 Byde?nitionofΘ,weknowthatthereexistsc1,c2sothattheΘ(n)termisbetweenc1nandc2n.Wemakethatinductivehypothesisbethatc1m2≤T(m)≤c2m2forallm c1n2≤c1maxn2?2n(q+2)+(q+1)2+(q+1)2+n q∈[n] =maxc1(n?q?2)2+c1(q+1)2+c1n q∈[n] ≤maxT(n?q?2)+T(q+1)+Θ(n) q∈[n] =T(n) SimilarlyfortheotherdirectionExercise7.4-2 We’llusethesubstitutionmethodtoshowthatthebest-caserunningtimeis?(nlgn).LetT(n)bethebest-casetimefortheprocedureQUICKSORTonaninputofsizen.Wehavetherecurrence T(n)= 1≤q≤n?1 min(T(q)+T(n?q?1))+Θ(n). SupposethatT(n)≥c(nlgn+2n)forsomeconstantc.Substitutingthisguess 3 intotherecurrencegivesT(n)≥ = 1≤q≤n?1 min(cqlgq+2cq+c(n?q?1)lg(n?q?1)+2c(n?q?1))+Θ(n) cn lg(n/2)+cn+c(n/2?1)lg(n/2?1)+cn?2c+Θ(n)2 ≥(cn/2)lgn?cn/2+c(n/2?1)(lgn?2)+2cn?2cΘ(n)=(cn/2)lgn?cn/2+(cn/2)lgn?cn?lgn+2+2cn?2cΘ(n)=cnlgn+cn/2?lgn+2?2c+Θ(n) Takingaderivativewithrespecttoqshowsthattheminimumisobtainedwhenq=n/2.Takingclargeenoughtodominatethe?lgn+2?2c+Θ(n)termmakesthisgreaterthancnlgn,provingthebound.Exercise7.4-3 Wewilltreatthegivenexpressiontobecontinuousinq,andthen,anyex-tremalvaluesmustbeeitheradjacenttoacriticalpoint,oroneoftheendpoints.Thesecondderivativewithrespecttoqis4,So,wehavethatanycriticalpointswe?ndwillbeminima.Theexpressionhasaderivativewithrespecttoqof2q?2(n?q?2)=?2n+4q+4whichiszerowhenwehave2q+2=n.So, 2 therewillbeaminimaatq=n?2.So,themaximalvaluesmustonlybetheendpoints.Wecanseethattheendpointsareequallylargebecauseatq=0,itis(n?1)2,andatq=n?1,itis(n?1)2+(n?n+1?1)2=(n?1)2.Exercise7.4-4 We’llusethelowerbound(A.13)fortheexpectedrunningtimegiveninthesection: E[X]= n?1?? 2 j?i+1i=1j=i+1 2k n?? =≥ n?in?1????i=1k=1n?1??i=1 2ln(n?i+1)??n?1?? i=1 ?? n?i+1 =2ln =2ln(n!) 2=lg(n!)lge≥cnlgn forsomeconstantcsincelg(n!)=Θ(nlgn)byExercise3.2-3.ThereforeRANDOMIZED-QUICKSORT’sexpectedrunningtimeis?(nlgn). 4 Exercise7.4-5 Ifweareonlydoingquick-sortuntiltheproblemsizebecomes≤k,then,wewillhavetotakelg(n/k)steps,since,asintheoriginalanalysisofrandomizedquicksort,weexpecttheretobelg(n)levelstotherecursiontree.Sincewethenjustcallquicksortontheentirearray,weknowthateachelementiswithinkofits?nalposition.Thismeansthataninsertionsortwilltaketheshiftingofatmostkelementsforeveryelementthatneededtochangeposition.Thisgetsustherunningtimedescribed. Intheory,weshouldpickktominimizethisexpression,thatis,takingaderivativewithrespecttok,wewantittobeevaluatingtozero.So,n?nk=0,1 sok～n2.Theconstantofproportionalitywilldependontherelativesizeoftheconstantsinthenktermandinthenlg(n/k)term.Inpractice,wewouldtryitwithalargenumberofinputsizesforvariousvaluesofk,becausetherearegrittypropertiesofthemachinenotconsideredheresuchascachelinesize.Exercise7.4-6 Forsimplicityofanalysis,wewillassumethattheelementsofthearrayAarethenumbers1ton.Ifweletkdenotethemedianvalue,theprobabilityofgettingatworstanαto1?αsplitistheprobabilitythatαn≤k≤(1?α)n.Thenumberof“bad”triplesisequaltothenumberoftriplessuchthatatleasttwoofthenumberscomefrom[1,αn]oratleasttwoofthenumberscomefrom[(1?α)n,n].Sincebothintervalshavethesamesize,theprobabilityofabadtripleis2(α3+3α2(1?α)).Thustheprobabilityofselectinga“good”triple,andthusgettingatworstanαto1?αsplit,is1?2(α3+3α2(1?α))=1+4α3?6α2.Problem7-1 a.Wewillbecallingwiththeparametersp=1,r=|A|=12.So,throughout,x=13. ij13199512874112621013619951287411213211116139512874112192121061395128741121921102Andwedoindeedseethatpartitionhasmovedthetwoelementsthatarebiggerthanthepivot,19and21,tothetwo?nalpositionsinthearray.b.Weknowthatatthebeginningoftheloop,wehavethati 5
算法导论 答案 Ch7
