第二章算法的构造及评价

第二章算法的构造及评价哈工大计算机科学与技术学院数据结构课程组1第1页，课件共30页，创作于2023年2月2.1逐步求精的算法构造过程2.1.1算法的定义1.计算能由一个给定的计算模型机械地执行的规则(或步骤)序列称为该计算模型的一个计算.注:一个计算机程序是一个计算(计算模型是计算机);计算可能永远不停止—不是算法.2.算法是一个满足下列条件的一个计算（程序）：(1)有穷性/终止性：总是在执行有穷步后停止;(2)确定性：每一步必须有严格的定义和确定的动作;(3)能行性：每个动作都能被精确地机械执行;(4)输入：有0个和多个满足约束条件的输入;(5)输出：有一个或多个满足约束条件的结果.第2页，课件共30页，创作于2023年2月2.1.2算法构造过程实际上就是用计算机求解一个问题的过程

1.模型化

对实际问题进行分析，选择适当的数学模型来描述问题，即模型化。

2.确定解决思路根据模型，找出解决问题的思路方法(算法的原型，一般用自然语言描述)。

3.逐步求精对用自然语言等描述的算法逐步细致化、精确化和形式化。这一阶段可能包括多个步骤。当到达适当精度时，许多非形式的描述可转变为基于ADT的形式化描述。

4.ADT的实现对每个ADT，选择适当的数据结构表示数学模型，并用相应的函数实现每个操作。第3页，课件共30页，创作于2023年2月算法逐步求精实例例2.1.2交叉路口的交通安全管理问题DCBAE图2.1一个交叉路口问题描述

一个具有多有多条通路的交叉路口,当允许某些通路上的车辆在交叉路口“拐弯”时,必须对其他一些通路上的车辆加以限制,不允许同时在交叉路口“拐弯”,以免发生碰撞.问题要求

(1)设置一组交通灯,实现安全管理（无碰撞管理）.(2)使交通灯的数目最少.第4页，课件共30页，创作于2023年2月问题的分析所有这些可能的“拐弯”构成一个集合.将此集合分成组,使得每组中所有的“拐弯”都能同时进行而不发生碰撞.每组对应一个指挥灯,保证不碰撞;用尽可能少的指挥灯归结为分成尽可能少的组.问题归结为如何进行集合的划分？第5页，课件共30页，创作于2023年2月模型化(1)用图作为交叉路口的数学模型;(2)每个“拐弯”对应图中的一个顶点;(3)若两个“拐弯”不能同时进行,则用用一条边把这两个“拐弯”所对应的两个结点连接起来，并且说这两个顶点是相邻的。ABACADBADCEDBCBDEADADBEBECDCBAE一个交叉路口第6页，课件共30页，创作于2023年2月算法的基本思路转化为图的着色问题（着同一颜色的结点即为一组）。常见算法为（1）穷举法（2）试探法（3）贪心法“贪心”算法的基本思想是首先用第一种颜色对图中尽可能多的顶点着色(尽可能多表现出“贪心”)，然后用第二种颜色对余下的顶点中尽可能多的顶点着色，如此等等，直至所有的顶点都着完色。第7页，课件共30页，创作于2023年2月算法原型（自然语言描述）（1）将所有的结点设置为未着色（2）当有未着色的结点时，进行如下步骤（3）产生一种新的颜色（4）选取某个未着色的点，用此新颜色对其着色（5）扫描所有未着色的顶点，对其中的每个顶点尽可能的用此新颜色着色。（依据为它是否与已着新颜色的任何顶点相邻。若不相邻，则用新颜色对它着色。）（此处体现了贪心）。（6）重复步骤（2）-（5），直到所有的结点均以着色第8页，课件共30页，创作于2023年2月第一步求精（伪代码描述）

voidgreedy(G,newclr)GRAPHG;SETnewclr;/*类型GRAPH和SET有待具体说明*//*本程序把G中可以着同一色的顶点放入newclr*/{(1)newclr=

(2)for(G中所有未着色的顶点v)(3)if(v不与newclr中的任何顶点相邻){(4)对v着色；(5)将v放入newclr；}};

voidColor(G)GRAPHG;/*类型GRAPH有待具体说明*/{SETclr;clr=

;while(G中有未着色的顶点){SETnewclr=new(SET);/*产生一种新颜色*/greedy(G,newclr);/*用此新颜色对尽可能多的结点进行着色*/将newclr放入clr;}};算法Color(G)完成对图G的着色，其执行结果为clr集合，它即为顶点集的一个划分。其中的每个元素为着相同颜色的顶点集。第9页，课件共30页，创作于2023年2月第二步求精求精v不与newclr中的任何顶点相邻（即对于所有的顶点，都不相邻）voidgreedy(G,newclr)GRAPHG;SETnewclr;{intfound;(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；}}};第10页，课件共30页，创作于2023年2月第三步求精遍历集合中的所有顶点voidgreedy(GRAPHG,SETnewclr){intfound;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页，创作于2023年2月第四步求精引入ADT

根据上一步求精的结果，算法中大部分操作都归结为对图和集合的操作。因此需定义ADTGRAPH和ADTSET。设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页，创作于2023年2月第五步求精用引入的ADT对算法进行形式化描述voidgreedy(G,newclr)GRAPHG;SETnewclr;{

intfound;elementtypev,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页，创作于2023年2月第六步求精ADT的实现以及整个程序的连编确定抽象数据型GRAPH及SET的数据模型如何实现。编写相应的操作函数。给出类型elementtype的定义和实现。将各部分连在一起。第14页，课件共30页，创作于2023年2月2.2算法评价和复杂性分析2.2.1算法的评价准则2.2.2算法时间复杂性分析方法第15页，课件共30页，创作于2023年2月2.2.1算法的评价准则一：正确性(Correctness)含义：指对一切合法的输入数据经有限时间或有限步后均可得到正确（满足规格说明要求）的结果。算法的正确性证明常有两种途径：形式化证明先构造一组相关的引理和定理，再形式的证明语句系列确实完成了符合规定的正确动作。对于复杂的算法，其正确性的形式证明仍是一个有待突破的课题。验证由于一切合法输入可能是不可穷尽的，所以通常只是构造一些有代表性的输入进行验证（这是我们通常采取的办法）。第16页，课件共30页，创作于2023年2月2.2.1算法的评价准则二：时间复杂性(TimeComplexity)含义：对于同一问题的不同正确算法，其执行时间的多少成为又一评价准则。计算和比较算法的执行时间常有两种方法：实验测量法（即计算其实际执行时间或执行的指令条数）优点：精确。缺点：算法必须编制成可运行程序后才能进行比较；所得的结果过多的依赖于非算法本身的因素，如计算机的硬件、编译程序、编程语言、操作系统等。数学分析法第17页，课件共30页，创作于2023年2月时间复杂性的数学分析可以进行数学分析算法的组成具有一定的规律：由一些基本操作经过三种控制结构（顺序，分支和循环）组成。就可以直接在程序的基础上，分析得出这些基本操作的累加次数，基于这一次数就可比较算法执行时间。时间复杂性的定义对于特定算法，其基本操作的累加次数只和问题的规模n有关，因此是一个关于n的函数，标记为T(n)。由于进行数学分析，主要考虑T(n)的增长率，变化趋势及界限等，其具体数值意义不大；所以主要考虑的是基本操作的重复次数。定义：算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间复杂性定义为T(n)=O(f(n))。此处O表示T(n)至多与f(n)同阶，因此也称为渐进时间复杂度（f(n)是T(n)增长率的上界。第18页，课件共30页，创作于2023年2月2.2.1算法的评价准则三：空间复杂性(SpaceComplexity)含义：算法的空间复杂性是指算法在执行过程中的存储量需求。其存储量需求主要包括：存放算法本身的指令、常数、变量和输入数据数据进行操作的工作单元和存储实现计算所需的辅助空间第二部分是主要的算法执行的不同时刻，其空间需求可能不同，此处考虑其最大需求。定义：算法在执行过程中的最大存储量需求是关于问题规模n的某个函数f(n)，定义算法的空间复杂度为：S(n)=O(f(n))。第19页，课件共30页，创作于2023年2月2.2.1算法的评价准则四：可读性(Readability)可读性好的算法有助于设计者和和他人阅读、理解、修改和重用晦涩难懂的算法不容易隐藏错误，而且还增加了阅读…难度可读性好的算法，常常也具有简单性。五：健壮性(Robustness)含义：当输入数据非法时，能作出适当的反应（如对输入数据进行语法检查，提出修改输入建议并提供重新输入的机会），避免异常出错。六：灵活性（Flexibility）、可重用性(Reuseabale)和自适应性(Adaptability)等。第20页，课件共30页，创作于2023年2月2.2.2算法时间复杂性分析方法一：O的含义定义1

设f（n）、T（n）是整数集到实数集上的函数，称函数f（n）是T（n）增长率的上界，当且仅当存在一个正常数C和整数n0，使得对任意的n≥n0时，有T(n)≤Cf(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+1≤8n5=Cf（n）证毕例推广此例得：若A（n）=amnm+…+a1n+a0，则A（n）=О（nm）

*说明，对于一个为和式的累加次数，其时间复杂性仅取决于该式中最高阶项的阶，而与该最高阶项的系数和其他低阶项无关。常见的时间复杂性有：О（1）<О（㏒㏒n）<О（㏒n）<О（n）<О（n㏒n）<О（n2）<О（n3）<О（2n）第21页，课件共30页，创作于2023年2月2.2.2算法时间复杂性分析方法各类时间复杂性的直观比较（图形化）T(n)n01000200030005101520252nn3100n5n2logn2100△n△

T(n)第22页，课件共30页，创作于2023年2月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))第23页，课件共30页，创作于2023年2月2.2.2算法时间复杂性分析方法三：对三种控制结构进行时间复杂性分析顺序结构：语句序列s1,…,sk的运行时间由加法原则确定：即T(s1,…,sk)=max{T(s1),…,T(sk)}分支结构：T(if(B)s1elses2)=T(B)+T(else)+max{T(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)第24页，课件共30页，创作于2023年2月算法时间复杂性分析实例(1)例2A是一个由n个不同元素的实数数组，给出求最大元和最小元的s算法SM时间复杂性。voidSM(doubleA[],intn,doublemax,doublemin){doublemax,min;max=min=A[0];for(k=1;k<=n-1;k++){if(A[k]>max)max=A[k];if(A[k]<min)min=A[k];}}容易看出，算法SM的基本操作为两个判断及赋值语句，基于循环结构的分析T(n)=O(1)+2（n-1）=O(n)第25页，课件共30页，创作于2023年2月算法时间复杂性分析实例(2)例3：Longfact

(intn)

{if(n==0)||(n==1)return(1);elsereturn(n*fact(n–1));}T(n)=C当n=0,n=1G+T(n–1)当n>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)=C∴T(n)=G（n-1）+C∴T(n)=O(G(n-1)+C)=O(n)第26页，课件共30页，创作于2023年2月算法时间复杂性分析实例(3)例4

A是一个由n个不同元素的实数数组，给出确定实数K是否在A中的算法SK的时间复杂性intSK(doubleA[],intn,doubleK){intj=1;while(j<=n){if(A[j]==K)break;elsej++;}returnj;//若j≤n，则K在A中，否则(j=n+1)K不在A中}注：此时，执行次数除了依赖于问题的规模（数组