计算机算法分析与设计优秀课件.ppt

计算机算法分析与设计第1页，本讲稿共33页学习目标学习目标n掌握算法分析与设计的基本理论掌握算法分析与设计的基本理论n掌握进行算法分析与设计的基本方法掌握进行算法分析与设计的基本方法（时间、空间复杂度分析，算法正确性（时间、空间复杂度分析，算法正确性的证明）的证明）n掌握计算机领域中常用的非数值计算方掌握计算机领域中常用的非数值计算方法，并学会用这些算法解决实际问题法，并学会用这些算法解决实际问题第2页，本讲稿共33页课程要求课程要求n教学方式：理论教学方式：理论(32学时学时)，实践，实践(16学时学时)n考核方式：考试考核方式：考试(80%)+实验作业实验作业(20%)n课程学分：课程学分：3n先修课程：先修课程：离散数学离散数学数据结构数据结构数值分析数值分析C语言程序设计语言程序设计第3页，本讲稿共33页授课教材授课教材n选用教材：选用教材：计算机算法基础计算机算法基础（第二版）（第二版）余祥宣，崔国华，邹海明余祥宣，崔国华，邹海明 华中科技大学出华中科技大学出版社版社n参考书目：参考书目：算法引论算法引论 张益新，沈雁张益新，沈雁 国防科技大学国防科技大学出版社出版社算法设计与分析算法设计与分析 周培德周培德 机械工业出机械工业出版社版社第4页，本讲稿共33页第一章第一章 导引导引 -计算机算法分析与设计是面向设计的、处于核心地位计算机算法分析与设计是面向设计的、处于核心地位的教育课程的教育课程 -计算机算法是计算机科学和计算机应用的核心。计算机算法是计算机科学和计算机应用的核心。1.什么是算法？什么是算法？2.如何分析算法？如何分析算法？3.如何表示算法？如何表示算法？4.基本数据结构基本数据结构第5页，本讲稿共33页1.什么是算法什么是算法算法算法数值计算方法数值计算方法（求解数值问题，插值计（求解数值问题，插值计算、数值积分等）算、数值积分等）非数值计算方法非数值计算方法（求解非数值问题，主（求解非数值问题，主要进行判断比较）要进行判断比较）算法笼统的定义：算法笼统的定义：求解一确定类问题的任意一种特殊方法。求解一确定类问题的任意一种特殊方法。非形式描述：非形式描述：算法就是一组有穷的规则，它规定了解决算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。某一特定类型问题的一系列运算。第6页，本讲稿共33页例例1 求两个正整数求两个正整数m,n的最大公因子的最大公因子算法算法1-1 欧几里得算法欧几里得算法输入：输入：正整数正整数m和和n输出：输出：m和和n的最大公因子的最大公因子第一步：求余数。第一步：求余数。rm%n第二步：判断第二步：判断r=0?，若是，终止，若是，终止(n为答为答案案)，否则，转第三步。，否则，转第三步。第三步：互换第三步：互换,mn,nr,返回第一步。返回第一步。BeginRm%nr=0？Swap(m.n)EndNY第7页，本讲稿共33页例例1 求两个正整数最大公因子的一个实例求两个正整数最大公因子的一个实例假设假设 m=21 和和 n=45，求，求21和和45的最大公因子的最大公因子第一步第一步：r=m%n=21%45=21；第二步第二步：r 不等于不等于0，转入第三步；，转入第三步；第三步第三步：互换，：互换，m=n=45,n=r=21，返回第一步。，返回第一步。第一步第一步：r=m%n=45%21=3；第二步第二步：r 不等于不等于0，转入第三步；，转入第三步；第三步第三步：互换，：互换，m=n=21,n=r=3，返回第一步。，返回第一步。第一步第一步：r=m%n=21%3=0；第二步第二步：r 等于等于0，算法结束，算法结束，3即为即为21和和45的最大公因子。的最大公因子。第8页，本讲稿共33页算法的五个重要特性算法的五个重要特性n确定性确定性每一种运算必须要有确切的定义，无二义性每一种运算必须要有确切的定义，无二义性n可行性可行性运算都是基本运算，原理上能在有限时间内完成运算都是基本运算，原理上能在有限时间内完成n输入输入有有1个或多个输入个或多个输入n输出输出一个或多个输出一个或多个输出n有穷性有穷性在执行了有穷步运算后终止在执行了有穷步运算后终止第9页，本讲稿共33页算法的特性算法的特性n凡是算法，都必须满足以上五条特性。凡是算法，都必须满足以上五条特性。n只满足前四条特性的一组规则不能称之为只满足前四条特性的一组规则不能称之为算法，只能叫做算法，只能叫做计算过程计算过程。n操作系统就是计算过程的一个典型例子。操作系统就是计算过程的一个典型例子。设计操作系统的目的是为了控制作业的运设计操作系统的目的是为了控制作业的运行，当没有作业时，这一计算过程并不终行，当没有作业时，这一计算过程并不终止，而是处于等待状态，一直等到一个新止，而是处于等待状态，一直等到一个新的作业的进入。的作业的进入。第10页，本讲稿共33页算法学习的五个内容算法学习的五个内容n如何设计算法如何设计算法运用一些基本设计策略规划算法运用一些基本设计策略规划算法n如何表示算法如何表示算法用恰当的方式表示算法用恰当的方式表示算法n如何确认算法如何确认算法算法正确性的证明算法正确性的证明(算法确认算法确认algorithm validation)n如何分析算法如何分析算法通过时间和空间复杂度的分析，确定算法的优劣通过时间和空间复杂度的分析，确定算法的优劣n如何测试程序如何测试程序测试程序是否会产生错误的结果测试程序是否会产生错误的结果第11页，本讲稿共33页2.如何分析算法如何分析算法n算法分析是对一个算法需要多少计算时间和存储空间算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。作定量的分析。n算法分析步骤：算法分析步骤：n首先确定使用那些运算以及执行这些运算所用首先确定使用那些运算以及执行这些运算所用的时间。的时间。(运算包括运算包括基本数值运算基本数值运算和和一些更基一些更基本的任意长序列的运算本的任意长序列的运算)n其次是要确定出能反映算法在各种情况下工作其次是要确定出能反映算法在各种情况下工作的数据集。（即要求我们编造出能产生最好、的数据集。（即要求我们编造出能产生最好、最坏和有代表性情况的数据配置，通过使用这最坏和有代表性情况的数据配置，通过使用这些数据来运行算法，以更了解算法的性能）些数据来运行算法，以更了解算法的性能）第12页，本讲稿共33页全面分析一个算法的两个阶段全面分析一个算法的两个阶段n事前分析事前分析(a priori analysis)n求出该算法的一个求出该算法的一个时间限界函数时间限界函数(一些关于参一些关于参数的函数数的函数)n事前分析只限于每条语句的事前分析只限于每条语句的频率计数频率计数(frequency count，该语句的执行次数，该语句的执行次数，与所用的机器无关，且独立于程序设计语言，与所用的机器无关，且独立于程序设计语言，可由算法直接确定可由算法直接确定)n事后测试事后测试(a posteriori testing)n收集此算法的实际执行时间和占用空间的统计收集此算法的实际执行时间和占用空间的统计资料资料第13页，本讲稿共33页例例3：频率计数例子频率计数例子n考虑语句考虑语句xx+y在下面三个程序段中的频率计数在下面三个程序段中的频率计数beginxx+yendFC:1beginfor i1 to n doxx+yrepeatEndFC:nbeginfor i1 to n do for j1 to n doxx+y repeatRepeatEndFC:n2第14页，本讲稿共33页计算时间的渐进估计表示计算时间的渐进估计表示n定义定义1.1 如果存在两个正常数如果存在两个正常数c和和n0，对于所有的，对于所有的nn0，有，有|f(n)|c|g(n)|则记作：则记作：f(n)=O(g(n)n因此，当说一个算法具有因此，当说一个算法具有O(g(n)的计算时间时，指的计算时间时，指的就是如果此算法用的就是如果此算法用n值不变的同一类数据在某台机器值不变的同一类数据在某台机器上运行时，所用的时间总是小于上运行时，所用的时间总是小于|g(n)|的一个常数倍。的一个常数倍。ng(n)是计算时间是计算时间f(n)的一个上界函数，的一个上界函数，f(n)的数量的数量级就是级就是g(n)第15页，本讲稿共33页时间的渐进估计表示时间的渐进估计表示n定理定理1.1 若若A(n)=amnm+a1n+a0是是一个一个m次多项式，则次多项式，则A(n)=O(nm)。证明：取证明：取n0=1，当，当nn0时利用时利用A(n)的定义和的定义和一个简单的不等式，有一个简单的不等式，有|A(n)|am|nm+|a1|n+|a0|(|am|+|am-1|/n+|a0|/nm)nm (|am|+|am-1|+|a0|)nm取取c=|am|+|am-1|+|a0|，定理得证。，定理得证。第16页，本讲稿共33页时间的渐进估计表示时间的渐进估计表示n定理表明，变量定理表明，变量n的固定阶数为的固定阶数为m的任一多的任一多项式，与此多项式的最高阶项式，与此多项式的最高阶nm同阶。因此，同阶。因此，一个计算时间为一个计算时间为m阶多项式的算法，其时阶多项式的算法，其时间都可以用间都可以用O(nm)来表示。来表示。n例如，一个算法的数量级为例如，一个算法的数量级为c1nm1,c2nm2,cknmk的的k个语句，则算个语句，则算法的数量级及计算时间就是法的数量级及计算时间就是c1nm1+c2nm2+cknmk=O(nm)其中其中m=maxmi|1 i k第17页，本讲稿共33页算法的分类算法的分类n从计算时间上可把算法分为两类从计算时间上可把算法分为两类n多项式时间算法多项式时间算法(polynomial time algorithm):可用多项式来对其计算时间限可用多项式来对其计算时间限界的算法。以下六种计算时间的多项式时间界的算法。以下六种计算时间的多项式时间算法是最为常见的算法是最为常见的O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)n指数时间算法指数时间算法(exponential time algorithm):计算时间用指数函数限界的算法计算时间用指数函数限界的算法O(2n)O(n!)O(nn)第18页，本讲稿共33页nlognnlognn2n32n100112212484428166416832464512256164642564096655363251601024327684294967296对于问题输入长度对于问题输入长度n取不同值，各种不同的时间复杂取不同值，各种不同的时间复杂性函数的算法，在机器上的运行所需时间如下所示：性函数的算法，在机器上的运行所需时间如下所示：第19页，本讲稿共33页时间的渐进估计表示时间的渐进估计表示n定义定义1.2 如果存在两个正常数如果存在两个正常数c和和n0，对于所有的，对于所有的nn0，有，有|f(n)|c|g(n)|则记作：则记作：f(n)=(g(n)n定义定义1.3 如果存在两个正常数如果存在两个正常数c1,c2和和n0，对于所有的，对于所有的nn0，有，有 c1|g(n)|f(n)|c2|g(n)|则记作：则记作：f(n)=(g(n)第20页，本讲稿共33页常用的整数求和公式常用的整数求和公式第21页，本讲稿共33页3.如何表示算法如何表示算法n将算法的基本思想和基本步骤用语言表示出来，便将算法的基本思想和基本步骤用语言表示出来，便于阅读并能很容易地用人工或机器翻译成其他实际于阅读并能很容易地用人工或机器翻译成其他实际使用的程序设计语言。使用的程序设计语言。n用用SPARKS语言写算法语言写算法nSPARKS语言的组成语言的组成n基本数据类型基本数据类型整型整型(integer),实型实型(float),布尔型布尔型(boolean),字符型字符型(char)n保留字保留字具有特殊含义的标识符，用黑体字表示具有特殊含义的标识符，用黑体字表示第22页，本讲稿共33页SPARKS语言的组成（语言的组成（1）n变量命名规则变量命名规则n以字母开头，不允许使用特殊字符，不要太长，不允许与任何以字母开头，不允许使用特殊字符，不要太长，不允许与任何保留字重复。保留字重复。n语句：语句：以分号作为语句结束的标志以分号作为语句结束的标志n赋值语句：赋值语句：n布尔值：布尔值：True Falsen逻辑运算符：逻辑运算符：and,or,notn关系运算符：关系运算符：,n数组：数组：任意整数下界和上界的多维数组任意整数下界和上界的多维数组第23页，本讲稿共33页SPARKS语言的组成（语言的组成（2）n条件语句条件语句if 条件条件 then s1或或 if 条件条件 thenelse s2s1endifendifnCase语句语句case:条件条件 1:s1:条件条件 n:sn:else :sn+1endcase第24页，本讲稿共33页SPARKS语言的组成（语言的组成（3）n循环语句循环语句while 条件条件 doloopS SRepeatuntil 条件条件 repeatFor vblestart to finish by increment doSRepeat 第25页，本讲稿共33页SPARKS语言的组成（语言的组成（4）n过程过程(函数函数)Procedure Name()SReturn()End Namen局部变量局部变量(local variabl)在当前的过程中说明的变量在当前的过程中说明的变量n全局变量全局变量(global variabl)在已包含当前过程的过程中说明为局部变量的变量在已包含当前过程的过程中说明为局部变量的变量n形式参数形式参数(formal parameter)参数表中的一个标识符参数表中的一个标识符第26页，本讲稿共33页1.4 基本数据结构基本数据结构(略略)n栈和队列栈和队列n栈的运算栈的运算n队列的运算队列的运算n树树n二元树二元树n堆堆n二分检索树二分检索树n图图第27页，本讲稿共33页1.5 递归和消去递归递归和消去递归n递归递归直接调用自己或间接通过一些语句调用自己直接调用自己或间接通过一些语句调用自己优点：描述某些数学问题非常自然，证明算法很优点：描述某些数学问题非常自然，证明算法很容易。容易。缺点：执行时间、空间消耗多缺点：执行时间、空间消耗多一个递归问题可分为一个递归问题可分为“回推回推”和和“递推递推”两个阶两个阶段段未知已知递推回推第28页，本讲稿共33页递归例子：递归例子：Fibonacci数列数列n定义定义F(n)=1,n=01,n=1F(n-1)+F(n-2),n1非递归部分非递归部分,终止条件终止条件递归部分递归部分,起始条件起始条件n求Fibonacci数列算法Procedure F(n)integer nif n1 then return(1)else return(F(n-1)+F(n-2)end ifEnd F第29页，本讲稿共33页用递归实现求最大公因数用递归实现求最大公因数Procedure GCD(a,b)if b=0 then return(a)else return(GCD(b,a mod b)endifEnd GCD例如：例如：a=22,b=8 求求GCD(22,8)=？第30页，本讲稿共33页GCD(22,8)GCD(8,6)GCD(6,2)GCD(2,0)2回推回推回推回推回推回推回推回推递归递归递归递归递归递归递归递归用递归实现求最大公因数用递归实现求最大公因数结果为结果为GCD(22,8)=2第31页，本讲稿共33页消去递归消去递归n递归的优点：与数学定义相似，容易编写算法递归的优点：与数学定义相似，容易编写算法n递归的缺点：计算时间长，很多值都被重复计算了多递归的缺点：计算时间长，很多值都被重复计算了多次次n消去递归消去递归n目的是克服递归时间空间的开销目的是克服递归时间空间的开销n解决方法：先使用递归，然后证明所设计的递解决方法：先使用递归，然后证明所设计的递归算法正确并且确信是一个好算法，再把递归归算法正确并且确信是一个好算法，再把递归消去，翻译成与之等价的只使用迭代的算法。消去，翻译成与之等价的只使用迭代的算法。n直接递规翻译成迭代过程的规则直接递规翻译成迭代过程的规则第32页，本讲稿共33页小结小结n算法就是一组有穷的规则，它规定了解决算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。某一特定类型问题的一系列运算。n算法的五个重要特性算法的五个重要特性确定性、可行性、输入、输出、有穷性确定性、可行性、输入、输出、有穷性n算法分析是对一个算法需要多少时间很存算法分析是对一个算法需要多少时间很存储空间作定量分析。储空间作定量分析。n用用SPARKS语言写算法语言写算法n递归和消去递归递归和消去递归第33页，本讲稿共33页