2011算法第一、二讲

,ECNU,Liu Yinping,算法设计与分析,ECNU,Yinping Liu,ECNU,Yinping Liu,课程目标,通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。,培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。,鼓励学生运用算法知识解决实际问题，培养他们的独立科研能力和理论联系实践的能力。,参考教材,1. 算法设计技巧与分析 吴伟昶 方世昌 等译,电子工业出版社,2. 算法设计与分析基础 (影印版),美 ,Anany,Levitin,著,3. 数据结构、算法与应用,C+,语言描述.,Sartaj,Sahni,著. 汪诗林，孙晓东等译.,机械工业出版社.,2000,年,1,月第,1,版,主要内容介绍,第1章算法引论,第2章 矩阵计算,第3章递归与分治策略,第4章动态规划,第5章贪心算法,第6章回溯法,第7章随机概率算法,第,8,章 计算几何学,第,9,章,NP,完全性理论,主要内容介绍（续）,第1章 算法引论,本章主要知识点：,1.1算法与程序,1.2表达算法的抽象机制,1.3描述算法,1.4算法复杂性分析,1.1算法与程序,算法：,是满足下述性质的指令序列。,输 入：有零个或多个外部量作为算法的输入。,输 出：算法产生至少一个量作为输出。,确定性：组成算法的每条指令清晰、无歧义。,有限性：算法中每条指令的执行次数有限，执行,每条指令的时间也有限。,程序：,是算法用某种程序设计语言的具体实现。,程序可以不满足算法的性质(4)即有限性。,1.2表达算法的抽象机制,1.从机器语言到高级语言的抽象,高级程序设计语言的主要好处是：,（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需,要几周时间的培训就可以胜任程序员的工作；,（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计,出来的程序可读性好，可维护性强，可靠性高；,（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而,所写出来的程序可植性好、重用率高；,（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，,程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。,1.2表达算法的抽象机制,2.抽象数据类型,抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。,抽象数据类型,带给算法设计的,好处,有,：,（1）算法顶层设计与底层实现分离；,（2）算法设计与数据结构设计隔开，允许数据结构自由选择；,（3）数据模型和该模型上的运算统一在,ADT,中,便于空间和时间耗费折衷；,（4）用抽象数据类型表述的算法具有很好的可维护性；,（5）算法自然呈现模块化；,（6）为自顶向下逐步求精和模块化提供有效途径和工具；,（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。,1.,3,复杂性分析初步,程序性能,(,program performance),是指运行一个程序所需的内存大小和时间多少。所以，程序的性能一般指程序的空间复杂性和时间复杂性。性能评估主要包含两方面, 即,性能分析,(,performance analysis),与,性能测量,(,performance measurement),前者采用分析的方法，后者采用试验的方法。,考虑空间复杂性的理由,在多用户系统中运行时，需指明分配给该程序的内存大小；,想预先知道计算机系统是否有足够的内存来运行该程序；,一个问题可能有若干个不同的内存需求解决方案,从中择取,;,用空间复杂性来估计一个程序可能解决的问题的最大规模。,考虑时间复杂性的理由,某些计算机用户需提供程序运行时间的上限,(,用户可接受的,);,所开发的程序需要提供一个满意的实时反应。,选取方案的规则,： 如果对于解决一个问题有多种可选的方案，那么方案的选取要基于这些方案之间的性能差异。对于各种方案的时间及空间的复杂性，,最好采取加权的方式进行评价,。但是随着计算机技术的迅速发展，,对空间的要求往往不如对时间的要求那样强烈,。,因此我们这里的分析主要强调时间复杂性的分析。, 1 空间复杂性,程序所需要的空间,：,指令空间,-用来存储经过编译之后的程序指令。程序所需的指令空间的大小取决于如下因素：,把程序编译成机器代码的编译器；,编译时实际采用的编译器选项；,目标计算机。,数据空间,-用来存储所有常量和变量的值。分成两部分：,a.),存储常量和简单变量；,b.),存储复合变量。,前者所需的空间取决于所使用的计算机和编译器，以及变量与常量的数目，这是由于我们往往是指计算所需内存的字节数，而每个字节所占的数位依赖于具体的机器环境。后者包括数据结构所需的空间及动态分配的空间。,类型 占用字节数 适用范围,char 1 -128127,unsigned char 1 0 255,short 2 -32768-32767,int 2 -32768-32767,unsigned int 2 0-65535,long 4 -2,31,- 2,31,-1,unsigned long 4 0- 2,31,-1,float 4,3.4E 38,double 8 1.7E 308,pointer 2,计算方法：结构变量所占空间等于各个成员所占空间的累加；数组变量所占空间等于数组大小乘以单个数组元素所占的空间。 例如：,double a100;,所需空间为： 100,8=800,int matrixrc;,所需空间为 2,r,c,环境栈空间,-保存函数调用返回时恢复运行所需要的信息。当一个函数被调用时，下面数据将被保存在环境栈中：,返回地址；,所有局部变量的值、递归函数的传值形式参数的值；,所有引用参数以及常量引用参数的定义。,在分析空间复杂性中，,实例特征的概念特别重要,。所谓,实例特征是指决定问题规模的那些因素,。如，输入和输出的数量或相关数的大小，如对,n,个元素进行排序、,n,n,矩阵的加法等。都可以,n,作为实例特征， 两个,m,n,矩阵的加法应该以,n,和,m,两个数作为实例特征。,一个程序所需要的空间可分为两部分：,固定部分,，它独立于实例特征。主要包括指令空间、简单变量以及,定义复合变量所占用的空间、常量所占用的空间。,可变部分,，主要包括复合变量所需的空间（其大小依赖于所解决的具体问题）。动态分配的空间（依赖于实例特征）、递归栈所需的空间（依赖于实例特征）。,令,S(P),表示程序,P,所需的空间，则有,S(P）=c+S,p,(,实例特征),其中,c,表示固定部分所需要的空间,，是一个常数；,S,p,表示可变部分所需的空间,。在分析程序的空间复杂性时，一般着重于估算,S,p,(,实例特征)。,实例特征的选择一般受到相关数的数量以及程序输入和输出规模的制约。,注,：一个精确的分析还应当包括编译期间所产生的临时变量所需的空间，这种空间与编译器直接相关联，在递归程序中除了依赖于递归函数外，还依赖于实例特征。但是，在考虑空间复杂性时，一般都被忽略。,例子：,例,1,利用应用参数,Template ,T abc( T &a, T &b, T &c),Return a+b+c+b,c+(a+b+c)/(a+b)+4;,在例,1,中，采用,T,作为实例特征。,由于,a,b,c,都是引用参数，在函数中不需要为它们的值分配空间，但需保存指向这些参数的指针,。若每个指针需要2 个字节，则共需要6个字节的指针空间，此时函数所需要的总空间是一个常量，而,Sabc(,实例特征)=0。 但,若函数,abc,的参数是传值参数，则每个参数需要分配空间,sizeof(T),的空间,，于是,a,b,c,所需的空间为：3,sizeof(T).,函数,abc,所需要的其他空间都与,T,无关，故,Sabc(,实例特征)=,3,sizeof(T)。,如果假定,使用,a,b,c,的大小作为实例特征,，由于在传值参数的情形下，分配给每个变量,a, b, c,的空间均为,sizeof(T),而不考虑这些变量中的实际值是多大，所以，不论是用引用参数还是使用传值参数，都有,Sabc(,实例特征)=,0,。,例,2,顺序搜索,template ,int SequentialSearch(T a,const T &x, int n), /,在,a0:n-1,中搜索,x，,若找到则回所在的位置，否则返回-1,int i;,for(i=0; in ,if (i=n) return 1;,return i;,在例,2,中，假定,采用被查数组的长度,n,作为实例特征,，并取,T,为,int,类型,。数组中每个元素需要 2 个字节，实参,x,需要2 个字节，传值形式参数,n,需要2 个字节，局部变量,i,需要2 个字节，整数常量 1 需要2 个字节，所需要的总的数据空间为 10 个字节，其,独立于,n,所以,S,顺序查找,(,n)=0.,这里,我们并没有把数组,a,所需的空间计算进来，因为该数组所需的空间已在定义实际参数(对应于,a),的函数中分配，不能再加到函数,SequentialSearch,所需的空间上去,。, 2 时间复杂性,时间复杂性的构成,一个程序所占时间,T(P)=,编译时间,+,运行时间,；,编译时间与实例特征无关，而且，一般情况下，一个编译过的程序可以运行若干次，所以，,人们主要关注的是运行时间,，记作,t,p,(,实例特征）；,如果了解所用编译器的特征，就可以确定代码,P,进行加、减、乘、除、比较、读、写等所需的时间，从而得到计算,t,p,的公式。令,n,代表实例特征（这里主要是问题的规模），则有如下的计算公式：,t,p,(n,)=,c,a,ADD(n)+c,s,SUB(n)+c,m,MUL(n)+c,d,DIV(n)+c,c,CMP(n,)+,其中，,c,a，,c,s，,c,m，,c,d，,c,c,分别表示一次加、减、乘、除及比较操作所需的时间，函数,ADD, SUB, MUL, DIV, CMP,分别表示代码,P,中所使用的加、减、乘、除及比较操作的次数；,一个,算术操作所需的时间取决于操作数的类型,(,int, float, double,等等），所以，有必要对操作按照数据类型进行分类；,在构思一个程序时，影响,t,p,的许多因素还是未知的，所以，在多数情况下仅仅是对,t,p,进行估计。,估算运行时间的方法,：,A.,找一个或多个关键操作,，确定这些关键操作所需要的执行时间（对于前面所列举的四种运算及比较操作，一般被看作是基本操作，并约定所用的时间都是一个单位）；,B.,确定程序总的执行步数,。,操作计数,首先选择一种或多种操作（如加、乘和比较等），然后计算这些操作分别执行了多少次。关键操作对时间复杂性影响最大。,例,3,寻找最大元素,template,int Max(T a,int n), /,寻找,a0:n-1,中的最大元素,int pos=0;,for(i=1; in; i+),if(aposai),pos=i;,return pos;,这里关键操作是比较。,For,循环中共进行了,n-1,次比较。,Max,还执行了其它比较，如,for,循环每次执行之前都要比较一下,i,和,n.,此外，,Max,还进行了其它的操作，如初始化,pos、,循环控制变量,i,的增量。这些一般都不包含在估算中，若纳入计数，则操作计数将增加一个常量。,例,4 n,次多项式求值,template,T PolyEval(T coeff, int n, const T& x), /,计算,n,次多项式的值，,coeff0:n,为多项式的系数,T y=1, value=coeff0;,for(i=1;i=n;i+) /n,循环, /,累加下一项,y,=x; /,一次乘法,value+=ycoeffi; /,一次加法和一次乘法,return value;, / 3n,次基本操作,例,5,例,6,template template,void Rank(T a,int n,int r) void SelectionSort(T a,int n), /,计算,a0:n-1,中元素的排名 / 对数组,a0:n-1,中元素排序,for(int i=1; i1;size-),ri=0; /,初始化 ,j=Max(a, size);,/,逐对比较所有的元素,Swap(aj,asize-1);,for(int i=1;in;i+) ,for (j=0;ji;j+) ,if (ajai) ri+; /,其中函数,Max,定义如例,3,else rj+； /,函数,Swap,由下述给出,template,inline void Swap(T &a, T &b), T temp=a; a=b; b=temp; ,在这两个程序中，关键的操作是比较。 在例,5,中，对每个,i,的取值，执行比较的次数是,i,总的比较次数为 1+2+(,n-1)=(n-1)n/2.,在此，,for,循环的额外开销、初始化数组,r,的开销、以及每次比较,a,中的两个数时对,r,进行的增值开销都未列入其中。,在例,6,给出的排序中，首先找出最大元素，把它移动到,an-1,然后在余下的,n-1,个中再寻找最大的元素，并把它移动到,an-2,如此进行下去，此种方法称为选择排序(,selection sort).,从例,3,中已经知道，每次调用,Max(a,size),需要进行,size-1,次比较，所以总的比较次数为1+2+,n-1=(n-1)n/2.,每调用一次函数,Swap,需要执行三次元素移动，所以总的移动次数为 3(,n-1).,当然，在本程序中，还会有其他开销，在此未予考虑。,注,：人们往往还会关心最好的、最坏的和平均的操作步数是多少。,在上面的计算中我们都考虑的是最坏的情况,。,执行步数,利用操作计数方法估计程序的时间复杂性注意力集中在“关键操作”上，忽略了所选择操作之外其它操作的开销。下面所要讲的统计执行步数（,step-count),的方法则要统计程序/函数中所有部分的时间开销。,执行步数也是实例特征的函数。通常做法是选择一些感兴趣的实例特征,。如，要了解程序的运行时间是如何随着输入数据的个数增加而增加的，则把执行步数仅看作输入数据个数的函数。所谓,程序步,是一个语法或语义上的程序片断，该片断的执行时间独立于实例特征。例如语句：,return a+b+b*c+(a+b+c)/(a+b)+4;,和,x=y;,都可以作为程序步。一种直观的统计程序执行步数的方法是做执行步数统计表,.,矩阵加法程序执行步数统计表,语句,s/e,频率 总步数,Void Addm(T*a, ) 0 0 0, 0 0 0,for(int i=0;irows;i+) 1 rows+1 rows+1,for(int j=0;j=0。,渐近符号,O,的定义：,f(n)=O(g(n),当且仅当存在正的常数,c,和,n,0,，,使得对于所有的,n=n,0,，,有,f(n)=cg(n)。,此时，称,g(n),是,f(n),的一个上界。,函数,f,至多是函数,g,的,c,倍，除非,nn,0,。,即是说，当,n,充分大时，,g,是,f,的一个上界函数，在相差一个非零常数倍的情况下。通常情况下，上界函数取单项的形式，如表1 所列。,C,0,=O(1): f(n),等于非零常数的情形。,3,n+2=O(n):,可取,c4，n,0,2。,100n+6=O(n):,可取,c=101，n,0,6。,10n,2,+4n+3=O(n,2,):,可取,c=11,n,0,6,62,n,+n,2,=O(2,n,):,可取,c =7，n,0,=4.,3log n + 2n + n,2,=O(n,2,).,nlog n +n,2,=O(n,2,).,3n+2=O(n,2,).,注意事项,1.用来作比较的函数,g(n),应该尽量接近所考虑的函数,f(n).,3n+2=O(n,2,),松散的界限；3,n+2=O(n),较好的界限。,2.不要产生错误界限。,n,2,+100n+6，,当,n3,时，,n,2,+100n+6c-100,就有,n,2,+100n+6cn。,同理，3,n,2,+42,n,=O(n,2,),是错误的界限。,3.,f(n)=O(g(n),不能写成,g(n)=O(f(n)，,因为两者并不等价。实际上，这里的等号并不是通常相等的含义。按照定义，用集合符号更准确些：,O(g(n)=f(n)|f(n),满足：存在正的常数,c,和,n,0,，,使得当,n=n,0,时，,f(n)=cg(n)。,所以，人们常常把,f(n)=O(g(n),读作：“,f(n),是,g(n),的一个大,O,成员”。,大,O,比率定理,：对于函数,f(,n,),和,g,(,n,),如果极限 存在,则,f(n)=,O(g(n),.,当且仅当存在正的常数,c,使得,例子 因为 所以 3,n+2=O(n);,因为 所以 10,n,2,+4n+2=O(n,2,);,因为 所以 6,2,n,+n,2,=O(2,n,);,因为 所以,n,16,+3,n,2,=O(2,n,);,本例最后一个不是一个好的上界估计，问题出在极限值不是正的常数。,例如, 根据上述定理， 我们很容易得出：,符号,的定义,(,f(n,)=,(g(n),当且仅当存在正的常数,c,和,n,0,，,使得对于所有的,n,n,0,，,有,f,(,n,),c,(,g,(,n,),。,此时，称,g(n),是,f(n),的一个下界。,函数,f,至少是函数,g,的,c,倍，除非,n,0,则,小,o,符号定义：,f(n)= o (g(n),当且仅当,f(n)= O(g(n),和,g(n),O,(f(n).,例,7,折半搜索,Template ,Int BinarySearch(T a , const T, x, int n),/,在,a0=a1=an-1,中搜索,x,/,如果找到，则返回所在位置，否则返回 -1,int left=0; int right=n-1;,while(leftamiddle) left=middle+1;,else right=middle-1;,Return -1 ; /,未找到,x,while,的每次循环(最后一次除外)都将以减半的比例缩小搜索范围, 所以, 该循环在最坏的情况下需要执行,(,log,n,),次.由于每次循环需耗时,(1),因此在最坏情况下,总的时间复杂性为,(log n).,本章作业,1.,多项式求值(,Horner,规则),假设有,n+2,个实数,a,0, a,1, , a,n,和,x,的序列，要对多项式,P,n,(x)=a,n,x,n,+ a,n-1,x,n-1,+ + a,1,x +a,0,求值。直接的方法是对每一项分别求值, 这种方法是十分低效的, 因为它需要,n+n-1+1=n(n+1)/2,次乘法。,通过如下的归纳法，可以导出一种快得多的方法，首先观察,P,n,(x)=,a,n,x,n,+ a,n-1,x,n-1,+ + a,1,x +a,0,=(a,n,x+a,n-1,)x+a,n-2,)x+a,n-3,)x+a,1,)x+a,0,这种求值的安排称为,Horner-,规则。用这种安排可导出以下更有效的方法。假设已经知道如何对,P,n-1,(x)=,a,n-1,x,n-1,+ a,n-2,x,n-2,+ + a,1,x +a,0,求值，那么再用一次乘法和一次加法，则有,P,n,(x) = xP,n-1,(x) +a,0,这种多项式求值的方法被称为,HORNER,算法,。,请估算,HORNER,算法的渐近复杂性。,2. 计算,BubbleSort,的渐近复杂性。,