计算机算法设计与分析第1章算法概述课件.ppt

1、1理论课：理论课：110周，周，40学时学时 周二周二(5-6)、周五、周五(1-2)上机：上机： 18学时学时期末考试：期末考试： 闭卷笔试，第闭卷笔试，第 11周周上课点名三次不到者取消考试资格；上课点名三次不到者取消考试资格；迟到或作业缺交，一次扣迟到或作业缺交，一次扣10分（平时成绩）。分（平时成绩）。2本课程是计算机类专业计算机类专业的专业基础课程；通过课程学习和上机实践课程学习和上机实践，对计算机常用算法有一个较全面的了解，掌握通用算法的一般设计方法；学会对算法的时间算法的时间、空间复杂度分析空间复杂度分析，掌握提高算法效率的方法提高算法效率的方法和途径。3（一）（一） 从理论和实

2、践的角度理解从理论和实践的角度理解 计算机科学的基石；掌握标准算法计算机科学的基石；掌握标准算法（二）从算法（二）从算法对于对于程序的重要性来讲程序的重要性来讲 皮之不存，毛将附焉？皮之不存，毛将附焉？（三）（三） 从对同学们的能力培养看从对同学们的能力培养看 开发分析问题的能力开发分析问题的能力4（一）数据结构关心的对象（一）数据结构关心的对象 各种各种数据结构数据结构的作用和效率、具体的问题的作用和效率、具体的问题（二）算法设计与分析关心的对象（二）算法设计与分析关心的对象 算法算法设计技术设计技术的适用性和效率、的适用性和效率、一般性方一般性方法法5第第1 1章章 算法概述算法概述第第2

3、 2章章 递归与分治策略递归与分治策略第第3 3章章 动态规划动态规划第第4 4章章 贪心算法贪心算法第第5 5章章 回溯法回溯法第第6 6章章 分支限界法分支限界法* *7-97-9章属研究生学习内容，可自学了解章属研究生学习内容，可自学了解。6学习要点学习要点: 一、一、理解算法的概念，以及问题求解的理解算法的概念，以及问题求解的过程。过程。二、二、掌握算法的几种描述方式。掌握算法的几种描述方式。三、三、理解算法的计算复杂性概念。理解算法的计算复杂性概念。四、四、掌握算法渐近复杂性的数学表述。掌握算法渐近复杂性的数学表述。7我们来编写一个烧开水的算法：输入输入自来水循环循环（反复）加热直到

4、水开输出输出开水8 算法概念算法概念：通俗地讲，算法是指解决问题通俗地讲，算法是指解决问题的一种方法或一个过程。严格地讲，算法是的一种方法或一个过程。严格地讲，算法是由若干条指令组成的有穷序列。由若干条指令组成的有穷序列。输入输出算法问题“计算设备”91、算法具有某些特性，如下几条：、算法具有某些特性，如下几条：(1)输入输入：有零个或多个外部提供的量作为算：有零个或多个外部提供的量作为算法的输入。法的输入。(2)输出输出：算法产生至少一个量作为输出。这：算法产生至少一个量作为输出。这些输出是和输入有某种特定关系的量。些输出是和输入有某种特定关系的量。10(3)确定性确定性：组成算法的每条指令

5、是清晰，无：组成算法的每条指令是清晰，无歧义的。歧义的。(4)有限性（有穷性）有限性（有穷性）：算法中每条指令的执：算法中每条指令的执行次数是有限的，执行每条指令的时间也是行次数是有限的，执行每条指令的时间也是有限的。有限的。11(5)可实现性可实现性：此性质是指算法中有待实现的此性质是指算法中有待实现的运算都是相当基本的，每种运算至少在原理运算都是相当基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成。上能由人用纸和笔在有限的时间内完成。（补充）（补充）122、关于算法有几个要点：、关于算法有几个要点：(1) 算法所处理的输入的值域必须严格定义。算法所处理的输入的值域必须严格定义。

6、(2) 同样一种算法可以用几种不同的形式来描同样一种算法可以用几种不同的形式来描述。述。13(3) 同一个问题可以存在多种解决的算法。同一个问题可以存在多种解决的算法。(4) 同一个问题的几种算法可能会基于完全不同一个问题的几种算法可能会基于完全不同的解题思路，而且解题速度也会有显著不同的解题思路，而且解题速度也会有显著不同。同。141)问题的陈述 用科学规范的语言用科学规范的语言,对所求解的问题做准确的对所求解的问题做准确的描述描述.2)建立数学模型 通过对问题的分析通过对问题的分析,找出其中的所有操作对象找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描及操作对象之间的关系并用数

7、学语言加以描述述.3)算法设计算法设计 根据数学模型设计问题的计算机求解算法根据数学模型设计问题的计算机求解算法.154)算法的正确性证明算法的正确性证明 证明算法对一切合法输入均能在有限次计算证明算法对一切合法输入均能在有限次计算后产生正确输出后产生正确输出.5)算法的程序实现 将算法正确地编写成机器语言程序将算法正确地编写成机器语言程序.6)算法分析算法分析 对执行该算法所消耗的计算机资源进行估算对执行该算法所消耗的计算机资源进行估算.16通过学习已被实践证明是有用的一些基本设通过学习已被实践证明是有用的一些基本设计策略，如递归、回溯等，掌握一般的算法计策略，如递归、回溯等，掌握一般的算法

8、设计方法，学会设计高效的算法。设计方法，学会设计高效的算法。17证明算法对所有可能的输入都能算出正确的证明算法对所有可能的输入都能算出正确的答案，这一工作称为答案，这一工作称为算法确认算法确认。这一领域是。这一领域是当前许多计算机工作者集中研究的对象，还当前许多计算机工作者集中研究的对象，还处于相当初期的阶段。处于相当初期的阶段。在学习本课程中，我们仅对算法的正确性进在学习本课程中，我们仅对算法的正确性进行一般的非形式化讨论，以及对算法的程序行一般的非形式化讨论，以及对算法的程序实现进行测试验证。实现进行测试验证。18分析算法包括分析算法包括 定量的分析算法需要多少定量的分析算法需要多少计算计

9、算时间时间和和存储空间存储空间，分析算法不仅可以预计，分析算法不仅可以预计 算算法能否有效得完成任务，而且可以知道算法法能否有效得完成任务，而且可以知道算法在在最坏最坏、最好最好和和平均情况平均情况下的运算时间，对下的运算时间，对解决同一问题解决同一问题的的不同算法不同算法的优劣作出比较。的优劣作出比较。191、计算两个整数的最大公约数问题的一个现、计算两个整数的最大公约数问题的一个现代数学术语表述代数学术语表述 欧几里得算法基于的方法是重复应用下列欧几里得算法基于的方法是重复应用下列等式：等式： gcd (m , n) = gcd (n , m mod n) ， 直到直到m mod n等于等

10、于0。gcd(60,24)=gcd(24,12)=gcd(12,0)=12注：gcd (m , 0) =m，m mod n 表示m除以n之后的余数，称为模运算20计算计算gcd（m，n）的欧几里得算法：）的欧几里得算法：第一步：如果第一步：如果n=0,返回返回m的值作为结果，同的值作为结果，同时过程结束；否则，进入第二步。时过程结束；否则，进入第二步。第二步：用第二步：用n去除去除m，将余数赋给，将余数赋给r。第三步：将第三步：将n的值赋给的值赋给m，将，将r的值赋给的值赋给n，返，返回第一步。回第一步。21ALGORITHM Euclid（m，n）/ 计算计算gcd（m，n）/ 输入：非负整

11、数输入：非负整数m，n，其中，其中m，n不同时为零不同时为零/ 输出：输出：m，n的最大公约数的最大公约数while n 0 dor m mod nm nn rreturn m22int Euclid（int m，int n）/ 计算计算gcd（m，n）/ 输入：非负整数输入：非负整数m，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; 23程序流程

12、图等，不再一一列举。程序流程图等，不再一一列举。24算法复杂性是算法效率的度量，是评价算法优劣的算法复杂性是算法效率的度量，是评价算法优劣的重要依据。重要依据。算法复杂性的高低体现在运行算法所需要的算法复杂性的高低体现在运行算法所需要的计算机计算机资源，即时间和空间（存储器）资源资源，即时间和空间（存储器）资源的多少上。的多少上。算法的时间复杂性算法的时间复杂性T T( (n n) )，空间复杂性，空间复杂性S S( (n n) )。其中其中n n是问题的规模（输入大小）。是问题的规模（输入大小）。25本课程主要对本课程主要对算法算法的时的时间复杂性间复杂性进行分析。进行分析。关于算法的复杂性

13、，有两个问题要弄清楚：关于算法的复杂性，有两个问题要弄清楚：（1 1）用怎样的一个）用怎样的一个量（指标）量（指标）来表达一个算法的来表达一个算法的复杂性；复杂性；（2 2）对于一个算法，怎样具体）对于一个算法，怎样具体计算计算它的复杂性。它的复杂性。26算法的算法的最坏最坏、最好最好和和平均平均时间复杂性时间复杂性（1）最坏情况下的时间复杂性）最坏情况下的时间复杂性 Tmax(n) = max T(I) | size(I)=n （2）最好情况下的时间复杂性）最好情况下的时间复杂性 Tmin(n) = min T(I) | size(I)=n 其中其中 size(I)= n 表示表示 I 是规

14、模为是规模为n的实例的实例27（3）平均情况下的时间复杂性）平均情况下的时间复杂性 Tavg(n) = 其中其中 p(I) 是实是实 例例I出现的概率。出现的概率。nIsizeITIp)()()(28例：例：顺序查找顺序查找算法的时间复杂度计算：算法的时间复杂度计算： 已知不重复已知不重复，从小到大排列的从小到大排列的m m个整数的数个整数的数组组A1.m,m=2K,KA1.m,m=2K,K为正整数为正整数。 对于给定的整数对于给定的整数c,c,要求找到一个下标要求找到一个下标i,i,使得使得Ai=c.Ai=c.找不到返回找不到返回0 0。 A1AmAi=c29分析分析:问题的规模为问题的规模

15、为m设元运算执行时间：赋值设元运算执行时间：赋值 a, 判断判断 t, 加法加法 s设设 c 在在A中查找成功中查找成功30 int search(int A , int m, int c) int i=1; a a while( Aic & icAmid=low) mid=(low+high)/2;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，存在正数

16、和存在正数和n0 0使得对所有使得对所有n n0有：有：0 cg(n) f(n) 等价于等价于 f(n) / g(n) ，as n。f(n) (g(n) g(n) o (f(n) 47例例1：3n+2= o(n2) 。 例例2：10n2+4n+2 = (n) 。48(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)

17、 49例：对于所有对于所有n，有：，有：3n+2= (n)100n+6= (n)10n2 +4n+2 = (n2 ) 62n+n2= (2n) 。50f(n)=O (g(n) f(n)的阶不高于的阶不高于g(n)的阶；的阶；f(n)= (g(n) f(n)的阶不低于的阶不低于g(n)的阶；的阶；f(n)=(g(n) f(n)与与g(n)同阶。同阶。课后习题课后习题1-651以下设以下设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) 如果如果

18、f(n) =O(g(n), 则则O(f)+O(g)=O(g)(5) O(cf(n)=O(f(n), 其中其中c是一个正的常数是一个正的常数(6) f =O(f)52课后习题课后习题1-353图1.2 时间函数的增长率54图1.3 时间函数的增长率55（一）算法分析的基本法则（一）算法分析的基本法则非递归非递归算法：算法：（1）for / while 循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；56（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。57建立算法的基本操作执行次数的建立算法的基本操作执行次数的

19、递推关系式递推关系式，然后，然后确定它的增长次数。确定它的增长次数。int factorial(int n) if (n = 0) return 1; return n*factorial(n-1); 01) 1(00)(nnTnnT110)(nTnnT)(0n58“算法算法”是在有限时间内，对问题求解的一是在有限时间内，对问题求解的一个清晰的指令序列。算法的输入确定了该算个清晰的指令序列。算法的输入确定了该算法求解问题的一个实例。法求解问题的一个实例。算法可以用自然语言或者伪代码来详细描述，算法可以用自然语言或者伪代码来详细描述，也可以用计算机程序的方式实现。也可以用计算机程序的方式实现。算

20、法复杂度（效率）有两种：时间复杂度和算法复杂度（效率）有两种：时间复杂度和空间复杂度。空间复杂度。59时间复杂度有三类：最坏，最好以及平均。时间复杂度有三类：最坏，最好以及平均。多数算法的复杂度分为几类：常数（多数算法的复杂度分为几类：常数（1）、对）、对数（数（logn）、线性（）、线性（n）、近似线性）、近似线性(nlogn)、平方（平方（n2）、立方（）、立方（n3）、指数（）、指数（mn ，n！）。！）。1、logn、n、nlogn、n2、n3统称为多项式时统称为多项式时间的有效算法或好算法，间的有效算法或好算法， mn ，n！统称为指！统称为指数时间的无效算法或坏算法。数时间的无效算法或坏算法。60一个好的算法常常是不懈努力和反复修正的一个好的算法常常是不懈努力和反复修正的结果。结果。