算法导论(第二版)课后习题解答

SolutionsforIntroductiontoalgorithmssecondeditionPhilipBilleTheauthorofthisdocumenttakesabsolutelynoresponsibilityforthecontents.ThisismerelyavaguesuggestiontoasolutiontosomeoftheexercisesposedinthebookIntroductiontoalgo-rithmsbyCormen,LeisersonandRivest.Itisverylikelythattherearemanyerrorsandthatthesolutionsarewrong.Ifyouhavefoundanerror,haveabettersolutiono[e-mail]stresortortocheckifyourinstructorgotitallwrong.Pleasenotethatthedocumentisunderconstructionandisupdatedonlysporadically.Havefunwithyouralgorithms.Bestregards,PhilipBilleLastupdate:December9,20021:2-2Insertionsortbeatsmergesortwhen8n264nlgn,)n8lgn,)2n=8n.Thisistruefor26n643(foundbyusingacalculator).Rewritemergesorttouseinsertionsortforinputofsize43orlessinordertoimprovetherunningtime.1-1Weassumethatallmonthsare30daysandallyearsare365.1111111secondminutehourdaymonthyearcenturylgn210626
107236
1082864
10822592
109294608
1010294608
1012pn101236
10141296
1016746496
10166718464
10188950673664
10208950673664
1024n1066
10736
108864
1082592
10994608
101094608
1012nlgn627462801417??????????n2103244948976
104293938160996830758413307584134n31023911532442013736981694556612n19253136414956n!911121315171822:1-2Inline5ofINSERTION-SORTalterA[i]keytoA[i]keyinordertosorttheelementsinnonincreasingorder.2:1-3Algorithm1LINEAR-SEARCH(A;v)Input:A=ha1;a2;:::aniandavaluev.Output:Anindexisuchthatv=A[i]ornilifv62Afori1tondoifA[i]=vthenreturniendifendforreturnnilAsaloopinvariantwesaythatnoneoftheelementsatindexA[1;:::;i-1]areequaltov.Clearly,allpropertiesarefulllledbythisloopinvariant.2:2-1n3=1000-100n2-100n+3=(n3).2:2-2AssumethatFIND-MIN(A;r;s)returnstheindexofthesmallestelementinAbetweenindicesrands.Clearly,thiscanbeimplementedinO(s-r)timeifrs.Algorithm2SELECTION-SORT(A)Input:A=ha1;a2;:::aniOutput:sortedA.fori1ton-1dojFIND-MIN(A;i;n)A[j]$A[i]endforAsaloopinvariantwechoosethatA[1;:::;i-1]aresortedandallotherelementsaregreaterthanthese.Weonlyneedtoiterateton-1sinceaccordingtotheinvariantthenthelementwillthenthelargest.ThencallsofFIND-MINgivesthefollowingboundonthetimecomplexity:nXi=1i!=(n2)Thisholdsforboththebest-andworst-caserunningtime.2:2-3Giventhateachelementisequallylikelytobetheonesearchedforandtheelementsearchedforispresentinthearray,alinearsearchwillontheaveragehavetosearchthroughhalftheelements.Thisisbecausehalfthetimethewantedelementwillbeinthersthalfandhalfthetimeitwillbeinthesecondhalf.Boththeworst-caseandaverage-caseofLINEAR-SEARCHis(n).32:2-4Onecanmodifyanalgorithmtohaveabest-caserunningtimebyspecializingittohandleabest-caseinputefciently.2:3-5Arecursiveversionofbinarysearchonanarray.Clearly,theworst-caserunningtimeis(lgn).Algorithm3BINARY-SEARCH(A;v;p;r)Input:AsortedarrayAandavaluev.Output:Anindexisuchthatv=A[i]ornil.ifprandv6=A[p]thenreturnnilendifjA[b(r-p)=2c]ifv=A[j]thenreturnjelseifvA[j]thenreturnBINARY-SEARCH(A;v;p;j)elsereturnBINARY-SEARCH(A;v;j;r)endifendif2:3-7Givea(nlgn)timealgorithmfordeterminingifthereexisttwoelementsinansetSwhosesumisexactlysomevaluex.Algorithm4CHECKSUMS(A;x)Input:AnarrayAandavaluex.Output:AbooleanvalueindicatingifthereistwoelementsinAwhosesumisx.ASORT(A)nlength[A]foritondoifA[i]0andBINARY-SEARCH(A;A[i]-x;1;n)thenreturntrueendifendforreturnfalseClearly,thisalgorithmdoesthejob.(Itisassumedthatnilcannotbetrueintheif-statement.)43:1-1Letf(n),g(n)beasymptoticallynonnegative.Showthatmax(f(n);g(n))=(f(n)+g(n)).Thismeansthatthereexistspositiveconstantsc1,c2andn0suchthat,06c1(f(n)+g(n))6max(f(n);g(n))6c2(f(n)+g(n))forallnn0.Selectingc2=1clearlyshowsthethirdinequalitysincethemaximummustbesmallerthanthesum.c1shouldbeselectedas1=2sincethemaximumisalwaysgreaterthantheweightedaverageoff(n)andg(n).Notethesignicanceofthe“asymptoticallynonnegative”assumption.Therstinequalitycouldnotbesatisedotherwise.3:1-42n+1=O(2n)since2n+1=2
2n62
2n!However22nisnotO(2n):bydenitionwehave22n=(2n)2whichfornoconstantcasymptoticallymaybelessthanorequaltoc
2n.3-4Letf(n)andg(n)beasymptoticallypositivefunctions.a.No,f(n)=O(g(n))doesnotimplyg(n)=O(f(n)).Clearly,n=O(n2)butn26=O(n).b.No,f(n)+g(n)isnot(min(f(n);g(n))).Asanexamplenoticethatn+16=(min(n;1))=(1).c.Yes,iff(n)=O(g(n))thenlg(f(n))=O(lg(g(n)))providedthatf(n)1andlg(g(n))1aregreaterthanorequal1.Wehavethat:f(n)6cg(n))lgf(n)6lg(cg(n))=lgc+lgg(n)Toshowthatthisissmallerthanblgg(n)forsomeconstantbwesetlgc+lgg(n)=blgg(n).Dividingbylgg(n)yields:b=lg(c)+lgg(n)lgg(n)=lgclgg(n)+16lgc+1Thelastinequalityholdssincelgg(n)1.d.No,f(n)=O(g(n))doesnotimply2f(n)=O(2g(n)).Iff(n)=2nandg(n)=nwehavethat2n62
nbutnot22n6c2nforanyconstantcbyexercise3:1-4.e.Yesandno,iff(n)1forlargenthenf(n)2f(n)andtheupperboundwillnothold.Otherwisef(n)1andthestatementistriviallytrue.f.Yes,f(n)=O(g(n))impliesg(n)=(f(n)).Wehavef(n)6cg(n)forpositivecandthus1=c
f(n)6g(n).g.No,clearly2n66c2n=2=cp2nforanyconstantcifnissufcientlylarge.h.Byasmallmodicationtoexercise3:1-1wehavethatf(n)+o(f(n))