《计算机算法设计与分析第1章算法概述优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算机算法设计与分析第1章算法概述优秀PPT.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、课程支配理论课：理论课：110周，周，40学时学时 周二周二(5-6)、周五、周五(1-2)上机：上机：18学时学时期末考试：期末考试：闭卷笔试，第闭卷笔试，第 11周周上课点名三次不到者取消考试资格；上课点名三次不到者取消考试资格；迟到或作业缺交，一次扣迟到或作业缺交，一次扣10分（平常成果）。分（平常成果）。1教学目的和要求本课程是计算机类专业的专业基础课程；通过课程学习和上机实践，对计算机常用算法有一个较全面的了解，驾驭通用算法的一般设计方法；学会对算法的时间、空间困难度分析，驾驭提高算法效率的方法和途径。2学习算法的重要性（一）（一）从理论和实践的角度理解从理论和实践的角度理解 计算机
2、科学的基石；驾驭标准算法计算机科学的基石；驾驭标准算法（二）从算法对于程序的重要性来讲（二）从算法对于程序的重要性来讲 皮之不存，毛将附焉？皮之不存，毛将附焉？（三）（三）从对同学们的实力培育看从对同学们的实力培育看 开发分析问题的实力开发分析问题的实力3算法分析与设计课程与 数据结构课程（一）数据结构关切的对象（一）数据结构关切的对象 各种数据结构的作用和效率、具体的问题各种数据结构的作用和效率、具体的问题（二）算法设计与分析关切的对象（二）算法设计与分析关切的对象 算法设计技术的适用性和效率、一般性方算法设计技术的适用性和效率、一般性方法法4授课内容第第1 1章章 算法概述算法概述第第2
3、2章章 递归与分治策略递归与分治策略第第3 3章章 动态规划动态规划第第4 4章章 贪心算法贪心算法第第5 5章章 回溯法回溯法第第6 6章章 分支限界法分支限界法*7-9*7-9章属探讨生学习内容，可自学了解。章属探讨生学习内容，可自学了解。5第1章 算法概述学习要点学习要点:一、理解算法的概念，以及问题求解的过一、理解算法的概念，以及问题求解的过程。程。二、驾驭算法的几种描述方式。二、驾驭算法的几种描述方式。三、理解算法的计算困难性概念。三、理解算法的计算困难性概念。四、驾驭算法渐近困难性的数学表述。四、驾驭算法渐近困难性的数学表述。6什么是算法？我们来编写一个烧开水的算法：输入输入自来水
4、循环循环（反复）加热直到水开输出输出开水7一、算法(Algorithm)算法概念算法概念：通俗地讲，算法是指解决问题通俗地讲，算法是指解决问题的一种方法或一个过程。严格地讲，算法是的一种方法或一个过程。严格地讲，算法是由若干条指令组成的有穷序列。由若干条指令组成的有穷序列。图图1.1 1.1 算法的概念图算法的概念图8（一）算法的性质（一）算法的性质1、算法具有某些特性，如下几条：、算法具有某些特性，如下几条：(1)输入：有零个或多个外部供应的量作为算输入：有零个或多个外部供应的量作为算法的输入。法的输入。(2)输出：算法产生至少一个量作为输出。这输出：算法产生至少一个量作为输出。这些输出是和
5、输入有某种特定关系的量。些输出是和输入有某种特定关系的量。9（一一）算法的性质）算法的性质(3)确定性：组成算法的每条指令是清晰，无确定性：组成算法的每条指令是清晰，无歧义的。歧义的。(4)有限性（有穷性）：算法中每条指令的执有限性（有穷性）：算法中每条指令的执行次数是有限的，执行每条指令的时间也是行次数是有限的，执行每条指令的时间也是有限的。有限的。10（一一）算法的性质）算法的性质(5)可实现性可实现性：此性质是指算法中有待实现的此性质是指算法中有待实现的运算都是相当基本的，每种运算至少在原理运算都是相当基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成。上能由人用纸和笔在有限的
6、时间内完成。（补充）（补充）11（一）算法性质（一）算法性质2、关于算法有几个要点：、关于算法有几个要点：(1)算法所处理的输入的值域必需严格定义。算法所处理的输入的值域必需严格定义。(2)同样一种算法可以用几种不同的形式来描同样一种算法可以用几种不同的形式来描述。述。12（一）算法性质（一）算法性质(3)同一个问题可以存在多种解决的算法。同一个问题可以存在多种解决的算法。(4)同一个问题的几种算法可能会基于完全不同一个问题的几种算法可能会基于完全不同的解题思路，而且解题速度也会有显著不同的解题思路，而且解题速度也会有显著不同。同。13（二）问题求解过程1)问题的陈述 用科学规范的语言,对所求
7、解的问题做精确的描述.2)建立数学模型 通过对问题的分析,找出其中的全部操作对象及操作对象之间的关系并用数学语言加以描述.3)算法设计 依据数学模型设计问题的计算机求解算法.14（二）问题求解过程4)算法的正确性证明算法的正确性证明 证明算法对一切合法输入均能在有限次计算证明算法对一切合法输入均能在有限次计算后产生正确输出后产生正确输出.5)算法的程序实现 将算法正确地编写成机器语言程序将算法正确地编写成机器语言程序.6)算法分析算法分析 对执行该算法所消耗的计算机资源进行估算对执行该算法所消耗的计算机资源进行估算.15（三）如何设计算法通过学习已被实践证明是有用的一些基本设通过学习已被实践证
8、明是有用的一些基本设计策略，如递归、回溯等，驾驭一般的算法计策略，如递归、回溯等，驾驭一般的算法设计方法，学会设计高效的算法。设计方法，学会设计高效的算法。16（四）如何确认算法（证明其正确性）证明算法对全部可能的输入都能算出正确的证明算法对全部可能的输入都能算出正确的答案，这一工作称为算法确认。这一领域是答案，这一工作称为算法确认。这一领域是当前很多计算机工作者集中探讨的对象，还当前很多计算机工作者集中探讨的对象，还处于相当时期的阶段。处于相当时期的阶段。在学习本课程中，我们仅对算法的正确性进在学习本课程中，我们仅对算法的正确性进行一般的非形式化探讨，以及对算法的程序行一般的非形式化探讨，以
9、及对算法的程序实现进行测试验证。实现进行测试验证。17（五）如何分析（评价）算法分析算法包括分析算法包括 定量的分析算法须要多少计算定量的分析算法须要多少计算时间和存储空间，分析算法不仅可以预料时间和存储空间，分析算法不仅可以预料 算算法能否有效得完成任务，而且可以知道算法法能否有效得完成任务，而且可以知道算法在最坏、最好和平均状况下的运算时间，对在最坏、最好和平均状况下的运算时间，对解决同一问题的不同算法的优劣作出比较。解决同一问题的不同算法的优劣作出比较。18二、算法的几种描述方式二、算法的几种描述方式1、计算两个整数的最大公约数问题的一个现、计算两个整数的最大公约数问题的一个现代数学术语
10、表述代数学术语表述 欧几里得算法基于的方法是重复应用下列欧几里得算法基于的方法是重复应用下列等式：等式：gcd(m,n)=gcd(n,m mod n)，直到直到m mod n等于等于0。gcd(60,24)=gcd(24,12)=gcd(12,0)=12注：gcd(m,0)=m，m mod n 表示m除以n之后的余数，称为模运算192、算法的一个结构化的描述、算法的一个结构化的描述计算计算gcd（m，n）的欧几里得算法：）的欧几里得算法：第一步：假如第一步：假如n=0,返回返回m的值作为结果，同时的值作为结果，同时过程结束；否则，进入其次步。过程结束；否则，进入其次步。其次步：用其次步：用n去
11、除去除m，将余数赋给，将余数赋给r。第三步：将第三步：将n的值赋给的值赋给m，将，将r的值赋给的值赋给n，返，返回第一步。回第一步。20ALGORITHM Euclid（m，n）/计算计算gcd（m，n）/输入：非负整数输入：非负整数m，n，其中，其中m，n不同时为零不同时为零/输出：输出：m，n的最大公约数的最大公约数while n 0 dor m mod nm nn rreturn m3、算法的一个伪代码描述、算法的一个伪代码描述214、算法的一个、算法的一个c+程序语言实现程序语言实现int Euclid（int m，int n）/计算计算gcd（m，n）/输入：非负整数输入：非负整数m
12、，n，其中，其中m，n不同时为零不同时为零/输出：输出：m，n的最大公约数的最大公约数 int r=0;if(m*n=0)return 0;/m，n不符合输入规范时返回不符合输入规范时返回0 while(n 0)r=m mod n;m=n;n=r;return m;22其他方法程序流程图等，不再一一列举。程序流程图等，不再一一列举。23三、算法困难性分析三、算法困难性分析算法困难性是算法效率的度量，是评价算法优劣的算法困难性是算法效率的度量，是评价算法优劣的重要依据。重要依据。算法困难性的凹凸体现在运行算法所须要的计算机算法困难性的凹凸体现在运行算法所须要的计算机资源，即时间和空间（存储器）资
13、源的多少上。资源，即时间和空间（存储器）资源的多少上。算法的时间困难性算法的时间困难性T(n)T(n)，空间困难性，空间困难性S(n)S(n)。其中其中n n是问题的规模（输入大小）。是问题的规模（输入大小）。24三、算法困难性分析三、算法困难性分析 本课程主要对算法的时间困难性进行分析。本课程主要对算法的时间困难性进行分析。关于算法的困难性，有两个问题要弄清晰：关于算法的困难性，有两个问题要弄清晰：（1 1）用怎样的一个量（指标）来表达一个算法的困）用怎样的一个量（指标）来表达一个算法的困难性；难性；（2 2）对于一个算法，怎样具体计算它的困难性。）对于一个算法，怎样具体计算它的困难性。25
14、1、算法的三种时间困难性、算法的三种时间困难性算法的最坏、最好和平均时间困难性算法的最坏、最好和平均时间困难性（1）最坏状况下的时间困难性）最坏状况下的时间困难性 Tmax(n)=max T(I)|size(I)=n（2）最好状况下的时间困难性）最好状况下的时间困难性 Tmin(n)=min T(I)|size(I)=n 其中其中 size(I)=n 表示表示 I 是规模为是规模为n的实例的实例261、算法的三种时间困难性、算法的三种时间困难性（3）平均状况下的时间困难性）平均状况下的时间困难性 Tavg(n)=其中其中 p(I)是实是实 例例I出现的概率。出现的概率。272、算法的时间困难性
15、计算、算法的时间困难性计算例：依次查找算法的时间困难度计算：例：依次查找算法的时间困难度计算：已知不重复，从小到大排列的已知不重复，从小到大排列的m m个整数的数个整数的数组组A1.m,m=2K,KA1.m,m=2K,K为正整数。为正整数。对于给定的整数对于给定的整数c,c,要求找到一个下标要求找到一个下标i,i,使使得得Ai=c.Ai=c.找不到返回找不到返回0 0。A1AmAi=c28分析分析:问题的规模为问题的规模为m设元运算执行时间：赋值设元运算执行时间：赋值 a,推断推断 t,加法加法 s设设 c 在在A中查找成功中查找成功292、算法的时间困难性计算、算法的时间困难性计算 int
16、search(int A,int m,int c)int i=1;a while(Aic&icAmid=low)mid=(low+high)/2;if(Amid=c)found=1;else if(Amid=2时，时，3n+2=2时，时，10n2+4n+2=5时，时，10n2+5n=4时，时，n2 0，存在正数和，存在正数和n0 0使得对全部使得对全部n n0有：有：0 f(n)0，存在正数和，存在正数和n0 0使得对全部使得对全部n n0有：有：0 cg(n)f(n)等价于等价于 f(n)/g(n)，as n。f(n)(g(n)g(n)o(f(n)46（3）非紧上界记号）非紧上界记号o和非紧
17、下界记号和非紧下界记号 例例例例1：3n+2=o(n2)。例例2：10n2+4n+2=(n)。47（4）紧渐近界记号）紧渐近界记号(g(n)=f(n)|存在正常数存在正常数c1,c2和和n0使得对使得对全部全部n n0有：有：c1g(n)f(n)c2g(n)记号记号适用于同一个函数适用于同一个函数g既可以作为函数既可以作为函数f的的上限也可以作为上限也可以作为f的下限的情形。的下限的情形。定理定理1：(g(n)=O(g(n)(g(n)48（4）紧渐近界记号）紧渐近界记号例例例：对于全部n，有：3n+2=(n)100n+6=(n)10n2+4n+2=(n2)62n+n2=(2n)。49O f(n
18、)=O(g(n)f(n)的阶不高于的阶不高于g(n)的阶；的阶；f(n)=(g(n)f(n)的阶不低于的阶不低于g(n)的阶；的阶；f(n)=(g(n)f(n)与与g(n)同阶。同阶。课后习题课后习题1-650O的运算规则以下设以下设f(n),g(n)是定义在正数集上的正函数：是定义在正数集上的正函数：(1)O(f)+O(g）=O(max(f,g)(2)O(f)+O(g）=O(f+g)(3)O(f)O(g）=O(fg)(4)假如假如f(n)=O(g(n),则则O(f)+O(g)=O(g)(5)O(cf(n)=O(f(n),其中其中c是一个正的常数是一个正的常数(6)f=O(f)51（5）算法分
19、析中常见的困难性函数）算法分析中常见的困难性函数课后习题课后习题1-3521、小规模数据、小规模数据图1.2 时间函数的增长率532、中等规模数据、中等规模数据图1.3 时间函数的增长率54五、算法分析方法五、算法分析方法（一）算法分析的基本法则（一）算法分析的基本法则非递归非递归算法：算法：（1）for/while 循环循环循环体内计算时间循环体内计算时间*循环次数；循环次数；（2）嵌套循环）嵌套循环循环体内计算时间循环体内计算时间*全部循环次数；全部循环次数；55（一）算法分析的基本法则（一）算法分析的基本法则非递归算法：非递归算法：（3）依次语句各语句计算时间相加；（4）if-else语
20、句if语句计算时间和else语句计算时间的较大者。56（二）递归算法困难性分析（二）递归算法困难性分析建立算法的基本操作执行次数的建立算法的基本操作执行次数的递推关系式递推关系式，然后，然后确定它的增长次数。确定它的增长次数。int factorial(int n)if(n=0)return 1;return n*factorial(n-1);57本章小结“算法算法”是在有限时间内，对问题求解的一是在有限时间内，对问题求解的一个清晰的指令序列。算法的输入确定了该算个清晰的指令序列。算法的输入确定了该算法求解问题的一个实例。法求解问题的一个实例。算法可以用自然语言或者伪代码来具体描述，算法可以用
21、自然语言或者伪代码来具体描述，也可以用计算机程序的方式实现。也可以用计算机程序的方式实现。算法困难度（效率）有两种：时间困难度和算法困难度（效率）有两种：时间困难度和空间困难度。空间困难度。58本章小结时间困难度有三类：最坏，最好以及平均。时间困难度有三类：最坏，最好以及平均。多数算法的困难度分为几类：常数（多数算法的困难度分为几类：常数（1）、对）、对数（数（logn）、线性（）、线性（n）、近似线性）、近似线性(nlogn)、平方（平方（n2）、立方（）、立方（n3）、指数（）、指数（mn，n！）！）。1、logn、n、nlogn、n2、n3统称为多项式时统称为多项式时间的有效算法或好算法，间的有效算法或好算法，mn，n！统称为指！统称为指数时间的无效算法或坏算法。数时间的无效算法或坏算法。59一个好的算法常常是不懈努力和反复修正的一个好的算法常常是不懈努力和反复修正的结果。结果。60