幻灯片1-中国传媒大学计算机学院课程.pptVIP

小结 数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于数据的逻辑结构，而算法的实现依赖于采用的存储结构 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 在某种意义上，数据结构可以看成是“一组具有相同结构的值”，则数据结构类型可以看成由一种数据结构和定义在其上的一组操作组成 * 小结 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作 抽象数据类型和数据类型实质上是一个概念，尽管二者在不同处理器上实现的方法可以不同，但其定义的数学特性相同；“抽象”的意义在于数据类型的数学抽象特性 抽象数据类型可以用三元组（D, S, P）表示，其中D是数据对象，S是D上的关系集，P是对D的基本操作集 * 小结 算法是对特定问题求解步骤的一种描述，其重要特性包括：有穷性、确定性、可行性、有输入和输出 评价一个“好”的算法的标准包括：正确性、可读性、健壮性、效率和低存储空间需求 算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度简称时间复杂度，记作 T(n) = O(f(n)) 表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同 * * * * * * * * * * * * * * * * * * * * * * * * 开始 为n个元素a1~an输入数值 a1→x 2→i i≤n aix ai→x i+1→i N Y Y 输出x 结束 采用文字描述,则如下步骤所示： 给n个元素a1~an输入数值； 把第一个元素a1赋给用于保存最大值元素的变量x； 把表示下标的变量i赋初值2； 如果i≤n则向下执行，否则输出最大值x后结束算法； 如果aix则将ai赋给x； 将下标i增1，以指示下一个元素； 转向第④步继续执行。 N 求n个元素中的最大值 算法描述 * 算 法 C 语 言 描 述 /* 程序1-1.c*/#includestudio.h#define N 8 /* 定义N为整数8 */void main(void) { int i, x, a[N]; /* 用a[0]~a[N-1]保存a1~an元素 */ printf(“请输入%d个整数：”, N); for (i=0; i N; i ++) scanf(“%d”, a[i]); x=a[0]; /* 把第一个元素a[0]的值赋给x */ i=1; /* 把第二个元素a[1]的下标1赋给i */  while (iN) { /* 循环比较得到最大值 */ if (a[i] x) x=a[i]; i ++; } printf(“%d个整数中的最大值为：%d\n”, N, x); } * 评价一个好的算法有以下几个标准: (1) 正确性(correctness) 算法应满足具体问题的需求。 (2) 可读性(readability) 算法应该好读,以有利于阅读者对程序的理解。 (3) 健壮性(robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 (4) 效率与低存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。 * 算法执行时间是通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。 事后统计方法，使用计算机内部计时功能，其缺陷是必须先运行程序，而且所得时间的统计量依赖于计算机的环境因素。 事先分析估算方法，比较同一问题的不同算法，通常的做法是以算法中基本操作重复执行的次数作为算法的时间度量。 算法效率的度量 * 一般情况下，算法中基本操作(如赋值、比较、计算、转向、返回、输入、输出等）重复执行的次数是问题规模 n 的某个函数，算法的时间量度记作 T (n)=O (f (n)) 称作算法的渐近时间复杂度,简称时间复杂度。 时间复杂度 * 一个算法是由控制结构（顺序、分支和循环）和原操作（固有数据类型的操作）构成，则算法时间取决与二者综合效果。 通常的做法是从算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。 多数情况下,被称做问题的基本操作的原操作是最深层循环内的语句中的原操作,其执行次数和包含它的语句的频度（语句重复执行次数）相同。 时间复杂度 * 例如在以下矩阵相乘的算法中，“