算法的构造及评价.ppt

第二章 算法的构造及评价,哈工大计算机科学与技术学院,数据结构课程组,2,2.1 逐步求精的算法构造过程,2.1.1 算法的定义,1.计算 能由一个给定的计算模型机械地执行的规则(或步骤)序列称为该计算模型的一个计算.注:一个计算机程序是一个计算(计算模型是计算机);计算可能永远不停止不是算法.,2.算法 是一个满足下列条件的一个计算（程序）：(1)有穷性/终止性：总是在执行有穷步后停止;(2)确定性：每一步必须有严格的定义和确定的动作;(3)能行性：每个动作都能被精确地机械执行;(4)输入：有0个和多个满足约束条件的输入;(5)输出：有一个或多个满足约束条件的结果.,哈工大计算机科学与技术学院,数据结构课程组,3,2.1.2 算法构造过程,实际上就是用计算机求解一个问题的过程,1.模型化 对实际问题进行分析，选择适当的数学模型来描述问题，即模型化。2.确定解决思路 根据模型，找出解决问题的思路方法(算法的原型，一般用自然语言描述)。3.逐步求精 对用自然语言等描述的算法逐步细致化、精确化和形式化。这一阶段可能包括多个步骤。当到达适当精度时，许多非形式的描述可转变为基于ADT的形式化描述。4.ADT的实现 对每个ADT，选择适当的数据结构表示数学模型，并用相应的函数实现每个操作。,哈工大计算机科学与技术学院,数据结构课程组,4,算法逐步求精实例,例2.1.2 交叉路口的交通安全管理问题,问题描述 一个具有多有多条通路的交叉路口,当允许某些通路上的车辆在交叉路口“拐弯”时,必须对其他一些通路上的 车辆加以限制,不允许同时在交叉路口“拐弯”,以免发生碰撞.,问题要求(1)设置一组交通灯,实现安全管理（无碰撞管理）.(2)使交通灯的数目最少.,哈工大计算机科学与技术学院,数据结构课程组,5,问题的分析,所有这些可能的“拐弯”构成一个集合.将此集合分成组,使得每组中所有的“拐弯”都能同时进行而不发生碰撞.每组对应一个指挥灯,保证不碰撞;用尽可能少的指挥灯归结为分成尽可能少的组.问题归结为如何进行集合的划分？,哈工大计算机科学与技术学院,数据结构课程组,6,模型化,(1)用图作为交叉路口的数学模型;(2)每个“拐弯”对应图中的一个顶点;(3)若两个“拐弯”不能同时进行,则用用一条边把这两个“拐弯”所对应的两个结点连接起来，并且说这两个顶点是相邻的。,哈工大计算机科学与技术学院,数据结构课程组,7,算法的基本思路,转化为图的着色问题（着同一颜色的结点即为一组）。常见算法为（1）穷举法（2）试探法（3）贪心法“贪心”算法的基本思想是首先用第一种颜色对图中尽可能多的顶点着色(尽可能多表现出“贪心”)，然后用第二种颜色对余下的顶点中尽可能多的顶点着色，如此等等，直至所有的顶点都着完色。,哈工大计算机科学与技术学院,数据结构课程组,8,算法原型（自然语言描述）,（1）将所有的结点设置为未着色（2）当有未着色的结点时，进行如下步骤（3）产生一种新的颜色（4）选取某个未着色的点，用此新颜色对其着色（5）扫描所有未着色的顶点，对其中的每个顶点尽可能的用此新颜色着色。（依据为它是否与已着新颜色的任何顶点相邻。若不相邻，则用新颜色对它着色。）（此处体现了贪心）。（6）重复步骤（2）-（5），直到所有的结点均以着色,哈工大计算机科学与技术学院,数据结构课程组,9,第一步求精（伪代码描述）,void greedy(G,newclr)GRAPH G;SET newclr;/*类型GRAPH和SET有待具体说明*/*本程序把G中可以着同一色的顶点放入newclr*/(1)newclr=(2)for(G中所有未着色的顶点v)(3)if(v不与newclr中的任何顶点相邻)(4)对v着色；(5)将v放入newclr；;,void Color(G)GRAPH G;/*类型GRAPH有待具体说明*/SET clr;clr=;while(G中有未着色的顶点)SET newclr=new(SET);/*产生一种新颜色*/greedy(G,newclr);/*用此新颜色对尽可能多的结点进行着色*/将newclr放入clr;,算法 Color(G)完成对图G的着色，其执行结果为clr集合，它即为顶点集的一个划分。其中的每个元素为着相同颜色的顶点集。,哈工大计算机科学与技术学院,数据结构课程组,10,第二步求精,求精v不与newclr中的任何顶点相邻（即对于所有的顶点，都不相邻）,void greedy(G,newclr)GRAPH G;SET newclr;int found;(1)newclr=;(2)for(G中所有未着色的顶点v)(3.1)found=0;/*found的初值为false*/(3.2)for(newclr中的每一个顶点w）(3.3)if(v与w相邻)(3.4)found=1;(3.5)if(found=0)/*v与newclr中的任何顶点都不相邻*/(4)对v着色；(5)将v放入newclr；;,哈工大计算机科学与技术学院,数据结构课程组,11,第三步求精,遍历集合中的所有顶点,void greedy(GRAPH G,SET newclr)int found;newclr=;v=G中第一个未着色的顶点；while(v!=0)/*G中还有未着色的顶点v*/found=0;w=newclr中的第一个顶点；while(w!=0)/*newclr中的顶点还没取尽*/if(v与w相邻)found=1;w=newclr中的下个顶点；;if(found=0)对v着色；将v放入newclr；;v=G中下一个未着色的顶点；;,哈工大计算机科学与技术学院,数据结构课程组,12,第四步求精,引入ADT 根据上一步求精的结果，算法中大部分操作都归结为对图和集合的操作。因此需定义ADT GRAPH和ADT SET。设G为GRAPH的实例，则需在G上定义如下操作：(1)FIRSTG(G)返回G中的第一个未加标记的（未着色的）元素；若G中没有这样的元素存在，则返回NULL。(2)EDGE(v,w,G)若v和w在G中相邻，则返回true，否则返回false。(3)MARK(v,G)标记G中的元素v。(4)ADDG(v,G)将元素v放入G中。(5)NEXTG(G)返回G中下一个未标记的元素，若G中没有这样的元素存在，则返回NULL。设S为SET的实例，则需在S上在定义如下操作：(1)MAKENULL(S)将集合S置空。(2)FIRST(S)返回S中的第一个元素；若S为空集，则返回NULL。(3)NEXT(S)返回S中的下一个元素；若S中没有下一个元素，则返回NULL。(4)ADDS(v,S)将v放入S中,哈工大计算机科学与技术学院,数据结构课程组,13,第五步求精,用引入的ADT对算法进行形式化描述,void greedy(G,newclr)GRAPH G;SET newclr;int found;elementtype v,w;/*elementtype可以自定义*/MAKENULL(newclr);v=FIRSTG(G);while(v!=NULL)found=0;w=FIRST(newclr);while(w!=NULL)if(EDGE(v,w,G)found=1;w=NEXT(newclr);v=NEXTG(G);,哈工大计算机科学与技术学院,数据结构课程组,14,第六步求精,ADT的实现以及整个程序的连编确定抽象数据型GRAPH及SET的数据模型如何实现。编写相应的操作函数。给出类型elementtype的定义和实现。将各部分连在一起。,哈工大计算机科学与技术学院,数据结构课程组,15,2.2 算法评价和复杂性分析,2.2.1算法的评价准则,2.2.2算法时间复杂性分析方法,哈工大计算机科学与技术学院,数据结构课程组,16,2.2.1 算法的评价准则,一：正确性(Correctness)含义：指对一切合法的输入数据经有限时间或有限步后均可得到正确（满足规格说明要求）的结果。算法的正确性证明常有两种途径：形式化证明先构造一组相关的引理和定理，再形式的证明语句系列确实完成了符合规定的正确动作。对于复杂的算法，其正确性的形式证明仍是一个有待突破的课题。验证由于一切合法输入可能是不可穷尽的，所以通常只是构造一些有代表性的输入进行验证（这是我们通常采取的办法）。,哈工大计算机科学与技术学院,数据结构课程组,17,2.2.1 算法的评价准则,二：时间复杂性(Time Complexity)含义：对于同一问题的不同正确算法，其执行时间的多少成为又一评价准则。计算和比较算法的执行时间常有两种方法：实验测量法（即计算其实际执行时间或执行的指令条数）优点：精确。缺点：算法必须编制成可运行程序后才能进行比较；所得的结果过多的依赖于非算法本身的因素，如计算机的硬件、编译程序、编程语言、操作系统等。数学分析法,哈工大计算机科学与技术学院,数据结构课程组,18,时间复杂性的数学分析,可以进行数学分析算法的组成具有一定的规律：由一些基本操作经过三种控制结构（顺序，分支和循环）组成。就可以直接在程序的基础上，分析得出这些基本操作的累加次数，基于这一次数就可比较算法执行时间。时间复杂性的定义对于特定算法，其基本操作的累加次数只和问题的规模n有关，因此是一个关于n的函数，标记为T(n)。由于进行数学分析，主要考虑T(n)的增长率，变化趋势及界限等，其具体数值意义不大；所以主要考虑的是基本操作的重复次数。定义：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间复杂性定义为T(n)=O(f(n)。此处O表示T(n)至多与f(n)同阶，因此也称为渐进时间复杂度（f(n)是T(n)增长率的上界。,哈工大计算机科学与技术学院,数据结构课程组,19,2.2.1 算法的评价准则,三：空间复杂性(Space Complexity)含义：算法的空间复杂性是指算法在执行过程中的存储量需求。其存储量需求主要包括：存放算法本身的指令、常数、变量和输入数据数据进行操作的工作单元和存储实现计算所需的辅助空间第二部分是主要的算法执行的不同时刻，其空间需求可能不同，此处考虑其最大需求。定义：算法在执行过程中的最大存储量需求是关于问题规模n的某个函数f(n)，定义算法的空间复杂度为：S(n)=O(f(n)。,哈工大计算机科学与技术学院,数据结构课程组,20,2.2.1 算法的评价准则,四：可读性(Readability)可读性好的算法有助于设计者和和他人阅读、理解、修改和重用晦涩难懂的算法不容易隐藏错误，而且还增加了阅读难度可读性好的算法，常常也具有简单性。五：健壮性(Robustness)含义：当输入数据非法时，能作出适当的反应（如对输入数据进行语法检查，提出修改输入建议并提供重新输入的机会），避免异常出错。六：灵活性（Flexibility）、可重用性(Reuseabale)和自适应性(Adaptability)等。,哈工大计算机科学与技术学院,数据结构课程组,21,2.2.2 算法时间复杂性分析方法,一：O的含义定义1 设f（n）、T（n）是整数集到实数集上的函数，称函数f（n）是 T（n）增长率的上界，当且仅当存在一个正常数C和整数n0，使得对任意的n n0 时，有T(n)C f(n)。记作：T（n）=O（f（n）此时也表明 T（n）的阶至多为 f（n）例1 设函数T（n）=3n5+4n2+1，则T（n）=（n5）证明：f（n）=n5.取n0=0,C=8,则当n n0时有 T（n）=3n5+4n2+18n5=C f（n）证毕例推广此例得：若 A（n）=amnm+a1n+a0，则 A（n）=（nm）*说明，对于一个为和式的累加次数，其时间复杂性仅取决于该式中最高阶项的阶，而与该最高阶项的系数和其他低阶项无关。常见的时间复杂性有：（1）（n）（n）（n）（nn）（n2）（n3）（2n）,哈工大计算机科学与技术学院,数据结构课程组,22,2.2.2 算法时间复杂性分析方法,各类时间复杂性的直观比较（图形化）,T(n),n,0,1000,2000,3000,5,10,15,20,25,2n,n3,100n,5n2,logn,2100,n,T(n),哈工大计算机科学与技术学院,数据结构课程组,23,2.2.2 算法时间复杂性分析方法,二：时间复杂性的运算法则对于单个语句，无论是赋值、判断、加减等，都有T(n)=O(1)。复合结构（多条语句通过控制结构组合）的T(n)分析需应用如下法则：此处设T1(n)=O(f(n)，T2(n)=O(g(n)分别为程序段P1和P2的运行时间。加法规则（P1和P2顺序连结）：T1(n)+T2(n)=O(max f(n),g(n)乘法规则（P1和P2嵌套连结）：T1(n)T2(n)=O(f(n)g(n),哈工大计算机科学与技术学院,数据结构课程组,24,2.2.2 算法时间复杂性分析方法,三：对三种控制结构进行时间复杂性分析顺序结构：语句序列s1,sk的运行时间由加法原则确定：即T(s1,sk)=maxT(s1),T(sk)分支结构：T(if(B)s1else s2)=T(B)+T(else)+maxT(s1),T(s2)通常取T(B)+T(else)=O(1)循环结构：T(for(i=1;i=n;i+)s)=T(i=1)+(T(for)+T(i=n)+T(i+)+T(s)通常取T(i=1)=O(1);T(for)+T(i=n)+T(i+)=O(1),哈工大计算机科学与技术学院,数据结构课程组,25,算法时间复杂性分析实例(1),例2 A是一个由n个不同元素的实数数组，给出求最大元和最小元的s算法SM时间复杂性。void SM(double A,int n,double max,double min)double max,min;max=min=A0;for(k=1;kmax)max=Ak;if(Akmin)min=Ak;容易看出，算法SM的基本操作为两个判断及赋值语句，基于循环结构的分析T(n)=O(1)+2（n-1）=O(n),哈工大计算机科学与技术学院,数据结构课程组,26,算法时间复杂性分析实例(2),例3：Long fact(int n)if(n=0)|(n=1)return(1);else return(n*fact(n 1);,T(n)=O(G(n-1)+C)=O(n),哈工大计算机科学与技术学院,数据结构课程组,27,算法时间复杂性分析实例(3),例4 A是一个由n个不同元素的实数数组，给出确定实数K是否在A中的算法SK的时间复杂性int SK(double A,int n,double K)int j=1;while(j=n)if(Aj=K)break;else j+;return j;/若j n，则K在A中，否则(j=n+1)K不在A中注：此时，执行次数除了依赖于问题的规模（数组A的大小），还依赖于输入（实数K）。,哈工大计算机科学与技术学院,数据结构课程组,28,2.2.2 算法时间复杂性分析方法,四：平均时间复杂性和最坏时间复杂性定义2 设一问题的输入的规模为n，D n是该问题的所有输入集合，且任一输入I D n的出现概率为P（I），满足 I D n P（I）=1，而算法在输入I 下所执行的基本运算次数为T（I）。此时称 E（n）=I D n P（I）*T（I）为该算法的期望时间复杂性（平均时间复杂性）称 W（n）=max I D n T（I）为该算法的最坏时间复杂性,哈工大计算机科学与技术学院,数据结构课程组,29,时间复杂性分析实例(3)的求解,算法SK的基本操作为元素与K 的比较假定q 表示K 在A 中的概率，且假设K以相同的概率等于A 的每个元素。令D n=I1,I2,In,In+1，其中I j(1 j n)表示K=A j 的输入，In+1 表示K 不是A 中元素的任意一输入。基于如上假设有：当 0 j n 时，P（Ij）=q/n，T（Ij）=j，P（In+1）=1-q，T（In+1）=n所以算法SK的期望时间复杂性和最坏时间复杂性为：E（n）=j D n P（Ij）*T（Ij）=j=1,n+1(q/n)*j+(1-q)*n=1/2(n+1)q+(1-q)n=q/2(1-n)+n=O(n)W（n）=max T（Ij）|1 j n=n=O(n),哈工大计算机科学与技术学院,数据结构课程组,30,作业,1.A是一个包含n个不同元素的实数数组，给出求其最大和最小元素的递归算法和时间复杂性分析。（课下）2.对复数ADT给出规格化描述。（课下）,