2014/4/7 课程简介 ●先修课程及条件 数据结构 程序设计的经验、C、离散数学、概率分析 ■教材：数据结构，黄刘生，经济科学出版社 计算机学院 数据结构(C语言版)，严蔚敏，清华大学出版社 肖明军 ■考核：考试+作业+上机 Email:xiaomj@ustc.edu.cn ■参考书 http://staff.ustc.edu.cn/~xiaomj C++数据结构，William Ford清华影印版 数据结构和程序设计，Robert,,Kruse.2nd版 sCh.1绪论 ·量要性 ◆人类社会已步入信惠杜会 ◆计算机不再仅仅局限于科学计算，已深入到社会生活 的各个领城 “给我一根杠杆，我就能捕动地球” 2045 “给我一个接口，我就能驱动地球” sCh.1绪论 sCh.1绪论 重要性 编写解决实际问题的程序的一般过程： 计算机：硬件+软件 ◆如何用数据形式描述问题？一即由问题抽象出一 个适当的数学模型： 算法+数据结构一程序设计(NwM山84年围奥奖得主) 。两个问题：信惠的表示和处理 ·问题所涉及的数据量大小及数据之间的关系： 信息的表示和组织又直接关系到处理信息的程 ·如何在计算机中存储数据及体现数据之间的关系？ 序的效率。随着应用问题的不断复杂，导致信息量 处理问题时需要对数据作何种运算？ 剧增与信息范图的拓宽，使许多系统程序和应用程 序的规模很大，结构又相当复杂。因此，必须分析 ◆】 所编写的程序的性能是否良好？ 待处理问题中的对象的特征及各对象之间存在的关 上面所列举的问题基本上由数据结构这门课程来回答。 系，这就是数据结构这门课所要研究的问题
2014/4/7 1 数据结构 1 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj 课程简介 先修课程及条件 程序设计的经验、C、离散数学、概率分析 教材：数据结构，黄刘生，经济科学出版社 数据结构(C语言版) 严蔚敏 清华大学出版社 2 数据结构(C语言版)，严蔚敏，清华大学出版社 考核：考试+作业+上机 参考书 C++ 数据结构，William Ford 清华影印版 数据结构和程序设计， Robert,Kruse.2nd版 §Ch.1 绪论 重要性 人类社会已步入信息社会 计算机不再仅仅局限于科学计算，已深入到社会生活 的各个领域 3 “给我一根杠杆，我就能撬动地球” “给我一个接口，我就能驱动地球” 4 § Ch.1 绪论 重要性 计算机：硬件+软件 算法+数据结构=程序设计（N.Wirth,84年图灵奖得主） 两个问题 信息的表示和处理 5 两个问题：信息的表示和处理 信息的表示和组织又直接关系到处理信息的程 序的效率。随着应用问题的不断复杂，导致信息量 剧增与信息范围的拓宽，使许多系统程序和应用程 序的规模很大，结构又相当复杂。因此，必须分析 待处理问题中的对象的特征及各对象之间存在的关 系，这就是数据结构这门课所要研究的问题。 编写解决实际问题的程序的一般过程： 如何用数据形式描述问题?—即由问题抽象出一 个适当的数学模型; 问题所涉及的数据量大小及数据之间的关系; § Ch.1 绪论 6 问题所涉及的数据量大小及数据之间的关系; 如何在计算机中存储数据及体现数据之间的关系? 处理问题时需要对数据作何种运算? 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答
2014/4/7 例1：电话号码查询系统 例2：磁盘目录文件系统 设有一个电话号码幕，它记录了N个人的名字和其 磁盘根目录下有很多子目录 相应的电话号码，假定按如下形式安排：(a1,b), 及文件，每个子目录里又可以包 (,b2),.(an,bnJ,其中a,b1(i=1,2.n）分别 含多个子目录及文件，但每个子 表示某人的名字和电话号码。本问题是一种典型的 目录只有一个父目录，依此类推： 表格问题。如表所示，数据与数据成简单的一对一的 本问题是一种典型的树型结 线性关系。 构问题，如图所示，数据与数据 姓名 电话号码 成一对多的关系，是一种典型的 陈海 13612345588 非线性关系结构一树形结构。 李四锋 13056112345 线性表结构 例3：交通网络图 S1.1基本概念和术语 从一个地方到另外一个地方可以有多条路径。本 ■数据：信息载体 问题是一种典型的网状结构问题，数据与数据成多对多 的关系，是一种非线性关系结构。 客观事物的符号表示，能由计算机程序识别、 存储和加工处理的符号集合 州 韩山 所有能够数字化的信息均可认为是数据 州 东 ■数据元素：数据的基本单位，在程序中通常作 山 为一个整体来进行考虑和处理 同义词：元素、结点、顶点、记录、对像、元组等 ■数据项：具有独立含义的最小标识单位，客观 周状抽构 事物某一方面特性的数据描述 同义词：字段、域、属性等 S1.1基本概念和术语 S1.1基本概念和术语 ■数据结构举例 系别 晚名 移 SCI 经量 数据结构：相互之间存在一种或多种特定关系 童明 触漫 5 的数据元素的集合，即数据的组织形式 王华业夏 B 数据的逻辑结构：数据元素之间的逻辑关系 23 李立般设情 6 60 ◆数据的存储结构：数据元素及其关系在计算机存储 器内的表示 行：结点（对象、记录、元组等： 数据的运算：对数据施加的操作 列：数据项（具性、罐、字段等） ◆逻辑结构：开始结点？终端结点？内部结点？ 推关 ◆存储结构：用数组实现，还是用指针实现？ ◆运算：创建、插入、除、查找等 2
2014/4/7 2 例1：电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其 相应的电话号码，假定按如下形式安排：(a1, b1)， (a2, b2)，…(an, bn)，其中ai, bi(i=1，2…n) 分别 表示某人的名字和电话号码。 本问题是一种典型的 表格问题。如表所示，数据与数据成简单的一对一的 7 姓名 电话号码 陈海 13612345588 李四锋 13056112345 。。。 。。。 线性关系。 线性表结构 例2：磁盘目录文件系统 磁盘根目录下有很多子目录 及文件，每个子目录里又可以包 含多个子目录及文件，但每个子 目录只有一个父目录，依此类推： 本问题是一种典型的树型结 8 本问题是 种典型的树型结 构问题，如图所示，数据与数据 成一对多的关系，是一种典型的 非线性关系结构—树形结构。 树形结构 例3：交通网络图 从一个地方到另外一个地方可以有多条路径。本 问题是一种典型的网状结构问题，数据与数据成多对多 的关系，是一种非线性关系结构。 佛山 广州 9 惠州 中山 东莞 深圳 珠海 网状结构 §1.1 基本概念和术语 数据：信息载体 客观事物的符号表示，能由计算机程序识别、 存储和加工处理的符号集合 所有能够数字化的信息均可认为是数据 10 数据元素：数据的基本单位，在程序中通常作 为一个整体来进行考虑和处理 同义词：元素、结点、顶点、记录、对象、元组等 数据项：具有独立含义的最小标识单位，客观 事物某一方面特性的数据描述 同义词：字段、域、属性等 §1.1 基本概念和术语 数据结构：相互之间存在一种或多种特定关系 的数据元素的集合，即数据的组织形式 数据的逻辑结构：数据元素之间的逻辑关系 数据的存储结构：数据元素及其关系在计算机存储 11 器内的表示 数据的运算：对数据施加的操作 §1.1 基本概念和术语 数据结构举例 系别 姓名 职称 SCI EI 经费 1 张明 教授 5 1 20 1 王华 教授 6 3 15 … 23 李立 教授 1 6 60 12 行：结点(对象、记录、元组等)； 列：数据项(属性、域、字段等) 逻辑结构：开始结点？终端结点？内部结点？ 结点之间的逻辑关系：有且仅有1个开始结点和1个终端结 点，表中任1结点最多只有1个直接前驱和1个直接后继----- 线性关系 存储结构：用数组实现，还是用指针实现？ 运算：创建、插入、删除、查找等
20144/7 S1.1基本概念和术语 S1.1基本概念和术语 ■逻辑结构 ■存储结构 线性结构：任一结点最多只有1个直接前驱和1个直接后继 (2)链接存俄方法 ◆非袋性结构：一结点可有多个直接前坚和多个直接后罐 ◆集合结构：元素间无关系，只有元素是否属于集合的关系 该方法不要求逻辑上相邻的结点在物理位置上亦相邻 借助于指针来表示结点闻的逻辑关系 (③)家引存储方法 ·存储结构◆一 在存储结点信息的同时，建立附加的索引表。 ()顺序存储方法 表中每项称为索引项（关键字，地址） 逻辑上相邻的结点存储在物理位置上相邻的存储单元里 测密素引：每个结点对应1个索引项 结点问的逻辑关系由存储单元的邻接关系来体现 希疏索引：一组结点对应1个索引项 借助于数组描述 (④)散列存俄方法 应用于线性的败据结构，非袋性的败据结构的线性化 根据结点的K©y直接计算出该结点的存储地址。 s1.1基本概念和术语 S1.1基本橛念和术语 ■数据结构的主要运算 ■数据结构3方面之联系 (i)建立(Create)一个数据结构； ·同一逻辑结构的不同存储结构，则用不同名称称调 (2)消除Destroy).一个数据结构； 例如， (3)从一个数据结构中副除(Del©t©)一个数据元素； 线性表中顺序表，链表，散列表 (4)把一个数据元素插入(Insert)到一个数据结构中： ◆运算不同，称训也不同 (5)对一个数据结构进行访问(Acoe8s); 线性表→栈、队列户顺序栈、顺序队列 (6)对一个数据结构（中的数据元素）进行修改 (Modify); ◆数据的逻辑结构和物理结构是密不可分的两个方面 一个算法的设计取决于所选定的逻辑结构，而算法 (7)对一个数据结构进行排序(Sort)； 的实现依赖于所采用的存储结构。 (8)对一个数据结构进行查找(Search)。 ◆在C语言中，用一维数组表示顺序存储结构；用结 构体类型表示链式存储结构。 逻辑结构 物理结构 S1.1基本概念和术语 线性表 :顺序存储结构 ■数据类型：是一个值的集合以及定义在这些值 树 链式存储结构 上的一组操作的总称，可看作是高级语言提供 的数据结构 复合存储结构 原子类型：值不可分，一般是基本的预定义类型 望辑纳构与所采用的存铺地构 int,char等，定义了“+”，“.等 败物的理填纳构 结构类型：可供用户定义的新类型，构造类型、导 要独兰纳构 出类型、派生类型等 受限线性表} 性表广爆司 树形结构 图状袖构 由基本类型组织而成，如数组、structs等 础性表楼和队列中食恒广义表款闲三又钢有向图无向面 败塘逗辑结构层次关系田 3
2014/4/7 3 §1.1 基本概念和术语 逻辑结构 线性结构：任一结点最多只有1个直接前驱和1个直接后继 非线性结构：一结点可有多个直接前驱和多个直接后继 集合结构：元素间无关系，只有元素是否属于集合的关系 13 存储结构 (1)顺序存储方法 逻辑上相邻的结点存储在物理位置上相邻的存储单元里 结点间的逻辑关系由存储单元的邻接关系来体现 借助于数组描述 应用于线性的数据结构，非线性的数据结构的线性化 §1.1 基本概念和术语 存储结构 (2)链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻 借助于指针来表示结点间的逻辑关系 (3)索引存储方法 14 在存储结点信息的同时，建立附加的索引表。 表中每项称为索引项 (关键字，地址) 稠密索引：每个结点对应1个索引项 稀疏索引：一组结点对应1个索引项 (4)散列存储方法 根据结点的Key直接计算出该结点的存储地址。 数据结构的主要运算 ⑴ 建立(Create)一个数据结构； ⑵ 消除(Destroy)一个数据结构； ⑶ 从一个数据结构中删除(Delete)一个数据元素； ⑷ 把一个数据元素插入(Insert)到一个数据结构中； §1.1 基本概念和术语 15 ⑸ 对一个数据结构进行访问(Access)； ⑹ 对一个数据结构(中的数据元素)进行修改 (Modify)； ⑺ 对一个数据结构进行排序(Sort)； ⑻ 对一个数据结构进行查找(Search)。 §1.1 基本概念和术语 数据结构3方面之联系 同一逻辑结构的不同存储结构，则用不同名称称谓 例如， 线性表顺序表，链表，散列表 运算不同 称谓也不同 16 ， 线性表栈、队列 顺序栈、顺序队列 数据的逻辑结构和物理结构是密不可分的两个方面， 一个算法的设计取决于所选定的逻辑结构，而算法 的实现依赖于所采用的存储结构。 在C语言中，用一维数组表示顺序存储结构；用结 构体类型表示链式存储结构。 逻辑结构与所采用的存储结构 线性表 树 图 顺序存储结构 链式存储结构 复合存储结构 逻辑结构 物理结构 17 数据的逻辑结构 非线性结构 集合 图状结构 有向图 无向图 树形结构 一般树 二叉树 线性结构 一般线性表 线性表推广 串 数组 广义表 受限线性表 栈和队列 数据逻辑结构层次关系图 §1.1 基本概念和术语 数据类型：是一个值的集合以及定义在这些值 上的一组操作的总称，可看作是高级语言提供 的数据结构 原子类型：值不可分，一般是基本的预定义类型 int，char等，定义了“+”，“-”等 18 int，char等，定义了 ， 等 结构类型：可供用户定义的新类型，构造类型、导 出类型、派生类型等 由基本类型组织而成，如数组、struct等
20144/7 S1:1基本概念和术语 61.1基本概念和术语 ■抽象数据类型(Abstract Data Type) ■抽象数据类型(Abstract Data Type) 抽象的数据组织和与之相关的燥作，可看作是数据的逻辑 ADTADT Namef 结构及其在逻辑结构上定义的抽象操作 Data:数据结构（数据对和数据关系）说明 特点 Operations: Constructor:构造函数，创建对象实例 ①封装与德藏：将数据和操作封装在一起，内部结构和 Operation1:用C++或C函数原型描述 实现细节对外屏蔽，实现信息隐藏 input: ②抽象：用户只能通过DT里定义的接口和说明来访问和 Preconditions:M初始条件，执行本操作前系统 操作数据。他反映了程序设计的两层抽象： 需满足的状态 ◆绿念层（抽）-ADT、类说明 process:对数据执行的操作 。实现层类实现，相当于普通类型 output:对返回数据的说明 一应用层一如main0K.),通过操作对象解决实际 Postconditions:执行本操作后系统的状态 问题 Operation2: S1.1基本概念和术语 §1.1基本概念和术语 例：抽象数据类型复数的定义 ADT Complex ■抽象数据类型的表示与实现 意时海 1e.e少是的实分2是复的数分 通过程序设计语言中的类型来实现 本作： omple&Zvl.2） ◆C 排作站果：构迪复章Z其实海取应物分敏腻似常y1和2的直。 DestroyComplex&Z☑ >抽象数据类型 输作谢果：复取放州眼， GetReak(Z &realPart) 数据对象 结构体 初抛条件：复康已存在， 基本操作 作轴果：用eP国直数Z的实善值 函数 件，复已有 ◆Ct+,Java >抽象数据类型 类class 数据对搬 数据成员 操作的果：用am域回两个复章、2的和值， >基本操作 成员函数（方法） 】ADT Complex ADT复数的C描述 ADT复数的C++描述 typedef struct class Complex(∥类的声明 double imagpart: protected: Complex: double realpart; boolean assign(Complex *pSre,Complex *pDes) double magpart; if(pSre-NULL pDes--NULL retur ERROR public: pDes>realpart-pSro>realpart: Complex(方 pDes->imagpart-pSre->imagpart Complex(double realval,double imagVal) return TRUE: Complex(Complex&z){assign(z);} -Complex(片： Complex *add(Complex *pZ1,Complex "pZ2){ void assign(Complex&z); Complex "pSum -(Complex ")malloc(sizeofComplex)): if pSum -NULL )return NULL: double getReal(void)const return realpart;) pSum>realpart-pZI>realpart +pz2>realpart: double getlmag(void)const return imagpart;) pSum->imagpart-pZI-imagpart+pZ2->imagpart: friend Complex add(Complex&z1,Complex&z2); return pSum; 4
2014/4/7 4 §1.1 基本概念和术语 抽象数据类型（Abstract Data Type） 抽象的数据组织和与之相关的操作，可看作是数据的逻辑 结构及其在逻辑结构上定义的抽象操作 特点 ①封装与隐藏：将数据和操作封装在一起，内部结构和 实现细节对外屏蔽 实现信息隐藏 19 ， ②抽象：用户只能通过ADT里定义的接口和说明来访问和 操作数据。他反映了程序设计的两层抽象： 概念层（抽象）---ADT、类说明 实现层---类实现，相当于普通类型 应用层----如main(){…}，通过操作对象解决实际 问题 §1.1 基本概念和术语 抽象数据类型（Abstract Data Type） ADT ADT_Name{ Data: 数据结构(数据对象和数据关系)说明 Operations： Constructor：//构造函数，创建对象实例 Operation1：//用C++或C函数原型描述 20 input： Preconditions：//初始条件，执行本操作前系统 //需满足的状态 process：//对数据执行的操作 output：//对返回数据的说明 Postconditions：//执行本操作后系统的状态 Operation2： } 例：抽象数据类型复数的定义 ADT Complex { 数据对象：D＝{e1,e2｜e1,e2∈RealSet } 数据关系：R1＝{ | e1是复数的实数部分,e2 是复数的虚数部分} 基本操作： InitComplex( &Z, v1, v2 ) 操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex( &Z) 操作结果 复数Z被销毁 §1.1 基本概念和术语 21 操作结果：复数Z被销毁。 GetReal( Z, &realPart) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 GetImag( Z, &ImagPart) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1、z2的和值。 } ADT Complex 抽象数据类型的表示与实现 通过程序设计语言中的类型来实现 C 抽象数据类型 数据对象 结构体 §1.1 基本概念和术语 22 数据对象 结构体 基本操作 函数 C++，Java 抽象数据类型 类class 数据对象 数据成员 基本操作 成员函数(方法) ADT复数的C描述 typedef struct { double realpart; double imagpart; }Complex; boolean assign(Complex *pSrc, Complex *pDes){ if (pSrc ==NULL || pDes==NULL ) return ERROR; pDes->realpart = pSrc->realpart; pDes >imagpart = pSrc >imagpart; 23 ->imagpart = pSrc->imagpart; return TRUE; } Complex *add(Complex *pZ1, Complex *pZ2){ Complex *pSum = (Complex *)malloc(sizeof(Complex)); if ( pSum==NULL )return NULL; pSum->realpart = pZ1->realpart + pZ2->realpart; pSum->imagpart = pZ1->imagpart + pZ2->imagpart; return pSum; } ADT复数的C++描述 class Complex{ // 类的声明 protected: double realpart; double magpart; public: Complex( ); 24 Complex(double realVal，double imagVal); Complex(Complex& z){ assign(z) ;} ~Complex( ); void assign(Complex& z); double getReal(void) const { return realpart;} double getImag(void) const { return imagpart;} friend Complex add(Complex& z1, Complex& z2); }；
2014/4/7 812算法描迷分析 /类的实现部分 Complex::Complex(double realVal,double imagVal){ ◆ 算法 realpart=realVal; ◆重要性：数据的运算是通过算法描述的 imagpart=imagVal; 定义：非形式地说，算法是任意一个良定义的计 void Complex::assign(Complex&z)( 算过程，它以一个或多个值作为输入，并产生 realpart =z.realpart; 个或多个值作为输出。因此，一个算法就是一系 imagpart=z.imagpart; 列将输入转换为输出的计算步骤。 Complex add(Complex&z1,Complex&z2)( ”5要素 Complex sum(z1片 粮入、输出、有穷性（有穷步骤，每步时间有限） sum.realpart +=z2.realpart; 、捧哥凝老卖的柔限次所有 执行路径) sum.imagpart+=z2.imagpart: return sum; ◆ 算法与程序的联系与区别 S1.2算法描迷分析 S1.2算法描述分析 输入实例 ■算法分析 一个问题的输入实例是由满足问题陈述中的限制、 并能计算出该问题解的所有输入构成的。 算法效率的度量 。事后统计：利用计算机内部的计时功能 算法描述 缺陷 自然语言、数学语言、伪语言、程序语言等均可 ,必须先运行依据算法编制的程序 本课程以C为主，但不拘泥于细节 时间统计量依赖于计算机的软硬件环境 double start,stop; 算法评价 time (&start); 正确性、可读性、健壮性、 时空性能 main process(n,…月 time(&stop): double runTime stop-start; printf ("%d%dIn",n,runTime ) s1.2算法描迷与分折 81.2算法描述分析 ◆ 算法分析 算法的时间是每语句执行时间的总和 。事前分析估算（时间） 每语句的执行时间=该语句执行次数（频度） 求出该算法的一个时间界限函数 一些影响因素： X该语句执行1次的时间 算法的策略 假定：每语句执行1次的时间为1个时间单位 问题的规模 则：算法的执行时间=Σ各语句频度 书写程序的语言 问题的规模(Size)n 编译器产生的机器代码的质量 机器执行指令的速度 输入量的大小，如 时间复杂度：算法的运行时间，是问题规模的函数
2014/4/7 5 // 类的实现部分 Complex::Complex(double realVal, double imagVal){ realpart = realVal; imagpart= imagVal; } void Complex::assign(Complex& z){ realpart = z.realpart; imagpart= z imagpart; 25 imagpart= z.imagpart; } Complex add(Complex& z1, Complex& z2){ Complex sum(z1); sum.realpart += z2.realpart； sum.imagpart += z2.imagpart； return sum; } §1.2 算法描述 分析 算法 重要性：数据的运算是通过算法描述的 定义：非形式地说，算法是任意一个良定义的计 算过程，它以一个或多个值作为输入，并产生一 个或多个值作为输出。因此，一个算法就是一系 列将输入转换为输出的计算步骤 26 。 5要素 输入、输出、有穷性（有穷步骤，每步时间有限） 确定性（算法只有唯一执行路径）、可行性（所有 操作可通过已经实现的基本运算有限次实现之） 算法与程序的联系与区别 §1.2 算法描述 分析 输入实例 一个问题的输入实例是由满足问题陈述中的限制、 并能计算出该问题解的所有输入构成的。 算法描述 自然语言、数学语言、伪语言、程序语言等均可 27 自然语言、数学语言、伪语言、程序语言等均可 本课程以C为主，但不拘泥于细节 算法评价 正确性、可读性、健壮性、 时空性能 算法分析 算法效率的度量 事后统计：利用计算机内部的计时功能 缺陷 必须先运行依据算法编制的程序 §1.2 算法描述 分析 28 必须先运行依据算法编制的程序 时间统计量依赖于计算机的软硬件环境 double start, stop; time (&start); main process(n, …); time (&stop); double runTime = stop -start; printf ("%d%d\n" , n, runTime ); 事前分析估算(时间) 求出该算法的一个时间界限函数 一些影响因素: 算法的策略 §1.2 算法描述 分析 29 算法的策略 问题的规模 书写程序的语言 编译器产生的机器代码的质量 机器执行指令的速度 §1.2 算法描述与分析 算法分析 算法的时间是每语句执行时间的总和 每语句的执行时间=该语句执行次数（频度） X该语句执行1次的时间 假定：每语句执行1次的时间为1个时间单位 30 假定 每语句执行 次的时间为 则：算法的执行时间=∑各语句频度 问题的规模（Size）n 输入量的大小，如… 时间复杂度：算法的运行时间，是问题规模的函数
2014/4/7 81.2算法描述与分析 812算法描述与分析 ■时间复杂度 渐近时间复杂度（简称时间复杂度） 例1：矩阵乘法 瓷器责搜絮性能，只关心当道向无穷大时。 for(i=0;i<n;it+】 //n+1 for(j=0:j≤n;j+){ //n(n+1) C0]=0; 1/n2 lim T (n)/n 3 H→e for k=0;k<n;k++) //n2(n+1) C[]=C[]+A[i][k]*B[k]];//n3 lim(2n3+3n2+2n+1)/n3 鞋子8 =2 。详细分析：T(n)=2n343n2+2n+1 即：T(n)和n同阶，数量极相同 ◆简单分析：频度最大的语句 T(n)= =n3 记作：T(n)=O(n) S1.2算法描迷与分析 81.2算法描述与分析 大0的数学定义 若T(n)和f(n)是定义在正整数集合上的两个函数， 例3for(i-l:;iKan;+i 则T(n片O(f(n)表示存在两个正的常数c和no, {+x;s+x;】 使得当n2n时都满足0sT(n)scfn)。 语句频度为：2，其时间复杂度为：0()，即为线性阶。 例2+x:s=0动 例4for(i-l:ikn:+i 将x自增香成是基本操作，则语句频度为1，即时间 for(j-l;j<-n;++j) 复杂度为O(1)。 {+x:s+=;】 如果将-0也看成是基本操作，则语句频度为2，其 语句频度为：2m,其时间复杂度为：0(m,即为平方阶。 时间复杂度仍为0()，即常量阶。 3 ⑧12算法描述与分析 81.2算法描述与分析 定理：若A(o)-ann■+a1nm1++1n+a是一个m次多项 以下六种计算算法时间的多项式是量常用的。其关系为： 式，则A(=0(nm) O(1)<O(bgn)<O(n)<O(nbgn)<O(n2)<0(3) 例5fori-2:is-n+i 。指数时间的关系为： for(j-2;j<-i-1;++j) 02<0(n)<0n） (+x;alil-x;) 语句频度为：1+2+3计..+n-2-(1+n-2)X(-2)/2 当取得很大时，指数时间算法和多项式时间算法在所 需时间上非常悬殊。因此，只要有人能将现有指数时间算 -(n-1)n-2)/2-m2-3n+2 法中的任何一个算法化简为多项式时间算法，那就取得了 ∴时间复杂度为0(，即此算法的时间复杂度为平方阶。 一个伟大的成就。 个算法时间为0的算法，它的基本运算执行 ·有的情况下，算法中基本操作重复执行的次数还随问 的次数是因定的。因此，总的时间由一个常教 题的输入数据集不同而不同。 〔即零次多项式) 限 个时间为O(n2)的 算法则由 个二次多项 式来限界。 6
2014/4/7 6 §1.2 算法描述与分析 时间复杂度 例1：矩阵乘法 for ( i=0; i＜n; i++) //n+1 for ( j=0; j＜n; j++) { //n(n+1) C[i] [j]=0; //n2 for ( k=0;k＜n; k++) //n2(n+1) 31 for ( k 0;k＜n; k++) //n (n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]; //n3 } 详细分析： T(n)=2n3+3n2+2n+1 简单分析：频度最大的语句 T(n)= =n 3 === n 1 i 0 0 j 0 k 1 －－－ n 1 1n §1.2 算法描述与分析 渐近时间复杂度（简称时间复杂度） 从宏观上评价时间性能，只关心当n趋向无穷大时， T(n)的数量级(阶) lim ( )/ lim(2 3 2 1)/ 2 3 3 2 3 = + + + = →∞ →∞ T n n n n n n n n lim ( )/ lim(2 3 2 1)/ 2 3 3 2 3 = + + + = →∞ →∞ T n n n n n n n n 3 2 3 3 = → ∞ T n n n lim ( ) / 32 2 2 3 2 1 3 2 3 = + + + → ∞ n n n n n lim ( ) / 即：T(n) 和n3同阶，数量极相同 记作：T(n)=O(n3) §1.2 算法描述与分析 大O的数学定义 若T(n)和f(n)是定义在正整数集合上的两个函数， 则T(n)=O(f(n))表示存在两个正的常数c和n0， 使得当n≥n0时都满足0≤T(n)≤c·f(n)。 33 例２ {++x; s=0 ;} 将x自增看成是基本操作，则语句频度为１，即时间 复杂度为Ｏ(1) 。 如果将s=0也看成是基本操作，则语句频度为２，其 时间复杂度仍为Ｏ(1)，即常量阶。 例３ for(i=1; i<=n; ++i) { ++x; s+=x ; } 语句频度为：2n，其时间复杂度为：O(n) ，即为线性阶。 §1.2 算法描述与分析 34 例４ for(i=1; i<=n; ++i) for(j=1; j<=n; ++j) { ++x; s+=x ; } 语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平方阶。 定理：若A(n)=am n m +am-1 n m-1 +…+a1n+a0是一个m次多项 式，则A(n)=O(n m) 例５ for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) {++x; a[i,j]=x; } §1.2 算法描述与分析 35 语句频度为：1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 ∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。 一个算法时间为O(1)的算法，它的基本运算执行 的次数是固定的。因此，总的时间由一个常数 （即零次多项式）来限界。而一个时间为O(n2)的 算法则由一个二次多项式来限界。 以下六种计算算法时间的多项式是最常用的。其关系为： O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3) 指数时间的关系为： O(2n)<O(n!)<O(nn) 当 取得很大时 指数时间算法和多项式时间算法在所 §1.2 算法描述与分析 36 当n取得很大时，指数时间算法和多项式时间算法在所 需时间上非常悬殊。因此，只要有人能将现有指数时间算 法中的任何一个算法化简为多项式时间算法，那就取得了 一个伟大的成就。 有的情况下，算法中基本操作重复执行的次数还随问 题的输入数据集不同而不同
2014/4/7 例1：素数的判断算法。 例2：冒泡排序法。 Void prime(intn)/*n是一个正整数*/ Void bubble sort(int all,int n) int i=2; for (i=n-1,change=TURE;i>1 &change;-i) while ((n%i)!=0 &&i*1.0sgrt(n)） change=false: printf(“&d是一个素数n”,n); for (j=0;jalj+1D) printf(“&d不是一个赛数n”,n); {all←-一→ajt1;change=--TURE;} 嵌套的最深层语句是计+；其频度由条件(% ◆最好情况：0次 =0&&i*1.0sqrt(o)决定，显然i*1.0<sqrt(a),时 令最坏情况：1+2+3++n-1=n(n-1)/2 间复杂度0(m2)。 平均时间复杂度为：0(m) 81.2算法描述与分析 作业 ■空间复杂度(Space complexity):是指算法编写成程 1数据的逻辑结构？数据的物理结构？逻辑结构与物 序后，在计算机中运行时所需存储空间大小的度量。 记作：S(=O(f)其中：n为问题的规模（或大小） 理结构的区别和联系是什么？ 该存储空间一般包括三个方面： 2分析以下程序段的时间复杂度，请说明分析的理由 或原因。 ◆指令常数变量所占用的存储空间： (1) ·输入数据所占用的存储空间： suml(intn） ◆辅助（存储）空间。 int p=1,sum-0,m for (m-1;m<-n;m++) 一般地，算法的空间复杂度指的是辅助空间。 {p*-m;sum+=p;】 。一维数组a:空间复杂度O(m return (sum); 二维数组a口m:空间复杂度O和*m) (2) Sum2(int n) 3.按增长率由小至大的顺序排列下列各函数： int sum-0,m,t; 2o0,(3/2°，(23y,n,,nl,2,lgn,n,n for (m-l;m<-n;m++) {p-l; for (t=l;t<-m;t++)p*-t; 4.有时为了比较两个同数量级算法的优劣，须突出主项 sum+-p 的常数因子，而将降低次项用大“口”记号表示。例如 return (sum); 设T,(n=1.39 nign+100n+256=1.39nlgn+0(n),T(n) =2.0nlgn-2n=2.0nlgn+0(n),这两个式子表示，当n 足够大时r,(n)优于T),因为前者的常数因子小于后 (3)递归函数 者。请用此方法表示下列函数，并指出当足够大时， fact(int n) 哪一个较优，哪一个较劣？ if (n<-1)return(1) (1)T,(n=5n2.3n+60lgn2)T2(n=3n2+1000n+3lgn else return(n*fact(n-1)); (3)T3n=8n2+31gn (4T,(nj=1.5n2+6000nlgn 7
2014/4/7 7 例1：素数的判断算法。 Void prime( int n) /* n是一个正整数 */ { int i=2 ; while ( (n% i)!=0 && i*1.0sqrt(n) ) printf(“&d 是一个素数\n” , n) ; 37 else printf(“&d 不是一个素数\n” , n) ; } 嵌套的最深层语句是i++；其频度由条件( (n% i)!=0 && i*1.01 && change; --i) change=false; for (j=0; ja[j+1]) 38 if (a[j]>a[j+1]) { a[j] ←→a[j+1] ; change=TURE ; } } 最好情况：0次 最坏情况：1+2+3+⋯+n-1=n(n-1)/2 平均时间复杂度为： O(n2) 空间复杂度(Space complexity) ：是指算法编写成程 序后，在计算机中运行时所需存储空间大小的度量。 记作： S(n)=O(f(n)) 其中： n为问题的规模(或大小) 该存储空间一般包括三个方面： 指令常数变量所占用的存储空间; §1.2 算法描述与分析 39 指令常数变量所占用的存储空间; 输入数据所占用的存储空间; 辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。 一维数组a[n]： 空间复杂度 O(n) 二维数组a[n][m]： 空间复杂度 O(n*m) 作 业 1 数据的逻辑结构？数据的物理结构？逻辑结构与物 理结构的区别和联系是什么？ 2 分析以下程序段的时间复杂度，请说明分析的理由 或原因。 40 ⑴ Sum1( int n ) { int p=1, sum=0, m ; for (m=1; m<=n; m++) { p*=m ; sum+=p ; } return (sum) ; } ⑵ Sum2( int n ) { int sum=0, m, t ; for (m=1; m<=n; m++) { p=1 ; for (t=1; t<=m; t++) p*=t ; sum+=p ; } return (sum) ; 41 return (sum) ; } ⑶ 递归函数 fact( int n ) { if (n<=1) return(1) ; else return( n*fact(n-1)) ; } 3. 按增长率由小至大的顺序排列下列各函数： 4. 有时为了比较两个同数量级算法的优劣，须突出主项 的常数因子，而将降低次项用大“O”记号表示。例如， 设 T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n) ， T2(n) 100 n n n n lgn 3/2 2 , (3/2) , (2/3) , n , n, n!, 2 , lgn, n , n 42 1 2 = 2.0nlgn-2n=2.0nlgn+O(n)，这两个式子表示，当n 足够大时T1(n)优于T2(n)，因为前者的常数因子小于后 者。请用此方法表示下列函数，并指出当n足够大时， 哪一个较优，哪一个较劣？ ⑴ T1(n)=5n2-3n+60lgn ⑵ T2(n)=3n2+1000n+3lgn ⑶ T3(n)=8n2+3lgn ⑷ T4(n)=1.5n2+6000nlgn