算法導(dǎo)論習(xí)題解答 solution to CLR 英文文獻(xiàn)資料

《算法導(dǎo)論習(xí)題解答 solution to CLR 英文文獻(xiàn)資料》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、SolutionsforIntroductiontoalgorithmssecondeditionPhilipBilleTheauthorofthisdocumenttakesabsolutelynoresponsibilityforthecontents.ThisismerelyavaguesuggestiontoasolutiontosomeoftheexercisesposedinthebookIntroductiontoalgo-rithmsbyCormen,LeisersonandRivest.Itisverylikelythatthereare

2、manyerrorsandthatthesolutionsarewrong.Ifyouhavefoundanerror,haveabettersolutionorwishtocontributeinsomeconstructivewaypleasesendamessagetobeetle@it.dk.Itisimportantthatyoutryhardtosolvetheexercisesonyourown.Usethisdocumentonlyasalastresortortocheckifyourinstructorgotitallwrong.Ple

3、asenotethatthedocumentisunderconstructionandisupdatedonlysporadically.Havefunwithyouralgorithms.Bestregards,PhilipBilleLastupdate:December9,20021:2-2Insertionsortbeatsmergesortwhen8n2<64nlgn,)n<8lgn,)2n=8

4、nsortforinputofsize43orlessinordertoimprovetherunningtime.1-1Weassumethatallmonthsare30daysandallyearsare365.1111111secondminutehourdaymonthyearcentury1066
10736
108864
1082592
10994608
101094608
1012lgn2222222p12141616182024n1036
101296
10746496
106718464
108950673664
10895067366

5、4
10678891012n106
1036
10864
102592
1094608
1094608
10nlgn627462801417??????????234n10244948976
1029393816099683075841330758413432n10391153244201373698169455661n219253136414956n!911121315171822:1-2Inline5ofINSERTION-SORTalterA[i]>keytoA[i]

6、gorder.2:1-3Algorithm1LINEAR-SEARCH(A;v)Input:A=ha1;a2;:::aniandavaluev.Output:Anindexisuchthatv=A[i]ornilifv62Afori1tondoifA[i]=vthenreturniendifendforreturnnilAsaloopinvariantwesaythatnoneoftheelementsatindexA[1;:::;i-1]areequaltov.Clearly,allpropertiesarefulllledbythisloopinva

7、riant.2:2-1n3=1000-100n2-100n+3=(n3).2:2-2AssumethatFIND-MIN(A;r;s)returnstheindexofthesmallestelementinAbetweenindicesrands.Clearly,thiscanbeimplementedinO(s-r)timeifr>s.Algorithm2SELECTION-SORT(A)Input:A=ha1;a2;:::aniOutput:sortedA.fori1ton-1dojFIND-MIN(A;i;n)A[j]$A[i]endforAsa

8、loopinvariantwechoosethatA[1;:::;