离散数学算法基础

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

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

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

4、2, iData3中寻找最大数。 解：算法1 /在整数 iData1, iData2, iData3中寻找最大数 FindMaxData(int iData1, iData2, iData3) X=iData1; if iData2X X=iData2; if iData3X X=iData3； return X； ,10,解：算法2 /在整数 iData1, iData2, iData3中寻找最大数 FindMaxData(int iData1, iData2, iData3) if (iData1iData2)and (iData1iData3) return iData1; if (iD

5、ata2iData1)and (iData2iData3) return iData2; if (iData3iData2)and (iData3iData1) return iData3; ,11,1.3 算法分析,完成一个任务，可以有多个算法。 算法分析-对按照该算法编制的程序在计算机上的执行效率进行估算，目的在于评价算法的优劣。,怎样评价算法的优劣 时间效率：时间复杂度 空间效率：空间复杂度,（一般考虑多些）,12,一、时间复杂度（Time complexity） 算法的时间复杂度是指算法需要消耗的时间资源。可以理解为程序运行从开始到结束所需要的时间。 两种方法： 事后统计方法 事前分析

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

7、 一般情况下，算法中原操作重复执行的次数是问题规模（Problems Size）n（元素个数）的某个函数T(n)作为算法的时间复杂度的估算。,16,【例 】语句频度的计算：下面的三个程序段 . . 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、 n2次。,17,例：求下列算法段的语句频度： for(i=1; i=n; i+) for(j =1; j =i ; j+) x=x+1; 分析：该算法为

8、一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因此，时间频度 T(n) = 1+2+3+n =,18,分析算法的时间复杂度时，一般考虑其渐近增长率，引入大O表示法： 令T(n)为算法的时间复杂度，如果存在正常数c，使得 则有： T(n) (f(n),例如 T(n) = 2n2+3n+7 ， f(n) = n2 所以，其时间复杂度也可记为T(n) =O(n2) 。,19,通常： f(n)=nx|x为T(n)多项式中最高指数,关键问题：求T(n)？,20,例：分析下列算法段的时间复杂度： for (i=1;i=n;i+) for (j=1;j=i;j+) for ( k=1;k=j;k+) x=i+j-k; ,21,分析算法规律可知时间频度 T(n)=1+(1+2)+(1+2+3)+.+(1+2+3+n) = = = + = + 由于 ，故时间复杂度为(n3)。,22,算法时间复杂性的关系,23,常见的时间复杂度有： 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) k次方阶O(nk) 指数阶O(2n),24,增长率的关系图：,25,数据值对运行时间的影响,平均时间复杂度： 例 if (n % 2=0) for(i=1; i=n; i+