绪论(信管网络)精要.pptVIP

注： 1） O（）为渐近符号。 2） 空间复杂度S(n)按数量级递增顺序也与上表类似。 复杂度高 复杂度低 时间复杂度T(n)按数量级递增顺序为： 1.5.2 时间复杂度和空间复杂度如何表示？ 多项式阶 时间复杂度：基本操作重复执行的次数的阶数 T(n)=o(f(n)) 空间复杂度：s(n)=o(f(n)) 3n+2=O(n) 因为 3n+2?4n for n?2 6*2n+n2=O(2n) 因为6*2n+n2 ?7*2n for n?4 例： 渐进符号（O）的定义：当且仅当存在一个正的常数 C，使得对所有的 n ? n0 ，有 f(n) ? Cg(n)，则： f(n) = O(g(n)) 1.5.3 计算举例 该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。 解： 分析：显然，语句①的频度是1。设语句2的频度是f(n)，则有： 算法的时间复杂度由嵌套最深层语句的频度决定 例1：分析以下程序段的时间复杂度。 　　i=1; ① while(i=n) 　　 i=i*2; ② 2f(n)≤n，则f(n)≤log 2n，取 f(n)=log 2n, 所以该程序段的时间复杂度T(n)=1+f(n)=1+ log 2n = O(log 2n) 例2：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]; } 本章小结 数据结构课程—— 数据结构＋算法＝程序，涉及数学、计算机硬件和软件。 数据结构定义——指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。 数据结构内容——数据的逻辑结构、存储结构和基本运算 数据结构学习工具——抽象数据类型和伪码（类C） 算法效率指标——时间效率和空间效率 第1章结束 作业： ① 配套习题集的相应题目。 ② 复习C语言，重点是结构类型和递归概念。 数 据 结 构 余冬梅 陕西理工学院计算机系 2012年9月 师生沟通渠道： 我的信箱：yudongmei609@ Tel学时数：54（40＋14） 学 分： 3 教 材：严蔚敏等，数据结构（C语言版），清华大学出版社 参考书： [1] 殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社（配题集） [2] 苏光奎等，数据结构导学，清华大学出版社 [3] 薛超英，数据结构（第二版），华中科技大学出版社 [4] 丁宝康等，数据结构自学考试指导，清华大学出版社 内 容 安 排 章 内 容 学时 章 内 容 学时 1 绪 论 2 7 图 8 2 线性表 6 8 动态存储管理 略 3 栈和队列 4 9 查找 6 4 串 1 10 内部排序 4 5 数组和广义表 2 11 外部排序 略 6 树和二叉树 7 12 文件 略 数据结构课程的地位 ——针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。 ——是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 关系 对象 关系 操作 数学 软件 硬件 对象 关系 操作 Data_Structure=（D, R） 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序 目 录 第1章　绪　论 讨论5个问题： 1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量 1.1 什么是数据结构 是相互之间存在一种或多种特定关系的数据元素的集合，表示为： （数值或非数值） Data_Structure=（D, R） ——是指同一数据元素类型中各元素之间存在的关系。 元素有限集 关系有限集 数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。 数据元素(data element)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。 数据项(Data item)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。 三者概念范围之间的