简介与算法时间复杂性.ppt

数据结构 刘士军 L 山东大学计算机学院 1 学习本课的目的？ 用数字计算机解决任何应用问题都离 不开数据表示和数据处理。而数据表 示和数据处理的核心问题之一就是数 据结构及其操作的实现。 算法设计提供了使用计算机解决问题 的基本思维方式。 算法分析是关于算法评价的科学方法 。 2 讲述内容 数据结构与算法分析概论 1 1 线性结构11 栈和队列11 数组和广义表1 树结构2 2 图结构2 3 搜索24 排序25 3 第一章 绪论 4 1.1数据结构讨论的范畴 Niklaus Wirth Algorithm + Data Structures = Programs 程序设计: 为计算机处理问题编制一组指 令集 算法:处理问题的策略 数据结构:问题的数学模型 例如: 数值计算的程序设计问题 结构静力分析计算 线性代数方程组 全球天气预报 环流模式方程 非数值计算的程序设计问题 5 例1 书目自动检索系统 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片 书目文件 按书名 按作者名 按分类号 索引表 线性表 6 例2 人机对奕问 题 树 . 7 例3多叉路口交通灯管理 问题 C E D A B ABACAD BABCBD DADBDC EAEBECED 图 8 数据结构定义: 是一门 研究非数值计算的程序设计 问题中计算机的操作对象以 及它们之间的关系和操作等 等的学科 9 数据所有能被输入到计算机中，且被计算机处理 的符号的集合 是计算机操作的对象的总称 是计算机处理的信息的某种特定的符号表示形式 数据元素数据的基本单位，也称节点或记录 数据项有独立含义的数据最小单位 数据结构数据元素和数据元素关系的集合 根据数据元素间关系的基本特性，有四种基本数据 结构 集合数据元素间除“同属于一个集合”外，无其它关 系 线性结构一个对一个，如线性表、栈、队列 树形结构一个对多个，如树 图状结构多个对多个，如图 1.2基本概念和术语 10 数据的逻辑结构只抽象反映数据元素的 逻辑关系 数据的存储（物理）结构数据的逻辑结 构在计算机存储器中的实现 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 存储结构分为： 顺序存储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系 1.2基本概念和术语 11 元素n 元素i 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储 1.2基本概念和术语 12 1536元素21400元素11346元素3 元素4 1345 h 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 . . 1400 元素2 1536 . . 1536 元素3 1346 链式存储 h 1.2基本概念和术语 13 数据类型高级语言中指数据的取值范围 及其上可进行的操作的总称 例 C语言中，提供int, char, float, double等基本数据类型，数组、结构体、 共用体、枚举等构造数据类型，还有指针 、空(void)类型等。用户也可用typedef 自己定义数据类型 typedef struct int num; char name20; float score; STUDENT; STUDENT stu1,stu2, *p; 1.2基本概念和术语 14 抽象数据类型 是指一个数学模型以及定义在此数学模型上的一 组操作 例如： 矩阵 +（求转置、加、乘、求逆、求特征值 ） 构成一个矩阵的抽象数据类型 数据结构+定义在此数据结构上的一组操作 = 抽 象数据类型 抽象数据类型的描述方法 抽象数据类型可用（D，S，P）三元组表示，其 中，D是数据对象，S是D上的关系集，P是对D的 基本操作集。 ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 15 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队 树形结构 图形结构 数据结构研究的三个方面 16 算法（algorithm）解决某一特定问 题的具体步骤的描述，是指令的有限序 列 算法特性 1.3 算法的描述和 算法分析简介 17 算法的五个特性 1有穷性 对于任意一组合法输入值，在执行有 穷步骤之后一定能结束，即：算法中的每个步骤 都能在有限时间内完成； 2确定性 对于每种情况下所应执行的操作，在 算法中都有确切的规定，使算法的执行者或阅读 者都能明确其含义及如何执行。并且在任何条件 下，算法都只有一条执行路径； 3可行性 算法中的所有操作都必须足够基本， 都可以通过已经实现的基本操作运算有限次实现 之 4有输入 作为算法加工对象的量值，通常体现 为算法中的一组变量。有些输入量需要在算法执 行过程中输入，而有的算法表面上可以没有输入 ，实际上已被嵌入算法之中； 5有输出 它是一组与“输入”与确定关系的量值 ，是算法进行信息加工后得到的结果，这种确定 关系即为算法的功能。 18 问题的定义 问题（problem）： 需要回答的一般性提问 通常含有若干参数 问题的描述： 对问题参数的一般性描述(input) 解满足的条件(objective) 问题的实例（instance）: 给问题的参数一组赋值后得到的问题的 特例 问题的定义 19 实例(instance): C = c1, c2, c3, c4, d (c1,c2) = 10, d (c1,c3) = 5, d (c1,c4) = 9 d (c2,c3) = 6, d (c2,c4) = 9, d (c3,c4) = 3 例1 旅行售货员问题 input：有穷个城市的集合C = c1, c2, , cm, 以 及城市之间的距离 正整数d (ci, cj) = d (cj, ci), 1 i 0,使得 对任意的n=n0， 有f(n)+f(n)/g(n)存在， 则这个极限 不等于就意味着f(n)=O(g(n)。 f(n)=O(g(n)说明c.g(n)是 f(n)的一个上 界。 例子：f(n)=5n3+7n2-2n+13, 则可以记做 f(n)=O(n3). 3n 不等于O(2n), 因为lim(3/2)n= . 如果一个算法A的时间复杂性是 f(n)=O(g(n), 则称算法A的时间复杂性是 O(g(n)。 37 的定义 定义：令f(n)与g(n) 是定义在自然数域上 的非副实函数，那么称f(n)=(g(n)如果 存在一个自然数n0 和一个常数c0,使得对 任意的n=n0， 有f(n)=cg(n). 若极限limn-+f(n)/g(n)存在， 则这个 极限不等于0就意味着f(n)= (g(n)。 f(n)= (g(n)说明c.g(n)是 f(n)的一个下 界 例子：f(n)=5n3+7n2-2n+13, 则可以记 做f(n)= (n3). 如果一个算法A的时间复杂性是f(n)= (g(n), 则称它的时间复杂性是(g(n)。 f(n)=O(g(n) g(n)=(f(n) 38 时间复杂性的例子 例子：设一个算法的时间复杂性是： 则有，T(n)=O(n2)，T(n)= (n), 但是 我们不知道T(n)的确切的阶。 39 时间复杂性的性质 设T1(n)=O(f(n),T2(n)=O(g(n), T1(n)+T2(n)=O(maxf(n),g(n)(两个过程 顺序进行) 证明：T1(n)=O(f(n)存在n1, c1,使得 当 n=n1时, T1(n)=n2时, T2(n)=n0时, T1(n)+T2(n)L2j) Lx=L2j; j+; x+; else Lx=L1i; i+; x+; end if end while if (i=T(k), Then, 对k=n/2, 有T(n/2)=C2+b. Let b=C1,a=C2+C1, then, we conclude by induction that for all n=1, T(n)=2 /n is power of b Expand 49 一类递推方程的一般解法 Since n=bk, k=logbn, ak=alogbn=nlogba. 第一项ak=alogbn=nlogba 称作齐次解，称 d(n)为驱动函数。若d(n)=0, 则齐次解成 为精确解。齐次解描述了所有子问题用的 时间。 第二项 称为特解，他描述产 生子问题以及合并子问题的解为原问题的 解所用时间。一般不好解特解。 50 d(n)为乘函数的讨论 乘函数f(xy)=f(x)f(y), e.g., f(n)=na, then f(xy)=(xy)a=xaya=f(x)f(y). 若 d(n)为乘函数， 则上述问题的特解为 ： 51 若ad(b)，则特解为O(ak), 从而整个问题的解等于 O(ak)=O(nlogba). 减小a,增大b可以改善运行效率。 若a4=a, 故特解是O(n3) ， 所以T(n)= O(n3). 53 例子： T(1)=1 T(n)=3T(n/2)+2n1.5 驱动函数不是乘函数。令U(n)=1/2*T(n), 则， U(1)=1 U(n)=3U(n/2)+n1.5 特解 1/2*alogn=O(nloga)=O(n1.59)