算法概述幻灯片.ppt





《算法概述幻灯片.ppt》由会员分享,可在线阅读,更多相关《算法概述幻灯片.ppt(69页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、算法概述第1页,共69页,编辑于2022年,星期一2课程简介算法分析与设计是一门面向设计,处于计算机科学核心地位的教育课程,通过对计算机算法系统的学习与研究,掌握算法设计的主要方法,培养对算法的计算复杂性正确分析的能力,为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。2第2页,共69页,编辑于2022年,星期一3课程信息学习目标熟悉算法分析的常用方法掌握算法设计的基本方法分治法、贪心法、动态规划法、回溯法等熟悉计算机科学中经常出现的某些问题的精巧求解算法例如,快速排序算法、求最小生成树的prim算法等等初步具有能针对所给实际问题来设计和实现算法,以及评价算法的能力。逐步养成对于所要解决
2、的问题,总是努力去设计出尽可能好的算法的良好习惯3第3页,共69页,编辑于2022年,星期一4课程信息教学方式课堂讲授(50学时)上机实验(6学时)考核方法期末闭卷考试70%实验作业30%4第4页,共69页,编辑于2022年,星期一5教材与教学参考资源教材计算机算法设计与分析,王晓东,电子工业出版社参考教材算法设计技巧与分析,电子工业出版社算法导论(第二版 影印版)高等教育出版社5第5页,共69页,编辑于2022年,星期一6课程主要学习内容算法分析的基本方法算法设计的基本方法 分治法 动态规划法 贪心法 回溯法 分枝限界法算法设计的其它方法6第6页,共69页,编辑于2022年,星期一7排序问题
3、(Sort)手动排序第7页,共69页,编辑于2022年,星期一8排序中的操作比较(Comparison)交换(Swap)=3 复制(copy)第8页,共69页,编辑于2022年,星期一9简单排序(Simple Sort Algorithm)第9页,共69页,编辑于2022年,星期一10插入排序(Insertion Sort Algorithm)第10页,共69页,编辑于2022年,星期一11选择排序(Selection Sort Algorithm)第11页,共69页,编辑于2022年,星期一12选择排序算法分析第12页,共69页,编辑于2022年,星期一13排序算法的效率Type of Ef
4、ficiencyMeasuresSpaceAmount of computer memoryTime#of items copied#of items swapped#of items comparedSpace EfficiencyAlgorithm#of memory cellsSimple SortInsertion SortSelection Sort1488Time EfficiencyAlgorithm#of copies#of comparisonsSimple SortInsertion SortSelection Sort74515421921第13页,共69页,编辑于202
5、2年,星期一14更一般的情况AlgorithmComparisonsCopiesSimple Sortn*(n-1)nInsertion Sort(n-1)+(n-2)+.+13*(n-1)+(n-2)+.+1Selection Sort(n-1)+(n-2)+.+13*(n-1)Comparisons Required#of ItemsSimple SortInsertion SortSelection Sort109045451009,9004,9504,9501,000999,000499,500499,50010,00099,990,00049,995,00049,995,000Cop
6、ies Required#of ItemsSimple SortInsertion SortSelection Sort10101352710010014,8502971,0001,0001,498,5002,99710,00010,000149,985,00029,997第14页,共69页,编辑于2022年,星期一15第一章 算法概述1.算法的概念2.算法复杂性及渐进复杂性3.算法分析的基本方法4.算法的时间复杂性15第15页,共69页,编辑于2022年,星期一161 算法的概念广义上,为解决一个问题而采取的方法和步骤,就称为算法。更严格的讲,算法是由若干条指令组成的有穷序列,且满足以下性质
7、:输入输出确定性有限性16第16页,共69页,编辑于2022年,星期一17算法与程序一个程序应包括:对数据的描述。在程序中要指定数据的类型和数据的组织形式,即数据结构(data structure)。对操作的描述。即操作步骤,也就是算法(algorithm)。Nikiklaus Wirth(沃思)提出的公式:数据结构+算法=程序算法是灵魂,数据结构是加工对象程序可以不满足算法的有限性有限性特征17第17页,共69页,编辑于2022年,星期一18问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法18第18页,共69页,编辑于
8、2022年,星期一19算法的表示自然语言流程图:直观形象,易于理解 伪代码:结构清晰,代码简单,可读性好,并且类似自然语言,介于自然语言与编程语言之间 程序设计语言:用计算机语言表示算法是我们的最终目的,计算机语言表示算法必须严格遵循所用语言的语法规则19第19页,共69页,编辑于2022年,星期一20衡量算法性能的标准正确性易读性健壮性高效率与低存储空间我们这里主要讨论算法的时间和空间性能,并以此作为衡量算法性能的重要标准,而且我们主要侧重于时间方面。20第20页,共69页,编辑于2022年,星期一212 算法复杂性算法复杂性:算法所需要的计算机资源时间复杂性(Time Complexity
9、)算法的时间复杂性:在算法运行期间所花费的时间。通常用渐进形式表示比如,T(n)=(n2)、(n2)或 (n2)空间复杂性(Space Complexity)算法的空间复杂性:在算法运行期间所需要的内存空间。一般是指,除开容纳输入数据之外的附加空间(auxiliary space,or work space)。通常用渐进形式表示比如,S(n)=(n2)、(n2)或(n2)21n是问题的规模(输入大小)第21页,共69页,编辑于2022年,星期一22算法渐近复杂性算法渐近复杂性是算法复杂性的一种表示形式,在难以精确计算基本操作执行次数时,仅需要求增长率(或阶)即可。T(n),as n(T(n)-
10、t(n)/T(n)0,as nt(n)是T(n)的渐近性态,为算法的渐近复杂性在数学上,t(n)是T(n)的渐近表达式,是T(n)去除了低阶项和首项常数后留下的主项,它比T(n)简单。22第22页,共69页,编辑于2022年,星期一23渐近表示的记号O 设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c0和一个自然数n0,使得对于任意的n n0,均有 f(n)cg(n),则 f(n)=O(g(n)O读:“大O”或“O”23第23页,共69页,编辑于2022年,星期一24渐近表示的记号 设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c0和一个自然数n0,
11、使得对于任意的n n0,均有 f(n)cg(n),则 f(n)=(g(n)读:“大omega”或“omega”24第24页,共69页,编辑于2022年,星期一25渐近表示的记号 设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在一个自然数n0和两个正常数c1,c2,使得对于任意的n n0,均有 c1g(n)f(n)c2 g(n),则 f(n)=(g(n)读:“theta”25第25页,共69页,编辑于2022年,星期一26渐近分析中函数比较f(n)=O(g(n)a b;f(n)=(g(n)a b;f(n)=(g(n)a=b.26第26页,共69页,编辑于2022年,星期一27渐近
12、表示Examples 例例1 1 设f(n)=10n2+20n。则有f(n)=O(n2)f(n)=(n2)f(n)=(n2)例例22 设f(n)=aknk+ak-1nk-1+a1n+a0,(ak0)。则有f(n)=O(nk)f(n)=(nk):f(n)=(nk)由此可见,复杂性的渐近表示可以简洁地表示出复杂性的数量级别。27第27页,共69页,编辑于2022年,星期一28渐近分析随n的增加T(n)的增长率28第28页,共69页,编辑于2022年,星期一29增长率的直观解释29第29页,共69页,编辑于2022年,星期一30在每秒在每秒1010亿步的计算机上的计算时间亿步的计算机上的计算时间nf
13、(n)=nf(n)=nlognf(n)=n2f(n)=n3f(n)=n4f(n)=n10f(n)=2n100.010.030.111010s1200.020.090.481602.84hr1000300.030.150.9278106.83d1s400.040.211.6642560121.36d18.3min500.050.282.412562503.1yr13d1000.10.66101000100ms3171yr4*1013yr100019.9610001s16.67min3.17*1013yr32*10283yr1000010130100ms16.67min115.7d3.17*102
14、3yr100000100166010s11.57d3171yr3.17*1033yr100000010001992016.67min31.71yr3.17*107yr3.17*1043yr默认单位为:us(微秒)30第30页,共69页,编辑于2022年,星期一313.算法分析(Algorithm Analysis)对于算法的时间和空间复杂性进行定量分析。分析算法时间复杂性的基本步骤选取一种或多种元运算作为基本运算 表示出在算法运行期间基本运算执行的总频数用渐近时间复杂性(asymptotic time complexity)表示31第31页,共69页,编辑于2022年,星期一32元运算算术运算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 概述 幻灯片

限制150内