《算法导论概要课件》由会员分享，可在线阅读，更多相关《算法导论概要课件（21页珍藏版）》请在金锄头文库上搜索。
1、算法导论第一课算法分析算法分析插入排序渐进分析合并排序递归翻译：今天在这个地方申明MIT的版权Prof. Charles E. Leiserson Copyright 2001-5 Erik D. Demaine and Charles E. Leiserson课程信息1.工作人员工作人员2.远程学习远程学习3.预备知识预备知识4.讲义讲义5.口头问答口头问答6.上课资料上课资料7.课本课本8.课程网站课程网站9.额外帮助额外帮助10.课程注册课程注册11.习题集习题集12.描述算法描述算法13.评分方式评分方式14.合作规定合作规定算法分析计算机程序性能和资源使用的理论研究。什么比性能更重要
2、？什么比性能更重要？模块性正确性可维护性函数性健壮性用户友好性程序员的时间简单性可扩展性可靠性为什么研究算法和性能？为什么研究算法和性能？算法有助于我们理解可量测性。性能经常在可行和重要之间划下最后的界限。算法的数学描述为讨论程序的行为提供一种语言。性能是计算所通行的。程序性能的课程概括为另一些计算资源。高速是有趣的。排序的问题输入：数字序列a1, a2, , an输出：置换a1, a2, , an使得a1a2an例如：输入：8 2 4 9 3 6输出输出: 2 3 4 6 8 9插入排序伪代码插入排序 (A, n)A1 . . nFor j 2 to n Do key A j i j 1 W
3、hile i 0 and Ai key Do Ai+1 Ai i i 1 Ai+1 = key“插入排序举例 8 2 4 9 3 6插入排序举例运行时间运行时间依赖于输入：已经排好序的序列更容易排序。通过输入规模量化运行时间：因为规模小的序列比规模大 的序列更容易排序。通常，我们寻找运行时间的上限，因为它是一种保证。分析的类型最坏情况最坏情况: (经常经常)T(n) =在任何输入规模n的情况下算法的最大时间.平均情况平均情况: (有时有时)T(n) =期望n输入规模的算法时间.需要假定输入规模的统计分布.最好情况最好情况: (不正确的不正确的)把一种缓慢执行的算法欺骗为某种输入规模上快速执行的
4、算法。与机器无关的时间插入排序最坏情况的时间是什么？它依赖于我们计算机的速度。 相对速度（在同一台机器上） 绝对速度（在不同的机器上）好的建议忽略与机器相关的常数。考虑当n时，T(n)的增长率。September 7, 2005 Introduction to Algorithms L1.22 Copyright 2001-5 Erik D. Demaine and Charles E. Leiserson 符号符号Math:(g(n) = f (n):这里存在整数这里存在整数c1, c2，n0使得使得 0 c1 g(n) f (n) c2 g(n)对于所有的对于所有的nn0工程学工程学:丢弃
5、低阶项; 忽略主要的常数例如: 3n3 + 90n25n+ 6046 = (n3)渐近性能渐近性能当n足够大时，(n2)的算法性能总是优于(n3)我们不应该忽略渐进缓慢的算法。现实生活的设计情形经常要求准确的工程目标平衡。渐进分析是一种有助于我们组织思考的有效工具。插入排序分析插入排序分析插入排序是最快的排序算法吗？ 对于n比较小时，速度适中。 对于n比较大时，速度比较慢。合并排序合并排序合并排序A1 . . n 1.If n= 1, done. 2.递归排序递归排序A 1 . . n/2 and A n/2 +1 . . n . 3.“合并合并”两个排好序的列表两个排好序的列表.关键子程序关键子程序:合并子程序合并子程序合并两个排好序的数组合并排序分析合并排序的递归T(n) =(1) if n= 1; 2T(n/2)+ (n) if n 1。我们通常省略说明基本的情况，对于n足够小时，T(n) = (1)，但只有当它对递归的渐进解决方法没有影响时。课本和在第二课中提供几种找出T(n)上限的好方法。递归树结论(n lg n)的增长比(n2)慢.因此，在最坏的情况下，合并排序的渐进性能比插入排序优。在实践中，对于n30时，合并排序优于插入排序。
