【精品数据结构】算法的基本概念.pptVIP

第二章?数据结构与算法 第二章?数据结构与算法 第二章?数据结构与算法 第二章?数据结构与算法 第二章?数据结构与算法 第二章?数据结构与算法 算法的时间复杂度: 算法中实现基本操作的语句（基本语句）重复执行的次数，称为算法的频度。 记作：T(n)=O(f(n)) 随问题规模n的增大，算法的频度T(n)和f(n)的增长率同阶。 例1： x+=5; 单个语句的频度为1，则 程序段的时间复杂度为T(n)=O(1)。 例 for (i=1; i=n; ++i) /* n+1 */ for (j=1; j=n; ++j) /* n(n+1) */ c [i][j]=0; /* n2 */ -------------------------------------------------------- T(n)=2n2+2n+1 当n充分大时， T(n)与n2是同阶的。 该算法时间复杂度为：T(n)=O(n2) 作业： P72 第1、2、3题 P72 第2题 (a)解 ∵∑i=1+2+3+……+n =(1+n)*n/2 ∴O(∑i)=O(n2) 1≤i≤n 1≤i≤n * 10 65 865 姓名 学号 成绩 班级 李红 9761059 95 机97.6 A B C D E F G 2.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。 2.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。 能输入到计算机中 并能被计算机程序处理的 符号的集合。 整数(1,2)、实数(1.1,1.2) 字符串(Beijing)、 图形、声音。 2.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。 计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、 有按作者编排的、有按分类编排 如何将查询图书的这些信息存入计算机中 既要考虑查询时间短，又要考虑节省空间 2.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。 最简单的办法之一是建立一张表， 每一本书的信息在表中占一行，如 2.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。 如何将0,1,2,3,4,5,6,7,8,9这10个数存放在 计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同。 从大到小排列：9,8,7,6,5,4,3,2,1,0 输出偶数：0,2,4,6,8,1,3,5,7,9 数据元素在 计算机中的表示 2.1 概述 数据结构是一门研究数据组织、存储和运算的一般方法的学科。 对数据结构中的节点进行 操作处理 (插入、删除、修改、查找、排序) 数据元素(Data Element) 数据元素是数据的基本单位，即数据集合中的个体。 有时一个数据元数可由若干数据项(Data Item)组成。数据项是数据的最小单位。 数据元素亦称节点或记录。 名词解释 数据结构可描述为 Group=（D，R） 有限个数据元素的集合 有限个节点间关系的集合 1．数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A．线性结构 B．非线性结构 A 顺序存储 B 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个主要问题 数据结构可描述为 Group=（D，R） 1．数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A．线性结构 B．非线性结构 A 顺序存储 B 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个主要问题 数据结构可描述为 Group=（D，R） 我和你们的逻辑结构是师生结构 我和你们在教室中的位置根据要求而不同 1．数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A．线性结构 B．非线性结构 A 顺序存储 B 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个主要问题 数据结构可描述为 Group=（D，R） 线性结构