离散数学算法基础.ppt

《离散数学算法基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法基础11.1算法简介一、算法的概念算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。也可以说，在有限的时间内，解决某一问题的一系列逻辑步骤就是算法。2二、算法的特征所有的算法都必须满足下列几个条件：1.有限性：必须保证执行有限步之后结束；也叫可终止性。2.确切性：算法的每一步骤必须有确切的含义，并且在任何情况下，对于相同的输入只能得出相同的输出。3.输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。4.输出：至少产生一个结果，此结果与输入的数据构成某种

2、特定的关系。5.可行性：对于指令的执行，可用笔和纸来模拟。31.2算法表示一、自然语言【例】写出“A、B为整数，求A除以B的余数”的算法。A/B算法：1）获得A和B的值；2）判断B是否为零；3）如果B为零，则输出“除数为零”出错信息；4）如果B不为零，则通过除式计算求得余数，最后，输出余数。4二、流程图【例】“A、B为整数，求A除以B的余数”的流程图算法。5三、伪代码伪代码（Pseudocode，拟代码，伪语言）是一种使用程序语言的基本结构来说明程序的运行过程的算法描述语言----程序语言的简化。使用伪代码的目的是为了使被描述的算法可以容易地以编程语言（Pascal，C，J

3、ava，etc）实现。伪代码的种类很多，原则上要结构化，尽量接近高级语言。本书以类C语言为算法描述语言。6【例】：伪代码示例if九点以前thendo私人事务；elseif9点到18点then工作；else下班;优点：结构清晰----体现了编程语言的结构表达精炼----忽略了编程语言繁琐的语法规则思路突出----容易把握解决方法的关键7类C语言的整体规格：1）算法名称（含参数）2）注释3）指令步骤类C语言的指令基本沿用C语言的指令集，在不产生歧义的情况下可适当简化。8【例1.2.1】算法:在整数iData1,iData2,iData3中寻找最大数。解：算法1//在整数iDat

4、a1,iData2,iData3中寻找最大数FindMaxData(intiData1,iData2,iData3){X=iData1;ifiData2>XX=iData2;ifiData3>XX=iData3；returnX；}9解：算法2//在整数iData1,iData2,iData3中寻找最大数FindMaxData(intiData1,iData2,iData3){if(iData1>iData2)and(iData1>iData3)returniData1;if(iData2>iData1)and(iData2>iData3)returniData2;if(iD

5、ata3>iData2)and(iData3>iData1)returniData3;}101.3算法分析完成一个任务，可以有多个算法。算法分析----对按照该算法编制的程序在计算机上的执行效率进行估算，目的在于评价算法的优劣。怎样评价算法的优劣时间效率：时间复杂度空间效率：空间复杂度（一般考虑多些）11一、时间复杂度（Timecomplexity）算法的时间复杂度是指算法需要消耗的时间资源。可以理解为程序运行从开始到结束所需要的时间。两种方法：事后统计方法事前分析方法12二、空间复杂度算法的空间复杂度是指算法需要消耗的空间资源（内存大小）。执行程序需要使用的空间是下列组成

6、的总和：1）固定部分：指令空间、固定大小的变量及常数所用的空间等。2）可变部分：动态变量和递归栈空间等。在一般的算法分析中，多以时间复杂度为主。13影响运行时间的因素：书写算法的程序设计语言编译产生的机器语言代码质量机器执行指令的速度问题的规模（数据个数）*原始数据的值（最好、平均、最坏）14找出问题的规模与时间之间的关系函数：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数（称为语句频度或时间频度）作为算法的时间度量。一般情况下，算法中原操作重复执行的次数是问题规模（Problem’sSize）n（元素个数）的某个函数T(n)－－作为算法的

7、时间复杂度的估算。15【例】语句频度的计算：下面的三个程序段..for(i=0;i