《{时间管理}数据结构窦延平版的讲义时间复杂性》由会员分享，可在线阅读，更多相关《{时间管理}数据结构窦延平版的讲义时间复杂性（11页珍藏版）》请在金锄头文库上搜索。
1、1、算法和算法分析,1、算法：一个算法就是有穷规则的集合，其中的规则规定了一个解决某一个特定问题的运算 序列。,2、算法的时间复杂性和空间复杂性：,问题的规模(n)：或大小。如：矩阵的阶数、图的结点个数、被分类序列的正整数个数 时间复杂性：算法的所需的时间和问题规模的函数。记为 T(n)。当 n- 时的时间复杂 性，被称之为渐进时间复杂性。 空间复杂性：算法的所需的空间和问题规模的函数。记为 T(n)。当 n- 时的时间复杂 性，被称之为渐进空间复杂性。,最坏情况下的时间复杂性和平均情况下的时间复杂性。 最坏情况下的时间复杂性： 平均情况下的时间复杂性：,3、大 O 表示法：,定义；如果存在着
2、正的常数 c 和自然数 n0，当 n = n0 时；有 f (n) = Cg(n) 成立，则 称 f( n ) = O（g( n ) 。 在算法分析中， 如果一个的算法的时间复杂性是O(g( n )，读作 g( n ) “ 级 ” 的 或 “ 阶 ” 的。 如： 线性阶的、平方阶的、立方阶的 ,1、算法和算法分析,例1、 设 T(n) = (n+1)2 = n2+2n2 +1 1 时， 式成立 选 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) =
3、O(n3) 同理：选 n0 = 0, c=5 ; T(n) = 5n4。所以，T(n) = O(n4)？ 注意：符合定义，但在算法分析中是没有意义的。 在算法分析中，通常所说的找到了时间复杂性的级别，是指找到了同样级别的最 简单的函数。 如：307 n2、 n2/2、 n2 都是同一级别的函数，最简单的函数是n2 。所以， 307 n2、 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) 。或者说找 到了
4、最低的上界。从算法的时间复杂性角度来看，象例2 中的 O(n4) 是没有 意义的。,1、算法和算法分析,紧贴渐进界：设存在一个函数 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的紧贴渐进界，那么必
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 = 0，有 n = 3n+5 ，所以 g(n) = c h(n)。 这样，根据大O 法的定义有 g(n)=O(h(n) 。但这是同假设相矛盾的。因此， f(n)= O(n) 是一个紧贴渐进界。,关于更严格的“紧贴渐进界”的概念，请看一下的定义。,1、算法和算法分析,时间复杂性分析的注意： 1、时间复杂性函数无时间单位。 2、上例采用的是均匀时间耗费。以简单语句的耗费时间
6、为 1 。 3、如循环语句，条件：O(1) + THEN OR ELSE 后的语句的时间耗费之和。 4、循环语句，先里后外，逐步求和。,4、时间复杂性的级别的判断：级别越低越好。,O(logn) 和 O (n1/2) ？,1、算法和算法分析,例1、 设 T(n) = (n+1)2 = n2+2n2 +1 = n2 ; 在 n 为任何数时，所以，T(n) = (n2),例2、 设 T(n) = 3n3+2n2 T(n) = 3n3。所以，T(n) = (n3) 同理：T(n) = 5n2。所以，T(n) = (n2) ？ 注意：符合定义，但在算法分析中是没有意义的。 :找尽可能高的下界。,1、算
7、法和算法分析,1,。下述两个程序段的作用都是将数组,int a,n,的前,n-1,数组元素置为和其,数组元素的下标相同的值，且最后一个数组元素置为,-1,即,a,n-1,= -1,。,两段程序那个好一些，那个差一些,(,从算法的时间复杂性角度考虑,),A.,for ( i = 0 ; i n-1; + i ) a,i,= i; a,n-1,= -1;,B.,for ( i = 0 ; i n; + i ) if ( i = = n-1 ) a,n-1,= -1;,else a,i,= i; ,解：程序 A 执行的语句次数为 n 次，而程序 B 执行的语句次数为 2 n 次, 故而程序 B 更好
8、一些。时 间省。,2,。以下是计算,n!,的递归程序，求其时间复杂性的级别：,int f ( int n), int m;,if ( n = 1 ) m = 1;,else m = n * f ( n -1);,return m;,1、算法和算法分析,解：根据上述程序的语句执行次数可得： 2 if n=1 T(n) = T(n-1)+2 else 解本递归式可得： T(n)= 2T(n-1)+2= 2(2T(n-2)+2)+2=O(n) 答：本程序的程序时间复杂性的级别是线性级的。,3,、将下列算法的时间复杂性的级别，按由低到高的顺序排成一列；,O(n,4,), O(1), O(n,3,),
9、O( n,n,1/2,), O(,logn), O(,nlogn), O(n,1/2,), O(n,2,), O(2,n,),解：由低到高的顺序为： O(1), O(logn), O(n1/2), O(n*logn), O(n*n1/2), O(n2), O(n3), O(n4), O(2n),1、算法和算法分析,4,、下面的算法为计算,x,的,n,次幂,的值,(y =,xn),，求其时间复杂性的级别，注意,x,和,n,都是正整数：,。,。,scanf(“%d”, ,scanf(“%d”, ,y = x;,while ( n 1 ), y = y * x ; n = n-1 ,printf(“
10、%d” , y );,.,解： 考察各个语句的执行次数，并把他们相加，可得到该程序的时间复杂性级别为： T(n)= 1+1+1+n+2n-2+1=O(n),1,1,1,n,2n-2,1,1、算法和算法分析,1,1,1,1,1,1,Log n + 2,Log n + 1,Log n + 1,Log n + 2,Log n + 1,Log n + 1,Log n + 1,代价 = 3( ),1,1、算法和算法分析,解：将上一页的语句执行相加次数，可得到总的执行次数，故： T(n) = 9 log n + 17 =O(log n) 算法的工作原理，可用求 x55来加以说明： x55= x110111
11、 = x32+16+0+4+2+1来加以说明。 程序的 第一个 while 求出 = 55 的最小的2的正整数幂 64，64/2 可得到32，在程 序的 第二个 while 中用到它。在程 序的 第二个 while 中： 55 - 32 = 23 得到 x110111 中的 幂指数中的最左位的1 23 - 16 = 7 得到 x110111 中的 幂指数中的左起第二位的1 7 - 8 0 得到 x110111 中的 幂指数中的左起第三位的0 7 - 4 = 3 得到 x110111 中的 幂指数中的左起第4位的1 3 - 2 = 1 得到 x110111 中的 幂指数中的左起第5位的1 1 - 1 =0 得到 x110111 中的 幂指数中的左起第 6三位的1 知道了上述求法之后，求 x110111 就很方便了：,1、算法和算法分析,解： 知道了上述求法之后，求 x110111 就很方便了： 先求 x1 ，1 * x =y 再求 x11 ， x11= x10 * x1 = x10 * x1 =y * y * x =y 再求 x110 ， x110= x11 * x11 = y * y 其余，依次类推。,
