算法导论概要课件

算法导论第一课算法分析插入排序渐进分析合并排序递归翻译：今天在这个地方申明MIT的版权Prof.CharlesE.LeisersonCopyright©2001-5ErikD.DemaineandCharlesE.Leiserson算法导论第一课课程信息1.工作人员2.远程学习3.预备知识4.讲义5.口头问答6.上课资料7.课本8.课程网站9.额外帮助10.课程注册11.习题集12.描述算法13.评分方式14.合作规定课程信息1.工作人员8.课程网站算法分析

计算机程序性能和资源使用的理论研究。

什么比性能更重要？

模块性正确性可维护性函数性健壮性用户友好性程序员的时间简单性可扩展性可靠性算法分析

计算机程序性能和资源使用的理论研究。

什么比性为什么研究算法和性能？算法有助于我们理解可量测性。性能经常在可行和重要之间划下最后的界限。算法的数学描述为讨论程序的行为提供一种语言。性能是计算所通行的。程序性能的课程概括为另一些计算资源。高速是有趣的。为什么研究算法和性能？算法有助于我们理解可量测性。排序的问题输入：数字序列〈a1,a2,…,an〉输出：置换〈a‘1,a’2,…,a‘n〉使得a'1≤a'2≤…≤a'n例如：输入：824936输出:234689排序的问题输入：数字序列〈a1,a2,…,an〉插入排序伪代码插入排序(A,n)⊳A[1..n]Forj←2tonDokey←A[j]i←j–1Whilei>0andA[i]>keyDoA[i+1]←A[i]i←i–1A[i+1]=key“插入排序伪代码插入排序举例824936插入排序举例插入排序举例插入排序举例运行时间运行时间依赖于输入：已经排好序的序列更容易排序。通过输入规模量化运行时间：因为规模小的序列比规模大的序列更容易排序。通常，我们寻找运行时间的上限，因为它是一种保证。运行时间运行时间依赖于输入：已经排好序的序列更容易排序。分析的类型最坏情况:(经常)•T(n)=在任何输入规模n的情况下算法的最大时间.平均情况:(有时)•T(n)=期望n输入规模的算法时间.需要假定输入规模的统计分布.最好情况:(不正确的)把一种缓慢执行的算法欺骗为某种输入规模上快速执行的算法。分析的类型最坏情况:(经常)与机器无关的时间插入排序最坏情况的时间是什么？它依赖于我们计算机的速度。

相对速度（在同一台机器上）

绝对速度（在不同的机器上）好的建议忽略与机器相关的常数。考虑当n→∞时，T(n)的增长率。September7,2005IntroductiontoAlgorithmsL1.22Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson与机器无关的时间插入排序最坏情况的时间是什么？

Θ符号Math:Θ(g(n))={f(n):这里存在整数c1,c2，n0使得0≤c1g(n)≤f(n)≤c2g(n)对于所有的n≥n0}工程学:丢弃低阶项;忽略主要的常数例如:3n3+90n2–5n+6046=Θ(n3)

Θ符号Math:

渐近性能

当n足够大时，Θ(n^2)的算法性能总是优于Θ(n^3)

我们不应该忽略渐进缓慢的算法。现实生活的设计情形经常要求准确的工程目标平衡。渐进分析是一种有助于我们组织思考的有效工具。

渐近性能

当n足够大时，Θ(n^2)的算法性能总是优于Θ(插入排序分析插入排序分析插入排序分析插入排序是最快的排序算法吗？

对于n比较小时，速度适中。

对于n比较大时，速度比较慢。插入排序分析插入排序是最快的排序算法吗？合并排序合并排序A[1..n]

1.Ifn=1,done.

2.递归排序A[1..⎡n/2⎤]andA[⎡n/2⎤+1..n].

3.“合并”两个排好序的列表.关键子程序:合并子程序合并排序合并排序A[1..n]合并两个排好序的数组合并两个排好序的数组合并排序分析合并排序分析合并排序的递归T(n)={Θ(1)ifn=1;2T(n/2)+Θ(n)ifn>1。我们通常省略说明基本的情况，对于n足够小时，T(n)=Θ(1)，但只有当它对递归的渐进解决方法没有影响时。课本和在第二课中提供几种找出T(n)上限的好方法。合并排序的递归T(n)={Θ(1)ifn=1;递归树递归树结论Θ(nlgn)的增长比Θ(n^2)慢.因此，在最坏的情况下，合并排序的渐进性能比插入排序优。在实践中，对于n>30时，合并排序优于插入排序。结论Θ(nlgn)的增长比Θ(n^2)慢.算法导论第一课算法分析插入排序渐进分析合并排序递归翻译：今天在这个地方申明MIT的版权Prof.CharlesE.LeisersonCopyright©2001-5ErikD.DemaineandCharlesE.Leiserson算法导论第一课课程信息1.工作人员2.远程学习3.预备知识4.讲义5.口头问答6.上课资料7.课本8.课程网站9.额外帮助10.课程注册11.习题集12.描述算法13.评分方式14.合作规定课程信息1.工作人员8.课程网站算法分析

计算机程序性能和资源使用的理论研究。

什么比性能更重要？

模块性正确性可维护性函数性健壮性用户友好性程序员的时间简单性可扩展性可靠性算法分析

计算机程序性能和资源使用的理论研究。

什么比性为什么研究算法和性能？算法有助于我们理解可量测性。性能经常在可行和重要之间划下最后的界限。算法的数学描述为讨论程序的行为提供一种语言。性能是计算所通行的。程序性能的课程概括为另一些计算资源。高速是有趣的。为什么研究算法和性能？算法有助于我们理解可量测性。排序的问题输入：数字序列〈a1,a2,…,an〉输出：置换〈a‘1,a’2,…,a‘n〉使得a'1≤a'2≤…≤a'n例如：输入：824936输出:234689排序的问题输入：数字序列〈a1,a2,…,an〉插入排序伪代码插入排序(A,n)⊳A[1..n]Forj←2tonDokey←A[j]i←j–1Whilei>0andA[i]>keyDoA[i+1]←A[i]i←i–1A[i+1]=key“插入排序伪代码插入排序举例824936插入排序举例插入排序举例插入排序举例运行时间运行时间依赖于输入：已经排好序的序列更容易排序。通过输入规模量化运行时间：因为规模小的序列比规模大的序列更容易排序。通常，我们寻找运行时间的上限，因为它是一种保证。运行时间运行时间依赖于输入：已经排好序的序列更容易排序。分析的类型最坏情况:(经常)•T(n)=在任何输入规模n的情况下算法的最大时间.平均情况:(有时)•T(n)=期望n输入规模的算法时间.需要假定输入规模的统计分布.最好情况:(不正确的)把一种缓慢执行的算法欺骗为某种输入规模上快速执行的算法。分析的类型最坏情况:(经常)与机器无关的时间插入排序最坏情况的时间是什么？它依赖于我们计算机的速度。

相对速度（在同一台机器上）

绝对速度（在不同的机器上）好的建议忽略与机器相关的常数。考虑当n→∞时，T(n)的增长率。September7,2005IntroductiontoAlgorithmsL1.22Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson与机器无关的时间插入排序最坏情况的时间是什么？

Θ符号Math:Θ(g(n))={f(n):这里存在整数c1,c2，n0使得0≤c1g(n)≤f(n)≤c2g(n)对于所有的n≥n0}工程学:丢弃低阶项;忽略主要的常数例如:3n3+90n2–5n+6046=Θ(n3)

Θ符号Math:

渐近性能

当n足够大时，Θ(n^2)的算法性能总是优于Θ(n^3)

我们不应该忽略渐进缓慢的算法。现实生活的设计情形经常要求准确的工程目标平衡。渐进分析是一种有助于我们组织思考的有效工具。

渐近性能

当n足够大时，Θ(n^2)的算法性能总是优于Θ(插入排序分析插入排序分析插入排序分析插入排序是最快的排序算法吗？

对于n比较小时，速度适中。

对于n比较大时，速度比较慢。插入排序分析插入排序是最快的排序算法吗？合并排序合并排序A[1..n]

1.Ifn=1,done.

2.递归排序A[1..⎡n/2⎤]andA[⎡n/2⎤+1..n].

3.“合并”两个排好序的列表.关键子程序:合并子程序合并排序合并排序A[1..n]合并两个排好序的数组合并两个排好序的数组合并排序分析合并排序分析合并排序的递归T(n)={Θ(1)ifn=1;2T(n/2)+Θ(n)i