资源描述：
《mit算法分析与设计lecture_01》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、IntroductiontoAlgorithms6.046J/18.401JLECTURE1AnalysisofAlgorithms•Insertionsort•MergesortProf.CharlesE.LeisersonCourseinformation1.Staff7.Extrahelp2.Prerequisites8.Registration3.Lectures9.Problemsets4.Recitations10.Describingalgorithms5.Handouts11.Gr
2、adingpolicy6.Textbook(CLRS)12.Collaborationpolicy¾Courseinformationhandout©2001–4byCharlesE.LeisersonSeptember8,2004IntroductiontoAlgorithmsL1.2AnalysisofalgorithmsThetheoreticalstudyofcomputer-programperformanceandresourceusage.What’smoreimportanttha
3、nperformance?•modularity•user-friendliness•correctness•programmertime•maintainability•simplicity•functionality•extensibility•robustness•reliability©2001–4byCharlesE.LeisersonSeptember8,2004IntroductiontoAlgorithmsL1.3Whystudyalgorithmsandperformance?•
4、Algorithmshelpustounderstandscalability.•Performanceoftendrawsthelinebetweenwhatisfeasibleandwhatisimpossible.•Algorithmicmathematicsprovidesalanguagefortalkingaboutprogrambehavior.•Performanceisthecurrencyofcomputing.•Thelessonsofprogramperformancege
5、neralizetoothercomputingresources.•Speedisfun!©2001–4byCharlesE.LeisersonSeptember8,2004IntroductiontoAlgorithmsL1.4TheproblemofsortingInput:sequence〈a,a,…,a〉ofnumbers.12nOutput:permutation〈a',a',…,a'〉such12nthata'≤a'≤…≤a'.12nExample:Input:824936Outpu
6、t:234689©2001–4byCharlesE.LeisersonSeptember8,2004IntroductiontoAlgorithmsL1.5InsertionsortINSERTION-SORT(A,n)⊳A[1..n]forj←2tondokey←A[j]i←j–1“pseudocode”whilei>0andA[i]>keydoA[i+1]←A[i]i←i–1A[i+1]=key©2001–4byCharlesE.LeisersonSeptember8,2004Introduc
7、tiontoAlgorithmsL1.6InsertionsortINSERTION-SORT(A,n)⊳A[1..n]forj←2tondokey←A[j]i←j–1“pseudocode”whilei>0andA[i]>keydoA[i+1]←A[i]i←i–1A[i+1]=key1ijnA:keysorted©2001–4byCharlesE.LeisersonSeptember8,2004IntroductiontoAlgorithmsL1.7Exampleofinsertionsort8
8、24936©2001–4byCharlesE.LeisersonSeptember8,2004IntroductiontoAlgorithmsL1.8Exampleofinsertionsort824936©2001–4byCharlesE.LeisersonSeptember8,2004IntroductiontoAlgorithmsL1.9Exampleofinsertionsort824936©2001–4byCharlesE.LeisersonSeptember8,2004
