思考题-计算机科学与技术学院.PPT

设计方案2的特点： 存储空间：大 算法时间：多 算法简洁性：好 设计方案3：将学生的学号、姓名和班号放在一个表中，将成绩数据放在另一个表中，两者通过学号关联。前者一个学生对应一个记录，后者一门课程成绩对应一条记录。对应的数据结构如下： 　 struct stud1 　　{ 　int no; //学号 　 　char name[10]; //姓名 　int bno; //班号 　　}; 　　struct stud2 　　{ 　int no; //学号 　int cno; //课程编号 　int deg; //分数 　　}; no name bno 1 张斌 9901 8 刘丽 9902 … … … 关联 存储结构3 no cno deg 1 1 78 1 2 82 1 4 92 1 5 85 1 6 83 8 1 65 8 3 72 8 5 80 8 6 79 … … … 设计方案3的特点： 存储空间：少。 算法时间：中。 算法简洁性：好。 最佳方案 综合分析的结果 思考题： 　　学习第1章有什么体会？ 本章小结 本章介绍了数据结构的基本概念，主要学习要点如下： （1）数据结构的定义，数据结构包含的逻辑结构、存储结构和运算三方面的相互关系。 （2）各种逻辑结构即线性结构、树形结构和图形结构之间的差别。 （3）数据结构和数据类型的差别和联系。 （4）算法的定义及其特性。 （5）算法的时间复杂度和空间复杂度分析。 练习题1： p24:习题3、习题5和习题6。 上机题： 　熟悉VC++6.0环境 算法描述的语言不同 算法执行的环境不同 其他因素 所以不能用绝对执行时间进行比较。 　　同一问题可以采用多种算法实现。如何比较算法执行效率？ 为了便于比较同一问题的不同算法，通常从算法中选取一种对于所研究的问题来说是基本运算的原操作（以下将基本运算的原操作简称为基本运算）。 算法执行时间大致为基本运算所需的时间与其运算次数（也称为频度）的乘积。 被视为算法基本运算的一般是最深层循环内的语句。 在一个算法中,进行基本运算的次数越少,其运行时间也就相对地越少；基本运算次数越多,其运行时间也就相对地越多。 所以,通常把算法中包含基本运算次数的多少称为算法的时间复杂度，也就是说，一个算法的时间复杂度是指该算法的基本运算次数。 算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作： 　　　 T(n)=O(f(n)) 记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。“O”的形式定义为： 若f(n)是正整数n的一个函数，则T(n)=O(f(n))表示存在一个正的常数M，使得当n≥n0时都满足： |T(n)|≤M|f(n)| 也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。 例如，T(n)=3n2-5n+10000=O(n2) 本质上讲，是一种最高数量级的比较 一个没有循环的算法的基本运算次数与问题规模n无关，记作O(1)，也称作常数阶。 一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。 其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。 各种不同数量级对应的值存在着如下关系： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!) 思考题： 　　为什么要进行算法的时间复杂度分析？ 例1.4 求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。 #define MAX 20 //定义最大的方阶 void matrixadd(int n,int A[MAX][MAX], int B[MAX][MAX],int C[MAX][MAX]) { int i,j; for (i=0;in;i++) for (j=0;jn;j++) C[i][j]=A[i][j]+B[i][j]; } 该算法中的基本运算是两重循环中最深层的语句C[i][j]=A[i][j]+B[i][j]，分析它的频度，即： 　T(n)= =O(n2) 例1.5 　分析以下算法的时间复杂度。 int fun(int n) { int i,j,k,s; s=0;