1.4算法和算法分析 时间复杂度: 个算法花费的时间与算法中语句的执行次数成正比例,哪 个算法中语句执行次数多,它花费时间就多。一个算法中语 句的执行次数称为语句频度或时间频度,记为T(n) 算法中基本操作重复执行的次数是问题规模n的某个函数,算 法的时间量度记作 T(n=o(f(n)) 随着问题规模的增大,算法执行时间的增长率和f(n)的增 长率相同,称为算法的渐近时间复杂度,简称时间复杂度。 数据结构 ③◎@
22 时间复杂度： 一个算法花费的时间与算法中语句的执行次数成正比例，哪 个算法中语句执行次数多，它花费时间就多。一个算法中语 句的执行次数称为语句频度或时间频度，记为T(n)。 算法中基本操作重复执行的次数是问题规模n的某个函数，算 法的时间量度记作 T（n）=O（f（n）） 随着问题规模的增大，算法执行时间的增长率和f（n）的增 长率相同，称为算法的渐近时间复杂度，简称时间复杂度。 1.4 算法和算法分析
1.4算法和算法分析 ①{++x;s=0;} o(1) ②for(i=1;i<=n;++i) o(n) ++x;s+=x;} ③for(j=1;j=n;++j o(n2) for(k=1; k<=n; ++k) ++x;s+=x;} ④i=1 while(i=n)i=i*2 o (log2n) 算法的时间复杂度由嵌套最深的语句的频度决定的 数据结构 ③◎@
23 ① {++x;s=0;} ② for(i=1;i<=n;++i) {++x;s+=x;} ③ for(j=1;j<=n;++j) for(k=1;k<=n;++k) {++x;s+=x;} O （1） O （n） O （n2） 算法的时间复杂度由嵌套最深的语句的频度决定的 ④ i=1; while(i<=n) i=i*2; O （log2n） 1.4 算法和算法分析
1.4算法和算法分析 常数阶O(1) 对数阶0(ogn) 线性阶0(n) 线性对数阶O( (nlog,n) 平方阶O(m2) 立方阶O(n3) K次方阶O( 指数阶O(2n) 数据结构 ③◎@
24 常数阶 O (1) 对数阶 O (log2n) 线性阶 O (n) 线性对数阶 O (nlog2n) 平方阶 O (n2 ) 立方阶 O (n3 ) … … K次方阶 O (nk ) 指数阶 O (2n ) 1.4 算法和算法分析
第1章总结 教学要求: 1、了解数据结构的相关术语:数据、数据元素、数据对象、 数据类型、数据结构、数据的逻辑结构与物理结构概念 及逻辑结构与物理结构间的关系。 2、了解算法的定义、算法的特性、算法的时间代价、算法 的空间代价。 3、掌握计算语句频度和估算算法时间复杂度的方法。 数据结构 ③◎@
25 教学要求： 1、了解数据结构的相关术语:数据、数据元素、数据对象、 数据类型、数据结构、数据的逻辑结构与物理结构概念 及逻辑结构与物理结构间的关系。 2、了解算法的定义、算法的特性、算法的时间代价、算法 的空间代价。 3、掌握计算语句频度和估算算法时间复杂度的方法。 第1章 总结
作业 1、把矩形定义及其运算设计成一种抽象数据类型,其数据部 分包括矩形的长度和宽度,操作部分包括初始化矩形的尺 寸、求矩形的周长和面积 2、试用图形的形式表示下列二元组表示的数据结构,并指出 它们分别属于何种结构。 (1)A=(KR),其中K={a1a2,a3…an} R=t (2)B=KR),其中K={a,b,c,d,ef,gh} REtry ≤a,b>,b,c>,≤c,d><d,e>,<e,f>,f,g>,<g,h>} (3)c=(K,R,其中K={a,b,c,d,e,f,g,h} R=(<d, b>, <d, g>, <b, a>, <b, c>, <g, e>, <g, h>, <e, (4)D=(KR,其中K={1,2,34,5,6} R={1,2>,<23>,<2,4>,<3,4>,<3,5,3,6,<4,5>,<4,6>} 数据结构 ③◎@
26 1、把矩形定义及其运算设计成一种抽象数据类型，其数据部 分包括矩形的长度和宽度，操作部分包括初始化矩形的尺 寸、求矩形的周长和面积。 2、试用图形的形式表示下列二元组表示的数据结构，并指出 它们分别属于何种结构。 (1) A=(K,R)， 其中K={a1 ,a2 ,a3……an } R={} (2) B=(K,R)，其中K={a,b,c,d,e,f,g,h} R={r} r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>} (3) C=(K,R)，其中K={a,b,c,d,e,f,g,h} R={<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>} (4) D=(K,R)，其中K={1,2,3,4,5,6} R={<1,2>,<2,3>,<2,4>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>} 作业