离散数学算法基础.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2021/10/3,#,第1章 算法基础,1,第1页,1.1 算法介绍,一、算法概念,算法,（,Algorithm,）是一系列处理问题清楚指令，也就是说，能够对一定规范输入，在有限时间内取得所要求输出。,也能够说，在有限时间内，处理某一问题一系列逻辑步骤就是,算法,。,2,第2页,二、算法特征,全部算法都必须满足以下几个条件：,1.有限性：,必须确保执行有限步之后结束；也叫可终止性。,2.确切性：,算法每一步骤必须有确切含义，而且在任何情况下，对于相同输入只能得出相同输出。,3.输入：,一个算法有0个或多个输入，以刻画运算对象初始情况，所谓0个输入是指算法本身定义了初始条件。,4.输出：,最少产生一个结果，此结果与输入数据组成某种特定关系。,5.可行性：,对于指令执行，可用笔和纸来模拟。,3,第3页,1.2 算法表示,一、自然语言,【例】,写出“A、B为整数，求A除以B余数”算法。,A/B算法：,1）取得A和B值；,2）判断B是否为零；,3）假如B为零，则输出“除数为零”犯错信息；,4）假如B不为零，则经过除式计算求得余数，最终，输出余数。,4,第4页,二、流程图,【例】,“A、B为整数，求A除以B余数”流程图算法。,5,第5页,三、,伪代码,伪代码,（,Pseudocode，拟代码，伪语言,）是一个使用程序语言基本结构来说明程序运行过程算法描述语言-程序语言简化。,使用伪代码目标是为了使被描述算法能够轻易地以编程语言（Pascal，C，Java，etc）实现。,伪代码种类很多，标准上要结构化，尽可能靠近高级语言。,本书以类C语言为算法描述语言。,6,第6页,【例】：,伪代码示例,if,九点以前,then,do 私人事务；,else,if,9点到18点,then,工作；,else,下班;,优点：,结构清楚,-表示了编程语言结构,表示精炼,-忽略了编程语言繁琐语法规则,思绪突出,-轻易把握处理方法关键,7,第7页,类C语言整体规格：,1）算法名称（含参数）,2）注释,3）指令步骤,类C语言指令基本沿用C语言指令集，在不产生歧义情况下可适当简化。,8,第8页,【例1.2.1】,算法:在整数 iData1,iData2,iData3中寻找最大数。,解：算法1,/在整数 iData1,iData2,iData3中寻找最大数,FindMaxData(int iData1,iData2,iData3),X=iData1;,if iData2X,X=iData2;,if iData3X,X=iData3；,return X；,9,第9页,解：算法2,/在整数 iData1,iData2,iData3中寻找最大数,FindMaxData(int iData1,iData2,iData3),if(iData1iData2)and(iData1iData3),return iData1;,if(iData2iData1)and(iData2iData3),return iData2;,if(iData3iData2)and(iData3iData1),return iData3;,10,第10页,1.3 算法分析,完成一个任务，能够有多个算法。,算法分析-对按照该算法编制程序在计算机上执行效率进行估算，目标在于评价算法优劣。,怎样评价算法优劣,时间效率：时间复杂度,空间效率：空间复杂度,（普通考虑多些）,11,第11页,一、时间复杂度,（Time complexity）,算法,时间复杂度,是指算法需要消耗时间资源。能够了解为程序运行从开始到结束所需要时间。,两种方法：,事后统计方法,事前分析方法,12,第12页,二、空间复杂度,算法,空间复杂度,是指算法需要消耗空间资源（内存大小）。,执行程序需要使用空间是以下组成总和：,1）固定部分：指令空间、固定大小变量及常数所用空间等。,2）可变部分：动态变量和递归栈空间等。,在普通算法分析中，多以时间复杂度为主。,13,第13页,影响运行时间原因：,书写算法程序设计语言,编译产生机器语言代码质量,机器执行指令速度,问题规模（数据个数）,*,原始数据值（最好、平均、最坏）,14,第14页,找出问题规模与时间之间关系函数：,从算法中选取一个对于所研究问题来说是基本运算,原操作,，以该原操作重复执行次数（,称为,语句频度,或,时间频度,）,作为算法时间度量。,普通情况下，算法中原操作重复执行次数是,问题规模,（,Problems Size,）,n,（元素个数）某个函数,T,(,n,)作为算法时间复杂度估算,。,15,第15页,【例】,语句频度计算：下面三个程序段,.,for(i=0;in;i+),.for(i=0;in;i+)for(j=0;jn;j+),x=x+1;x=x+1;x=x+1;,.,.,(a)(b)(c),指令,x=x+1,在程序,(a)、(b)、(c),中,语句频度分别是,1,、,n,、,n,2,次。,16,第16页,例：,求以下算法段语句频度：,for(i=1;i=n;i+),for(j=1;j=i;j+),x=x+1;,分析：,该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环相关，所以，时间频度,T,(,n,)=1+2+3+,n,=,17,第17页,分析算法时间复杂度时，普通考虑其渐近增加率，引入,大,O,表示法,：,令,T,(,n,)为算法时间复杂度，假如存在正常数,c,，使得,则有：,T,(,n,),(,f,(,n,),比如,T,(,n,)=2,n,2,+3,n,+7，,f,(,n,)=,n,2,所以，其时间复杂度也可记为,T,(,n,)=,O,(,n,2,)。,18,第18页,通常：,f,(,n,)=,n,x,|,x,为,T,(,n,)多项式中最高指数,关键问题：求,T,(,n,)？,19,第19页,例：,分析以下算法段时间复杂度：,for(i=1;i=n;i+),for(j=1;j=i;j+),for(k=1;k=j;k+),x=i+j-k;,20,第20页,分析算法规律可知时间频度,T,(,n,)=1+(1+2)+(1+2+3)+.+(1+2+3+,n,),=,=,=+,=+,因为 ，故时间复杂度为,(,n,3,)。,21,第21页,算法时间复杂性关系,多项式时间算法,指数时间算法,22,第22页,常见时间复杂度有：,常数阶,O,(1),对数阶,O,(log,2,n,),线性阶,O,(,n,),线性对数阶,O,(,n,log,2,n,),平方阶,O,(,n,2,),立方阶,O,(,n,3,),k,次方阶,O,(,n,k,),指数阶,O,(2,n,),23,第23页,增加率关系图：,24,第24页,数据值对运行时间影响,平均时间复杂度,：,例,if(n%2=0),for(i=1;i=n;i+),x=x+1;,else,x=0；,当,n,为偶数，时间复杂度为,O,(,n,);,当,n,为奇数，时间复杂度为,O,(1);,假设，,n,为偶数和奇数几率相同，均为50%，则其平均复杂度为：,0.5*,O,(,n,)+0.5*,O,(1),即：,O,(,n,),25,第25页,作业：,P6:,习题:,2，4，6,7,26,第26页,