第1章绪论第2版周.ppt

例1：N×N矩阵相乘 for(i=1;i=n;i++) for(j=1;j=n;j++) {c[i][j]=0; for(k=1;k=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; } 算法中的基本操作语句为c[i][j]=c[i][j]+a[i][k]*b[k][j]; 例2： for( i=1; i=n; i++) for (j=1; j=i; j++) for (k=1; k=j; k++) 　　　　x=x+1; 语句频度 = 定理1.1 若f(n)=amnm+am-1nm-1+?+a1n+a0是m次多项式，则T(n)=O(nm)。 忽略所有低次幂项和最高次幂系数，体现出增长率的含义 例3：分析以下程序段的时间复杂度 i=1; ① while(i=n) i=i*2; ② 即f(n)≤log2n，取最大值f(n)=log2n 所以该程序段的时间复杂度T(n) =O( log2n) 例4：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置。 for (i=0;i n;i++) if (a[i]==e) return i+1; return 0; 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同 最好情况：1次 最坏情况：n 平均时间复杂度为:O(n) 时间复杂度T(n)按数量级递增顺序为： 复杂度高 复杂度低 　当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊 空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n)) 其中n为问题的规模(或大小) 算法要占据的空间 算法本身要占据的空间，输入/输出，指令，常数，变量等 算法要使用的辅助空间 渐进空间复杂度 【算法1】? for(i=0;in/2;i++) { t=a[i]; a[i]=a[n-i-1]; a[n-i-1]=t; }? 【算法2】? for(i=0;in;i++) b[i]=a[n-i-1]; for(i=0;in;i++) a[i]=b[i]; ? 例5：将一维数组a中的n个数逆序存放到原数组中。 S(n) = O(n) S(n) = O(1) 原地工作 若算法执行所需要的辅助空间相对于输入数据量而言是个常熟，则这个算法为原地工作，辅助空间为Ｏ（１） 1、数据、数据元素、数据项、数据结构等基本概念 2、对数据结构的两个层次的理解 逻辑结构 存储结构 3、抽象数据类型的表示方法 4、算法、算法的时间复杂度及其分析的简易方法 小结 * * * * * * * 逻辑结构和存储结构都相同, 但运算不同, 则数据结构不同. 例如, 栈与队列 对于一种数据结构, 常见的运算 插入 删除 修改 查找 排序 数据的运算 数据的逻辑结构 数据的存储结构 数据的运算：插入、删除、修改、查找、排序 线性结构 非线性结构 顺序存储 链式存储 线性表 栈、队列 串、数组 树形结构 图形结构 逻辑结构 唯一 存储结构 不唯一 运算的实现 依赖于 存储结构 定义：在一种程序设计语言中，变量所具有的数据种类　 数据类型 FORTRAN语言：整型、实型、和复数型 C语言： 　基本数据类型： char int float double void 　构造数据类型：数组、结构体、共用体、文件 数据类型是一组性质相同的值的集合, 以及定义于这个集合上的一组运算的总称 抽象数据类型 (ADTs: Abstract Data Types) 更高层次的数据抽象 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的操作 抽象数据类型 抽象数据类型可以用以下的三元组来表示： ADT = （D，S，P） 数据对象 D上的关系集 D上的操作集 ADT抽象数据类型名{ 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作 ：基本操作的定义 } ADT抽象数据类型名 ADT常用定义格式 抽象数据类型 查找　插入　 删除 修改 线性表 接口或用户界面 数据类型的物理实现封装 信息隐蔽和数据封装，使用与实现相分离 1.3 　抽象数据类型的表示与实现 抽象数据