算法导论-课后题答案

算法导论-课后题答案

ID:20765426

大小:986.44 KB

页数:26页

时间:2018-10-15

算法导论-课后题答案_第1页
算法导论-课后题答案_第2页
算法导论-课后题答案_第3页
算法导论-课后题答案_第4页
算法导论-课后题答案_第5页
资源描述:

《算法导论-课后题答案》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、PartialSolutionsforIntroductiontoalgorithmssecondeditionProfessor:SongYouTA:ShaoWenACKNOWLEDGEMENTCLASSONE:JINZICLASSTWO:LIUHAO,SONGDINMIN,SUNBOSHAN,SUNYANGCLASSFOUR:DONGYANHAO,FANSHENGBO,LULU,XIAODONG,CLASSFIVE:GAOCHEN,WANGXIAOCHUAN,LIUZHENHUA,WANGJIA

2、N,YINGYINGCLASSSIX:ZHANGZHAOYU,XUXIAOPENG,PENGYUN,HOULANCLASS:LIKANG,JIANGZHOU,ANONYMITYThecollatorofthisAnswerSet,SHAOWen,takesabsolutelynoresponsibilityforthecontents.ThisismerelyavaguesuggestiontoasolutiontosomeoftheexercisesposedinthebookIntroducti

3、ontoalgorithmsbyCormen,LeisersonandRivest.Itisverylikelythattherearemanyerrorsandthatthesolutionsarewrong.Ifyouhavefoundanerror,haveabettersolutionorwishtocontributeinsomeconstructivewaypleasesendanEmailtoshao_wen_buaa@163.comItisimportantthatyoutryhar

4、dtosolvetheexercisesonyourown.Usethisdocumentonlyasalastresortortocheckifyourinstructorgotitallwrong.Havefunwithyouralgorithmsandgetasatisfactoryresultinthiscourse.Bestregards,SHAOWenChapteroneExercises1.1-2Otherthanspeed,whatothermeasuresofefficiencym

5、ightoneuseinareal-worldsetting?空间,硬件资源等Exercises1.1-4(classtwo刘浩)Howaretheshortest-pathandtraveling-salesmanproblemsgivenabovesimilar?Howaretheydifferent?相似点:找出最短路径不同点:shortest-path不一定经过所有点,而traveling-salesman得经过所有点Exercises1.2-2Supposewearecomparingim

6、plementationsofinsertionsortandmergesortonthesamemachine.Forinputsofsizen,insertionsortrunsin8n2steps,whilemergesortrunsin64nlgnsteps.Forwhichvaluesofndoesinsertionsortbeatmergesort?插入排序的性能优于合并排序也就是:插入排序所用的步数少:所以有:8n2≤64nlgn⇒n<8??n需要解一下这个超越方程,编个程序很容易得到

7、:2≤n≤43Exercises1.2-3Whatisthesmallestvalueofnsuchthatanalgorithmwhoserunningtimeis100n2runsfasterthananalgorithmwhoserunningtimeis2nonthesamemachine?原理同上题,可列出如下不等式:100n2≤2n解这个不等式(代数法),可求出最小的整数n=15Problems1-1:ComparisonofrunningtimesForeachfunctionf(n)

8、andtimetinthefollowingtable,determinethelargestsizenofaproblemthatcanbesolvedintimet,assumingthatthealgorithmtosolvetheproblemtakesf(n)microseconds.1111111secondminutehourdaymonthyearcenturylgn210626·107236·108∞∞∞∞12361416n10·101296·10∞

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。