欢迎来到天天文库
浏览记录
ID：39205689
大小：235.81 KB
页数：51页
时间：2019-06-27
《算法导论习题解答 solution to CLR 英文文献资料》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
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=84、nsortforinputofsize43orlessinordertoimprovetherunningtime.1-1Weassumethatallmonthsare30daysandallyearsare365.1111111secondminutehourdaymonthyearcentury1066107361088641082592109946081010946081012lgn2222222p12141616182024n103610129610746496106718464108950673664108950673665、410678891012n1061036108641025921094608109460810nlgn627462801417??????????234n102449489761029393816099683075841330758413432n10391153244201373698169455661n219253136414956n!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,allpropertiesarefulllledbythisloopinva7、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]endforAsa8、loopinvariantwechoosethatA[1;:::;
4、nsortforinputofsize43orlessinordertoimprovetherunningtime.1-1Weassumethatallmonthsare30daysandallyearsare365.1111111secondminutehourdaymonthyearcentury1066107361088641082592109946081010946081012lgn2222222p12141616182024n10361012961074649610671846410895067366410895067366
5、410678891012n1061036108641025921094608109460810nlgn627462801417??????????234n102449489761029393816099683075841330758413432n10391153244201373698169455661n219253136414956n!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,allpropertiesarefulllledbythisloopinva7、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]endforAsa8、loopinvariantwechoosethatA[1;:::;
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;:::;
此文档下载收益归作者所有
