《数据结构窦延平版的讲义--_时间复杂性dsjw.pptx》由会员分享，可在线阅读，更多相关《数据结构窦延平版的讲义--_时间复杂性dsjw.pptx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 物料管理物料管理INTRO3/25/20231数据结构与程序设计考研复习大纲数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析、算法和算法分析1、算法：一个算法就是有穷规则的集合，其中的规则规定了一个解决某一个特定问题的运算、算法：一个算法就是有穷规则的集合，其中的规则规定了一个解决某一个特定问题的运算 序列。序列。2、算法的时间复杂性和空间复杂性：、算法的时间复杂性和空间复杂性：问题的规模问题的规模(n)：或大小。如：矩阵的阶数、图的结点个数、被分类序列的正整数个数：或大小。如：矩阵的阶数、图的结点个数、被分类序列的正整数个数 时间复杂性：算法的所需的时间和问题规模的函数。记为时
2、间复杂性：算法的所需的时间和问题规模的函数。记为 T(n)。当当 n-时的时间复杂时的时间复杂 性，被称之为性，被称之为渐进时间复杂性渐进时间复杂性。空间复杂性：算法的所需的空间和问题规模的函数。记为空间复杂性：算法的所需的空间和问题规模的函数。记为 T(n)。当。当 n-时的时间复杂时的时间复杂 性，被称之为性，被称之为渐进空间复杂性渐进空间复杂性。最坏情况下的时间复杂性和平均情况下的时间复杂性。最坏情况下的时间复杂性和平均情况下的时间复杂性。最坏情况下的时间复杂性：最坏情况下的时间复杂性：平均情况下的时间复杂性：平均情况下的时间复杂性：3、大、大 O 表示法：表示法：定义；如果存在着正的常
3、数定义；如果存在着正的常数 c 和自然数和自然数 n0，当，当 n=n0 时；有时；有 f(n)=Cg(n)成立，则成立，则 称称 f(n)=O（g(n)。在算法分析中，在算法分析中，如果一个的算法的时间复杂性是如果一个的算法的时间复杂性是O(g(n)，读作，读作 g(n)“级级 ”的的 或或“阶阶”的。的。如：如：线性阶的、平方阶的、立方阶的线性阶的、平方阶的、立方阶的 2 物料管理物料管理INTRO3/25/20232数据结构与程序设计考研复习大纲数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析、算法和算法分析例例1、设设 T(n)=(n+1)2 =n2+2n2+1 1 时，时，
4、式成立式成立 选选 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)=n0，3n+5=0，有有 n=3n+5，所以，所以 g(n)=if Lim f(n)/g(n)=0;这里这里 c 是常数。是常数。f(n)级别低级别低。n-if Lim f(n)/g(n)=;这里这里 c 是常数。是常数。g(n)级别低级别低。n-如：如：Lim logn/n=Lim Ln(n)loge/n =Lim(loge/n)/1 =Lim l
5、oge/n=0;logn 级别低。级别低。注意：这里使用了罗彼特的求极限的法则。注意：这里使用了罗彼特的求极限的法则。n-n-n-n-O(logn)和和 O(n1/2)？5 物料管理物料管理INTRO3/25/20235数据结构与程序设计考研复习大纲数据结构与程序设计考研复习大纲_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
6、 为任何数时，所以，为任何数时，所以，T(n)=(n2)例例2、设设 T(n)=3n3+2n2 T(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)
7、6 物料管理物料管理INTRO3/25/20236数据结构与程序设计考研复习大纲数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析、算法和算法分析1。下述两个程序段的作用都是将数组 int an 的前 n-1 数组元素置为和其 数组元素的下标相同的值，且最后一个数组元素置为-1,即 an-1=-1。两段程序那个好一些，那个差一些 (从算法的时间复杂性角度考虑 )A.for(i =0;i n-1;+i )ai=i;an-1=-1;B.for(i =0;i n;+i )if (i =n-1)a n-1=-1;else ai=i;解：程序解：程序 A 执行的语句次数为执行的语句次数为 n 次
8、，而程序次，而程序 B 执行的语句次数为执行的语句次数为 2 n 次次,故而程序故而程序 B 更好一些。时更好一些。时间省。间省。2。以下是计算 n!的递归程序，求其时间复杂性的级别：int f(int n)int m;if (n 1 )y=y*x;n=n-1 printf(“%d”,y );.解：解：考察各个语句的执行次数，并把他们相加，可得到该程序的时间复杂性级别为：考察各个语句的执行次数，并把他们相加，可得到该程序的时间复杂性级别为：T(n)=1+1+1+n+2n-2+1=O(n)111n2n-219 物料管理物料管理INTRO3/25/20239数据结构与程序设计考研复习大纲数据结构与
9、程序设计考研复习大纲_SJTU1、算法和算法分析、算法和算法分析111111Log n+2Log n+1Log n+1Log n+2Log n+1Log n+1Log n+1代价代价=55 的最小的的最小的2的正整数幂的正整数幂 64，64/2 可得到可得到32，在程，在程 序的序的 第二个第二个 while 中用到它。在程中用到它。在程 序的序的 第二个第二个 while 中：中：55-32=23 得到得到 x110111 中的中的 幂指数中的最左位的幂指数中的最左位的123-16=7 得到得到 x110111 中的中的 幂指数中的左起第二位的幂指数中的左起第二位的17-8 0 得到得到 x
10、110111 中的中的 幂指数中的左起第三位的幂指数中的左起第三位的07-4 =3 得到得到 x110111 中的中的 幂指数中的左起第幂指数中的左起第4位的位的13-2 =1 得到得到 x110111 中的中的 幂指数中的左起第幂指数中的左起第5位的位的11-1 =0 得到得到 x110111 中的中的 幂指数中的左起第幂指数中的左起第 6三位的三位的1 知道了上述求法之后，求知道了上述求法之后，求 x110111 就很方便了：就很方便了：11 物料管理物料管理INTRO3/25/202311数据结构与程序设计考研复习大纲数据结构与程序设计考研复习大纲_SJTU1、算法和算法分析、算法和算法分析解：解：知道了上述求法之后，求知道了上述求法之后，求 x110111 就很方便了：就很方便了：先求先求 x1，1*x =y再求再求 x11，x11=x10 *x1=x10*x1 =y*y*x=y 再求再求 x110，x110=x11 *x11=y*y 其余，依次类推。其余，依次类推。