算法概述幻灯片.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元运算算术运算

15、：主要有加、减、乘、除等运算。逻辑运算：主要有与、或、非等运算。关系运算：主要有大于、小于、等于、不等于运算。数据传输：主要包括赋值、输入、输出等操作。32第32页，共69页，编辑于2022年，星期一33Step Count 方法一条或多条执行时间是常常数数的语句称为“1步”，例如简单赋值语句；不涉及函数调用的表达式求值；简单的条件判断等。Step Count 方法以程序执行的总“步数”，即“步数”计数，作为算法的时间复杂性T(n)。设c1每“步”的执行时间c2,则实际执行时间满足：c1t(n)实际执行时间c2t(n)划分程序步的方法不唯一，t(n)也不唯一,但数量级唯一.33第33页，共69

16、页，编辑于2022年，星期一34算法分析的基本法则for/while 循环循环体内计算时间*循环次数嵌套循环循环体内计算时间*所有循环次数顺序语句各语句计算时间相加if-else语句if语句计算时间和else语句计算时间的较大者34计算时间约等于计算步数，是同阶的（同数量级）。第34页，共69页，编辑于2022年，星期一35例 求和step table是应用这种方法的范例。Count+仅用于说明Step Count方法，在应用该方法时并不需要写这样的程序。3535第35页，共69页，编辑于2022年，星期一36例 求总执行步数 s/e代表该语句执行后步数(count)的变化（增量）；Frequ

17、ency代表该语句的执行次数；Total steps代表该语句在整个程序执行过程中引发的总步数。36第36页，共69页，编辑于2022年，星期一374 算法的时间复杂性对于算法的时间复杂性，通常从分平均、最坏、最好几种情形来衡量，尤其是前两种。算法的平均复杂性 算法的最坏复杂性算法的最好复杂性37第37页，共69页，编辑于2022年，星期一38算法的时间复杂性最坏情况最坏情况下的时间复杂性 Tmax(n)=max T(I)|size(I)=n 最好情况最好情况下的时间复杂性 Tmin(n)=min T(I)|size(I)=n 平均情况平均情况下的时间复杂性 Tavg(n)=其中I是问题的规模

18、为n的实例，p(I)是实例I出现的概率。38第38页，共69页，编辑于2022年，星期一39例 顺序查找当仅考虑成功查找时，average case:t(n)=（n+1）/2；Best case:t(n)=1,Worst case:t(n)=n 3939第39页，共69页，编辑于2022年，星期一40顺序查找的最好时间复杂性40第40页，共69页，编辑于2022年，星期一41顺序查找的最坏时间复杂性41第41页，共69页，编辑于2022年，星期一42（1）Tmax(n)=max T(I)|size(I)=n=O(n)（2）Tmin(n)=min T(I)|size(I)=n=O(1)（3）在平

19、均情况下，假设：(a)搜索成功的概率为p(0 p 1)；(b)在数组的每个位置i(0 i n)搜索成功的概率相同，均为 p/n。42第42页，共69页，编辑于2022年，星期一43检索问题的顺序查找算法检索问题的顺序查找算法 以元素的比较作为基本操作。考虑成功检索的情况。最好情况下的时间复杂性：(1)最坏情况下的时间复杂性：(n)在等概率前提下，平均情况下的时间复杂性：(n)直接插入排序算法直接插入排序算法 以元素的比较作为基本操作。最好情况下的时间复杂性：(n)最坏情况下的时间复杂性：(n2)在等概率前提下，平均情况下的时间复杂性：(n2)43第43页，共69页，编辑于2022年，星期一44

20、最优算法（optimal algorithm）最优算法最优算法如果能够证明求解问题P的任何算法的时间是(f(n),那么称求解问题P的时间为 O(f(n)的任一算法为问题P的最优算法。44第44页，共69页，编辑于2022年，星期一45小结算法分析的概念算法分析的概念渐近复杂性：渐近复杂性：O,平均时间复杂性，最坏时间复杂性，最好时间复杂性平均时间复杂性，最坏时间复杂性，最好时间复杂性最优算法最优算法分析算法的基本方法分析算法的基本方法分析算法时间复杂性的步骤分析算法时间复杂性的步骤Step count方法方法45第45页，共69页，编辑于2022年，星期一46算法概念及特征算法复杂性时间复杂性

21、空间复杂性最好情况最坏情况平均情况算法分析渐进复杂性第46页，共69页，编辑于2022年，星期一习题算法分析题：1-1，1-3，1-4，1-6算法实现题：1-147第47页，共69页，编辑于2022年，星期一附录1：算法渐近复杂性分析中常用函数（1 1）单调函数）单调函数单调递增：m n f(m)f(n);单调递减：m n f(m)f(n);严格单调递增：m n f(m)f(n);严格单调递减：m f(n).（2 2）取整函数）取整函数 x ：不大于x的最大整数；x ：不小于x的最小整数。第48页，共69页，编辑于2022年，星期一取整函数的若干性质 x-1 x x x 0，有：n/a /b

22、=n/ab ;n/a /b =n/ab ;a/b (a+(b-1)/b;a/b (a-(b-1)/b;f(x)=x ,g(x)=x 为单调递增函数。第49页，共69页，编辑于2022年，星期一p(n)=a0+a1n+a2n2+adnd；ad0;p(n)=(nd);f(n)=O(nk)f(n)多项式有界；f(n)=O(1)f(n)c;k d p(n)=O(nk);k d p(n)=(nk);.多项式函数第50页，共69页，编辑于2022年，星期一对于正整数m,n和实数a0:a0=1;a1=a;a-1=1/a;(am)n=amn;(am)n=(an)m;aman =am+n;a1 an为单调递增函

23、数;a1 nb=o(an)指数函数第51页，共69页，编辑于2022年，星期一ex 1+x;|x|1 1+x ex 1+x+x2;ex=1+x+(x2),as x0;第52页，共69页，编辑于2022年，星期一 log n=log2n;lg n=log10n;ln n=logen;logkn=(log n)kl;log log n=log(log n);for a0,b0,c0对数函数第53页，共69页，编辑于2022年，星期一第54页，共69页，编辑于2022年，星期一|x|1 for x -1,for any a 0,logbn=o(na)第55页，共69页，编辑于2022年，星期一Sti

24、rlings approximation 阶乘函数第56页，共69页，编辑于2022年，星期一第57页，共69页，编辑于2022年，星期一附录2：用c+描述算法第58页，共69页，编辑于2022年，星期一（1 1）选择语句：）选择语句：（1.1)if 1.1)if 语句：语句：（1.2)1.2)？语句：？语句：if(expression)statement;else statement;exp1?exp2:exp3 y=x9?100:200;等价于：if(x9)y=100;else y=200;第59页，共69页，编辑于2022年，星期一（1.3)switch1.3)switch语句：语句：s

25、witch(expression)case 1:statement sequence;break;case 2:statement sequence;break;default:statement sequence;第60页，共69页，编辑于2022年，星期一（2 2）迭代语句：）迭代语句：（2.1)for 2.1)for 循环：循环：for(init;condition;inc)statement;（2.2)while 2.2)while 循环：循环：while(condition)statement;（2.3)do-while 2.3)do-while 循环：循环：do statement

26、;while(condition);第61页，共69页，编辑于2022年，星期一（3 3）跳转语句：）跳转语句：（3.1)return3.1)return语句：语句：return expression;（3.2)goto3.2)goto语句：语句：（不推荐使用）goto label;label:第62页，共69页，编辑于2022年，星期一（4 4）函数：）函数：例：例：return-type function name(para-list)body of the function int max(int x,int y)return xy?x:y;第63页，共69页，编辑于2022年，星期一（

27、5 5）模板）模板templatetemplate：template Type max(Type x,Type y)return xy?x:y;int i=max(1,2)；double x=max(1.0,2.0)；第64页，共69页，编辑于2022年，星期一（6 6）动态存储分配：）动态存储分配：（6.16.1）运算符）运算符new new：运算符new用于动态存储分配。new返回一个指向所分配空间的指针。例：int x；y=new int；y=10；也可将上述各语句作适当合并如下：int y=new int；y=10；或 int y=new int(10)；或 int y；y=new i

28、nt(10)；第65页，共69页，编辑于2022年，星期一（6.26.2）一维数组）一维数组 ：为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个float类型的指针。然后用new为数组动态地分配存储空间。例：例：float x=new floatn；创建一个大小为n的一维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。然后可用x0，x1，xn-1来访问每个数组元素。第66页，共69页，编辑于2022年，星期一（6.36.3）运算符）运算符delete delete：当动态分配的存储空间已不再需要时应及时释放所占用的空间。用运算符delete来

29、释放由new分配的空间。例：例：delete y；delete x；分别释放分配给y的空间和分配给一维数组x的空间。第67页，共69页，编辑于2022年，星期一（6.46.4）动态二维数组）动态二维数组 ：创建类型为Type的动态工作数组，这个数组有rows行和cols列。template void Make2DArray(Type*&x,int rows,int cols)x=new Type*rows;for(int i=0;irows;i+)xi=new Typecols;第68页，共69页，编辑于2022年，星期一当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所分配的空间。然后释放为行指针分配的空间。释放空间后将x置为0，以防继续访问已被释放的空间。template void Delete2DArray(Type*&x,int rows)for(int i=0;irows;i+)delete xi;delete x;x=0;第69页，共69页，编辑于2022年，星期一