数据结构窦延平版的讲义--1_时间复杂性

1物料管理INTRO1数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析1、算法：一个算法就是有穷规则的集合，其中的规则规定了一个解决某一个特定问题的运算序列。2、算法的时间复杂性和空间复杂性：·问题的规模(n)：或大小。如：矩阵的阶数、图的结点个数、被分类序列的正整数个数……·时间复杂性：算法的所需的时间和问题规模的函数。记为T(n)。当n-∞时的时间复杂性，被称之为渐进时间复杂性。·空间复杂性：算法的所需的空间和问题规模的函数。记为T(n)。当n-∞时的时间复杂性，被称之为渐进空间复杂性。·最坏情况下的时间复杂性和平均情况下的时间复杂性。最坏情况下的时间复杂性：平均情况下的时间复杂性：3、大O表示法：·定义；如果存在着正的常数c和自然数n0，当n=n0时；有f(n)=Cg(n)成立，则称f(n)=O（g(n))。在算法分析中，如果一个的算法的时间复杂性是O(g(n))，读作g(n)“级”的或“阶”的。如：线性阶的、平方阶的、立方阶的……2物料管理INTRO2数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析·例1、设T(n)=(n+1)2=n2+2n2+1=n2+2n2+n2;在n=1时，等式成立，n1时，式成立选n0=1,c=4;T(n)=4n2。所以，T(n)=O(n2)·例2、设T(n)=3n3+2n2选n0=0,c=5;T(n)=5n3。所以，T(n)=O(n3)同理：选n0=0,c=5;T(n)=5n4。所以，T(n)=O(n4)？？？注意：符合定义，但在算法分析中是没有意义的。在算法分析中，通常所说的找到了时间复杂性的级别，是指找到了同样级别的最简单的函数。如：307n2、n2/2、n2都是同一级别的函数，最简单的函数是n2。所以，307n2、n2/2、n2的级别都是O(n2)。f、g同级别：满足：f=O(g)且g=O(f),·例3、设T(n)=3n!=O(2n)注意：f(n)=O(g(n))意味着找到了f(n)的一个最“紧贴”的上界g(n))。或者说找到了最低的上界。从算法的时间复杂性角度来看，象例2中的O(n4)是没有意义的。3物料管理INTRO3数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析紧贴渐进界：设存在一个函数f(n)=O(g(n))，如果对于每一个函数h(n)都使得f(n)=O(h(n))，也使得g(n)=O(h(n))，就说g(n)是f(n)的紧贴渐进界。例如：f(n)=3n+5；f(n)=O(n)同样根据定义f(n)=O(n2)。但是，我们通常所讲的f(n)的紧贴渐进界是f(n)=O(n)，而不是f(n)=O(n2)。这可用反证法加以证明。反证法：上例中g(n)=n。假设g(n)=n不是f(n)=3n+5的紧贴渐进界，那么必定存在一个函数h(n)，使得f(n)=3n+5=O(h(n))，但g(n)!=h(n)。由于3n+5=O(h(n))，那么根据大O法的定义，必定存在二个正数c和n0，使得对于所有的n=n0，3n+5=ch(n)。很显然，对一切n=0，有n=3n+5，所以g(n)=ch(n)。这样，根据大O法的定义有g(n)=O(h(n))。但这是同假设相矛盾的。因此，f(n)=O(n)是一个紧贴渐进界。关于更严格的“紧贴渐进界”的概念，请看一下的定义。4物料管理INTRO4数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析·时间复杂性分析的注意：1、时间复杂性函数无时间单位。2、上例采用的是均匀时间耗费。以简单语句的耗费时间为1。3、如循环语句，条件：O(1)+THENORELSE后的语句的时间耗费之和。4、循环语句，先里后外，逐步求和。4、时间复杂性的级别的判断：级别越低越好。·ifLimf(n)/g(n)=c;这里c是常数。f(n)、g(n)同级别。n-∞·ifLimf(n)/g(n)=0;这里c是常数。f(n)级别低。n-∞·ifLimf(n)/g(n)=∞;这里c是常数。g(n)级别低。n-∞如：Limlogn/n=LimLn(n)loge/n=Lim(loge/n)/1=Limloge/n=0;logn级别低。注意：这里使用了罗彼特的求极限的法则。n-∞n-∞n-∞n-∞O(logn)和O(n1/2)？？？5物料管理INTRO5数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析5、大Ω表示法：·定义；如果存在着正的常数c和自然数n0，当n=n0时；有f(n)=Cg(n)成立，则称f(n)=Ω(g(n))。·例1、设T(n)=(n+1)2=n2+2n2+1=n2;在n为任何数时，所以，T(n)=Ω(n2)·例2、设T(n)=3n3+2n2T(n)=3n3。所以，T(n)=Ω(n3)同理：T(n)=5n2。所以，T(n)=Ω(n2)？？？注意：符合定义，但在算法分析中是没有意义的。Ω:找尽可能高的下界。6、Θ表示法：·定义；如果存在着正的常数c1、c2和自然数n0，当n=n0时；有C1×g(n)=f(n)=C2×g(n)成立，则称f(n)=Θ(g(n))。·例1、设T(n)=(n+1)2=Θ(n2)6物料管理INTRO6数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析1。下述两个程序段的作用都是将数组inta〔n〕的前n-1数组元素置为和其数组元素的下标相同的值，且最后一个数组元素置为-1,即a〔n-1〕=-1。两段程序那个好一些，那个差一些(从算法的时间复杂性角度考虑)A.for(i=0;in-1;++i)a〔i〕=i;a〔n-1〕=-1;B.for(i=0;in;++i){if(i==n-1)a[n-1〕=-1;elsea〔i〕=i;}解：程序A执行的语句次数为n次，而程序B执行的语句次数为2n次,故而程序B更好一些。时间省。2。以下是计算n!的递归程序，求其时间复杂性的级别：intf(intn){intm;if(n=1)m=1;elsem=n*f(n-1);returnm;}7物料管理INTRO7数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析解：根据上述程序的语句执行次数可得：2ifn=1T(n)=T(n-1)+2else解本递归式可得：T(n)=2T(n-1)+2=2(2T(n-2)+2)+2=…=O(n)答：本程序的程序时间复杂性的级别是线性级的。3、将下列算法的时间复杂性的级别，按由低到高的顺序排成一列；O(n4),O(1),O(n3),O(n×n1/2),O(logn),O(nlogn),O(n1/2),O(n2),O(2n)解：由低到高的顺序为：O(1),O(logn),O(n1/2),O(n*logn),O(n*n1/2),O(n2),O(n3),O(n4),O(2n),8物料管理INTRO8数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析4、下面的算法为计算x的n次幂的值(y=x^n)，求其时间复杂性的级别，注意x和n都是正整数：。。scanf(“%d”,&x);scanf(“%d”,&n);y=x;while(n1){y=y*x;n=n-1}printf(“%d”,y);.解：考察各个语句的执行次数，并把他们相加，可得到该程序的时间复杂性级别为：T(n)=1+1+1+n+2n-2+1=O(n)111n2n-219物料管理INTRO9数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析5、下面的算法为计算x的n次幂的值(y=x^n)的另一种算法，求其时间复杂性的级别，注意x和n都是正整数：。。scanf(“%d”,&x);scanf(“%d”,&n);m=n;t=1;while(m0){m=m/2;t=t*2;}m=n;y=1;while(t1){t=t/2;y＝y*y;if(n=t){y=y*x;n=n-t;}}printf(“%d”,y);..111111Logn+2Logn+1Logn+1Logn+2Logn+1Logn+1Logn+1代价=3()110物料管理INTRO10数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析解：将上一页的语句执行相加次数，可得到总的执行次数，故：T(n)=9logn+17=O(logn)算法的工作原理，可用求x55来加以说明：x55=x110111=x32+16+0+4+2+1来加以说明。程序的第一个while求出=55的最小的2的正整数幂64，64/2可得到32，在程序的第二个while中用到它。在程序的第二个while中：55-32=23得到x110111中的幂指数中的最左位的123-16=7得到x110111中的幂指数中的左起第二位的17-80得到x110111中的幂指数中的左起第三位的07-4=3得到x110111中的幂指数中的左起第4位的13-2=1得到x110111中的幂指数中的左起第5位的11-1=0得到x110111中的幂指数中的左起第6三位的1知道了上述求法之后，求x110111就很方便了：11物料管理INTRO11数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析解：知道了上述求法之后，求x110111就很方便了：先求x1，1*x=》y再求x11，x11=x10*x1=x10*x1=》y*y*x=》y再求x110，x110=x11*x11=》y*y其余，依次类推。