第二章算法的构造及评价优秀课件.ppt

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