计算机软件技术基础计算机软件技术基础 数据结构数据结构东北大学网络学院计算机软件技术基础课程组教师：高克宁教师：高克宁E-mailE-mail：c_gknnecmail.neu.edu.cnc_gknnecmail.neu.edu.cn数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2 2 o主要内容主要内容o数据构造讨论的范畴数据构造讨论的范畴o根本概念根本概念o笼统数据类型笼统数据类型o算法的特性、分类及度量算法的特性、分类及度量o数据构造的选择和评价数据构造的选择和评价数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3 3 o数据构造讨论的范畴数据构造讨论的范畴o程序程序=数据构造数据构造+算法算法o数据构造：问题的数据模型数据构造：问题的数据模型o数据的逻辑构造数据的逻辑构造o数据的物理构造数据的物理构造o数据的运算数据的运算o算法：算法： 求解问题的战略求解问题的战略o查找查找o排序排序数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组4 4 o数据构造讨论的范畴数据构造讨论的范畴o数值计算的程序设计问题数值计算的程序设计问题o圆的面积函数圆的面积函数o构造静力分析计算构造静力分析计算 线性代数方程组线性代数方程组o人口增长预告微分方程人口增长预告微分方程数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组5 5 o数据构造讨论的范畴数据构造讨论的范畴o非数值计算问题的程序设计问题非数值计算问题的程序设计问题o学生信息管理系统表学生信息管理系统表o算法：需求检索的工程如何检索、用户界算法：需求检索的工程如何检索、用户界面面o模型：各种表格模型：各种表格o人机对弈树人机对弈树o算法：对弈的规那么和战略算法：对弈的规那么和战略o模型：棋盘及棋盘的格局模型：棋盘及棋盘的格局o教学方案编排问题图教学方案编排问题图o算法：课表编排的规那么算法：课表编排的规那么o模型：课程以及课程间关系模型：课程以及课程间关系数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组6 6 数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组7 7 数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组8 8 数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组9 9 o数据构造讨论的范畴数据构造讨论的范畴o数据构造是一门讨论数据构造是一门讨论“描画现实世界实体描画现实世界实体的数学模型的数学模型(非数值计算非数值计算)及其上的操作在及其上的操作在计算机中如何表示和实现的学科计算机中如何表示和实现的学科o学习数据构造的目的学习数据构造的目的o是为了了解计算机处置对象的特性，将实是为了了解计算机处置对象的特性，将实践问题中所涉及的处置对象在计算机中表践问题中所涉及的处置对象在计算机中表示出来并对它们进展处置示出来并对它们进展处置o经过算法训练来提高学生的思想才干，经经过算法训练来提高学生的思想才干，经过程序设计的技艺训练来促进学生的综合过程序设计的技艺训练来促进学生的综合运用才干和专业素质的提高运用才干和专业素质的提高数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组1010 o数据构造根本概念数据构造根本概念o数据数据data)o一切能输入到计算机中去的描画客观事物一切能输入到计算机中去的描画客观事物的符号的符号o是计算机操作的对象的总称是计算机操作的对象的总称o是计算机处置的信息的某种特定的符号表是计算机处置的信息的某种特定的符号表示方式示方式o数据元素数据元素data elemento数据构造中讨论的根本单位，也称结点数据构造中讨论的根本单位，也称结点node或记录或记录recordo是数据集合中的一个是数据集合中的一个“个体个体o例如：学生信息检索系统中学生信息表中例如：学生信息检索系统中学生信息表中的一个记录、对弈问题中形状树的一个形的一个记录、对弈问题中形状树的一个形状、排课问题中的一个顶点等，都被称为状、排课问题中的一个顶点等，都被称为一个数据元素一个数据元素数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组1111 o数据构造根本概念数据构造根本概念o数据项数据项data itemo有独立含义的数据最小单位，也称域有独立含义的数据最小单位，也称域(field)o数据元素可以是数据项的集合数据元素可以是数据项的集合o数据对象数据对象o是性质一样的数据元素的集合，是性质一样的数据元素的集合，o是数据的一个子集。是数据的一个子集。 数据元素是数据对数据元素是数据对象的一个实例象的一个实例o例如例如o整数数据对象是集合整数数据对象是集合N=-2,-1,0,1,2.数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组1212 o数据构造根本概念数据构造根本概念o数据构造数据构造data structure)o数据构造是相互之间存在着某种逻辑关系数据构造是相互之间存在着某种逻辑关系的数据元素的集合的数据元素的集合o例如：在一维数组例如：在一维数组 a1, a2, a3, a4, a5, a6 的数据元素之间存在如下的次的数据元素之间存在如下的次序关系序关系| i=1, 2, 3, 4, 5数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组1313 o什么是数据构造？什么是数据构造？o数据构造的三个方面数据构造的三个方面o数据的逻辑构造数据的逻辑构造o从详细问题笼统出来的数学模型，它与数从详细问题笼统出来的数学模型，它与数据的存储无关据的存储无关o线性构造：线性表、栈、队列线性构造：线性表、栈、队列o非线性构造：树、图非线性构造：树、图o数据的存储构造数据的存储构造o数据构造在计算机中的标识又称映像数据构造在计算机中的标识又称映像称为数据的物理构造，数据的逻辑构造在称为数据的物理构造，数据的逻辑构造在计算机存储器中的实现计算机存储器中的实现o顺序存储顺序存储o链式存储链式存储o数据的运算数据的运算o检索、排序、插入、删除、修正等检索、排序、插入、删除、修正等数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组1414 o什么是数据构造？什么是数据构造？ (1)o数据的逻辑构造数据的逻辑构造o数据的逻辑构造可以用一组数据表示为数据的逻辑构造可以用一组数据表示为结点集合结点集合D，以及这些数据之间的一组，以及这些数据之间的一组二元关系关系集合二元关系关系集合S来表示：来表示：( D ，S )o其中其中oD 是数据元素的有限集，是由有限个结是数据元素的有限集，是由有限个结点组成的集合，每一个结点都代表一个数点组成的集合，每一个结点都代表一个数据或一组有明确构造的数据据或一组有明确构造的数据oS 是是 D上关系的有限集，是定义在集合上关系的有限集，是定义在集合D上的一组关系，用它描画结点数据之间的上的一组关系，用它描画结点数据之间的逻辑关系逻辑关系Data_Structures = (D, S)数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组1515 o什么是数据构造？什么是数据构造？ (2)o数据的逻辑构造数据的逻辑构造o结点的数据类型结点的数据类型o高级言语中指数据的取值范围及其上可进高级言语中指数据的取值范围及其上可进展的操作的总称展的操作的总称o例例C言语中言语中o根本数据类型：根本数据类型：int, char, float, double等等o构造数据类型：数组、构造体、共用体、构造数据类型：数组、构造体、共用体、枚举枚举 o指针、空指针、空(void)类型类型o用户也可用用户也可用typedef 本人定义数据类型本人定义数据类型o结点的类型可以是根本数据类型，也可以结点的类型可以是根本数据类型，也可以根据运用的需求来灵敏定义根据运用的需求来灵敏定义typedef struct int num; char name20; float score; STUDENT;STUDENT stu, *pstu;数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组1616 o什么是数据构造？什么是数据构造？ (3)o数据的逻辑构造数据的逻辑构造o关系关系S阐明数据构造的特性阐明数据构造的特性o线性构造线性构造linear structureo一个对一个一个对一个o树型构造树型构造tree structureo一个对多个一个对多个o图状构造图状构造graph structureo多个对多个多个对多个数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组1717 o什么是数据构造？什么是数据构造？ (4)o数据的逻辑构造数据的逻辑构造o线性构造线性构造o关系关系S 是一种线性关系，或称为是一种线性关系，或称为前后关前后关系系，有时也称为，有时也称为大小关系大小关系。关系。关系S是有向的，且满足全序性和单索性等约束是有向的，且满足全序性和单索性等约束条件条件o全序性全序性o线性构造的全部结点两两皆可以比较前后线性构造的全部结点两两皆可以比较前后关系关系So单索性单索性o每一个结点每一个结点a都存在独一的一个直接后继都存在独一的一个直接后继结点结点b数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组1818 o什么是数据构造？什么是数据构造？ (5)o数据的逻辑构造数据的逻辑构造o树型构造树型构造o树型构造又称为层次构造，其关系树型构造又称为层次构造，其关系S称为称为层次关系层次关系o树型构造的最高层次的结点称为根树型构造的最高层次的结点称为根root结点结点o只需它没有父结点只需它没有父结点o每一个结点可以有多于一个的每一个结点可以有多于一个的子结点子结点，但是它只能有独一的，但是它只能有独一的父结点父结点o图状构造图状构造o也称为结点互联的网络构造，允许结点具也称为结点互联的网络构造，允许结点具有多个有多个父结点父结点o图构造的关系图构造的关系S没有任何约束，无法利用没有任何约束，无法利用关系关系S的约束来设计图构造的存储构造的约束来设计图构造的存储构造因特网的因特网的web网页链接关系网页链接关系是一个非常复杂的图构造是一个非常复杂的图构造数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组1919 o什么是数据构造？什么是数据构造？ (6)o数据的逻辑构造数据的逻辑构造o三种构造的区别三种构造的区别o树构造和图构造的根本区别就是树构造和图构造的根本区别就是“每个结每个结点能否仅仅从属一个父结点点能否仅仅从属一个父结点o线性构造和树构造的根本区别是线性构造和树构造的根本区别是“每个结每个结点能否仅仅有一个直接后继点能否仅仅有一个直接后继数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2020 o什么是数据构造？什么是数据构造？ (7)o数据的存储物理构造数据的存储物理构造o数据的逻辑构造在计算机存储器中的实现数据的逻辑构造在计算机存储器中的实现逻辑构造在存储器中的映象逻辑构造在存储器中的映象o计算机的主存储器的特性计算机的主存储器的特性o存储空间提供了一种具有非负整数地址编存储空间提供了一种具有非负整数地址编码的，相邻单元的集合码的，相邻单元的集合o其根本的存储单元是字节其根本的存储单元是字节o计算机的指令具有按地址随机访问存储空计算机的指令具有按地址随机访问存储空间内恣意单元的才干，访问不同地址所需间内恣意单元的才干，访问不同地址所需的访问时间根本一样的访问时间根本一样数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2121 o什么是数据构造？什么是数据构造？ (8)o数据的存储物理构造数据的存储物理构造o数据的存储构造是建立一种映象，对于数数据的存储构造是建立一种映象，对于数据逻辑构造据逻辑构造 D , s ,其中其中sSo“数据元素的映象数据元素的映象o对它的结点集合对它的结点集合D建立一个从建立一个从D到存储器到存储器的单元的映射：对于每一个结点的单元的映射：对于每一个结点dD都都对应一个独一的延续存储区域。对应一个独一的延续存储区域。o“关系的映象关系的映象o每一个关系元组每一个关系元组d1 ,d2s其中其中d1, d2D是结点，是结点， d1 ,d2的逻辑的逻辑后继关系应映射为存储单元的地址顺序关后继关系应映射为存储单元的地址顺序关系或链接关系系或链接关系数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2222 o什么是数据构造？什么是数据构造？ (9)o数据的存储物理构造数据的存储物理构造o顺序存储构造顺序存储构造o用一块无空隙的存储区域存储数据称为用一块无空隙的存储区域存储数据称为顺序存储顺序存储o借助元素在存储器中的相对位置来表示借助元素在存储器中的相对位置来表示数据元素间的逻辑关系数据元素间的逻辑关系o结点间的逻辑后继关系用存储单元的自结点间的逻辑后继关系用存储单元的自然顺序关系来表达然顺序关系来表达o链式存储构造链式存储构造o借助指示元素存储地址的指针表示数据借助指示元素存储地址的指针表示数据元素间的逻辑关系元素间的逻辑关系o两个结点的逻辑后继关系可以用指针的两个结点的逻辑后继关系可以用指针的指向来表达指向来表达数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2323 o什么是数据构造？什么是数据构造？ (10)o数据的存储物理构造数据的存储物理构造LoLo+mLo+(i-1)*mLo+n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+i-1)*m顺序存储顺序存储元素元素1 1元素元素2 2元素元素i i元素元素n nhead数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2424 o什么是数据构造？什么是数据构造？ (11)o数据的逻辑构造与存储构造亲密相关数据的逻辑构造与存储构造亲密相关算法设计 逻辑构造算法实现 存储构造数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2525 o笼统数据类型笼统数据类型Abstract Data Type Abstract Data Type 简简称称ADTADTo笼统数据类型是描画数据构造的一种实际笼统数据类型是描画数据构造的一种实际工具工具o特点是把数据构造作为独立于运用程序的特点是把数据构造作为独立于运用程序的一种笼统代数构造来描画一种笼统代数构造来描画o笼统数据类型不同于详细的数据构造笼统数据类型不同于详细的数据构造o目的是使人们可以独立于程序的实现细节目的是使人们可以独立于程序的实现细节来了解数据构造的特性来了解数据构造的特性数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2626 o笼统数据类型笼统数据类型1 1o笼统数据类型的定义取决于它的一组逻辑笼统数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实特性，而与其在计算机内部如何表示和实现无关现无关o即不论其内部构造如何变化，只需它的数即不论其内部构造如何变化，只需它的数学特性不变，都不影响其外部的运用学特性不变，都不影响其外部的运用数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2727 o笼统数据类型笼统数据类型(2)(2)o是指一个数学模型以及定义在此数学模型是指一个数学模型以及定义在此数学模型上的一组操作。上的一组操作。o“笼统的定义在于数据类型的数学笼统笼统的定义在于数据类型的数学笼统特性特性o笼统数据类型的方式定义：笼统数据类型的方式定义：o ADT= ADT=D D，S S，P Po其中：其中：D D是数据对象；是数据对象；S S是是D D上的关系集；上的关系集；P P是对是对D D的根本操作集。的根本操作集。ADT 笼统数据类型名笼统数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 根本操作：根本操作的定义根本操作：根本操作的定义 ADT 笼统数据类型名笼统数据类型名数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2828 例如，笼统数据类型复数的定义：例如，笼统数据类型复数的定义：ADT Complex 数据对象：数据对象： De1,e2e1,e2RealSet 数据关系：数据关系： R1 | e1是复数的实数部分；是复数的实数部分；| e2 是复数的虚数部分是复数的虚数部分 根本操作：根本操作： AssignComplex( &Z, v1, v2 ) 操作结果：构造复数操作结果：构造复数 Z,其实部和虚部分别被赋以参数其实部和虚部分别被赋以参数 v1 和和 v2 的值。的值。 DestroyComplex( &Z) 操作结果：复数操作结果：复数Z被销毁。被销毁。 GetReal( Z, &realPart ) 初始条件：复数已存在。初始条件：复数已存在。 操作结果：用操作结果：用realPart前往复数前往复数Z的实部值。的实部值。 GetImag( Z, &ImagPart ) 初始条件：复数已存在。初始条件：复数已存在。 操作结果：用操作结果：用ImagPart前往复数前往复数Z的虚部值。的虚部值。 Add( z1,z2, &sum ) 初始条件：初始条件：z1, z2是复数。是复数。 操作结果：用操作结果：用sum前往两个复数前往两个复数z1, z2 的和值。的和值。 ADT Complex数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组2929 o笼统数据类型笼统数据类型(3)(3)oADT ADT 重要特征重要特征o数据笼统数据笼统o用用ADTADT描画程序处置的实体时，强调的是描画程序处置的实体时，强调的是其本质的特征、其所能完成的功能以及它其本质的特征、其所能完成的功能以及它和外部用户的接口即外界运用它的方法和外部用户的接口即外界运用它的方法o数据封装数据封装o将实体的外部特性和其内部实现细节分别，将实体的外部特性和其内部实现细节分别，并且对外部用户隐藏其内部实现细节并且对外部用户隐藏其内部实现细节数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3030 o笼统数据类型笼统数据类型(4)(4)oADTADT与数据类型的关系与数据类型的关系o笼统数据类型和数据类型本质上是一个概笼统数据类型和数据类型本质上是一个概念念o“笼统的意义在于数据类型的数学笼统笼统的意义在于数据类型的数学笼统特性。特性。 o笼统数据类型需求经过固有数据类型笼统数据类型需求经过固有数据类型( (高高级编程言语中已实现的数据类型级编程言语中已实现的数据类型) )来实现来实现o笼统数据类型的范畴更广，它不再局限于笼统数据类型的范畴更广，它不再局限于各处置器中已定义并实现的数据类型，还各处置器中已定义并实现的数据类型，还包括用户在设计软件系统时本人定义的数包括用户在设计软件系统时本人定义的数据类型据类型数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3131 o笼统数据类型笼统数据类型(4)(4)数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3232 o算法的特性与度量算法的特性与度量o算法算法algorithmo处理某一特定问题的详细步骤的描画，是处理某一特定问题的详细步骤的描画，是指令的有限序列指令的有限序列o程序是算法的一种实现，计算机按照程序程序是算法的一种实现，计算机按照程序逐渐执行算法，实现对问题的求解逐渐执行算法，实现对问题的求解数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3333 o算法的特性与度量算法的特性与度量o算法的特性算法的特性o有穷性有穷性o对于恣意一组合法输入值，在执行有穷步对于恣意一组合法输入值，在执行有穷步骤之后一定能终了，即：算法中的每个步骤之后一定能终了，即：算法中的每个步骤都能在有限时间内完成骤都能在有限时间内完成o确定性确定性o对于每种情况下所应执行的操作，在算法对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在读者都能明确其含义及如何执行。并且在任何条件下，算法都只需一条执行途径任何条件下，算法都只需一条执行途径数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3434 o算法的特性与度量算法的特性与度量(1)o算法的特性算法的特性o可行性可行性o算法中的一切操作都必需足够根本，都可算法中的一切操作都必需足够根本，都可以经过曾经实现的根本操作运算有限次实以经过曾经实现的根本操作运算有限次实现之现之o输入输入o作为算法加工对象的量值，通常表达为算作为算法加工对象的量值，通常表达为算法中的一组变量。有些输入量需求在算法法中的一组变量。有些输入量需求在算法执行过程中输入，而有的算法外表上可以执行过程中输入，而有的算法外表上可以没有输入，实践上已被嵌入算法之中没有输入，实践上已被嵌入算法之中o输出它是一组与输出它是一组与“输入有确输入有确o定关系的量值，是算法进展信息加工后得定关系的量值，是算法进展信息加工后得到的结果，这种确定关系即为算法的功能到的结果，这种确定关系即为算法的功能数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3535 o算法的特性与度量算法的特性与度量(2)o算法设计的原那么算法设计的原那么o正确性正确性(correctness)o可读性可读性(readability)o强壮性强壮性(robustness)o高效率与低存储量高效率与低存储量正确性：算法该当满足以特定的正确性：算法该当满足以特定的“规规格阐明方式给出的需求以下四个层格阐明方式给出的需求以下四个层次：无语法错误次：无语法错误 、随意数据、刻意、随意数据、刻意数据、一切合法数据数据、一切合法数据可读性：算法主要是为了人的阅读与可读性：算法主要是为了人的阅读与交流，其次才是为计算机执行，因此交流，其次才是为计算机执行，因此算法应该易于人的了解；晦涩难读的算法应该易于人的了解；晦涩难读的程序易于隐藏较多错误而难以调试程序易于隐藏较多错误而难以调试强壮性：当输入的数据非法时，算法该当强壮性：当输入的数据非法时，算法该当恰当地作出反映或进展相应处置，而不是恰当地作出反映或进展相应处置，而不是产生莫名奇妙的输出结果。处置出错的方产生莫名奇妙的输出结果。处置出错的方法也不应是中断程序的执行，而应是前往法也不应是中断程序的执行，而应是前往一个表示错误或错误性质的值，以便在更一个表示错误或错误性质的值，以便在更高的笼统层次上进展处置高的笼统层次上进展处置高效率与低存储量：高效率与低存储量：效率指的是算法执行时间；存储量指效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关空间，两者都与问题的规模有关数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3636 o算法的特性与度量算法的特性与度量(3)o算法的执行效率算法的执行效率o处理同一个问题总是存在着多种算法，而处理同一个问题总是存在着多种算法，而算法设计者在所破费的时间和所运用的空算法设计者在所破费的时间和所运用的空间资源往往要两者之间采取折中，采用某间资源往往要两者之间采取折中，采用某种以空间资源换取时间资源的战略种以空间资源换取时间资源的战略o算法设计者可以经过算法分析，判别所提算法设计者可以经过算法分析，判别所提出的算法能否现实，设计出更好的算法出的算法能否现实，设计出更好的算法数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3737 o算法的特性与度量算法的特性与度量(4)o算法的执行效率算法的执行效率o用根据该算法编制的程序在计算机上执行用根据该算法编制的程序在计算机上执行所耗费的时间来度量所耗费的时间来度量o和算法执行时间相关的要素和算法执行时间相关的要素o算法选用的战略算法选用的战略o问题的规模问题的规模o编写程序的言语编写程序的言语o编译程序产生的机器代码的质量编译程序产生的机器代码的质量o计算机执行指令的速度计算机执行指令的速度数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3838 o算法的特性与度量算法的特性与度量(5)o算法的执行效率算法的执行效率o时间复杂度时间复杂度o假设，随着问题规模假设，随着问题规模 n 的增长，算法执行的增长，算法执行时间的增长率和时间的增长率和 f(n) 的增长率一样，那的增长率一样，那么可记作：么可记作：o 称称T (n) 为算法的为算法的(渐近渐近)时间复杂度时间复杂度o算法的渐进分析就是要估计，当数据规模算法的渐进分析就是要估计，当数据规模n逐渐增大时，资源开销逐渐增大时，资源开销T(n)的增长趋势的增长趋势o从数量级大小的比较来思索，当从数量级大小的比较来思索，当n增大到增大到一定值以后，资源开销的计算公式中影响一定值以后，资源开销的计算公式中影响最大的就是最大的就是n的幂次最高的项，其他的常的幂次最高的项，其他的常数项和低幂次项都是可以忽略的数项和低幂次项都是可以忽略的T (n) = O(f(n)数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组3939 o算法的特性与度量算法的特性与度量(6)o算法的执行效率算法的执行效率o如何估算算法的时间复杂度如何估算算法的时间复杂度o算法的执行时间与原操作执行次数之和成算法的执行时间与原操作执行次数之和成正比正比算法 = 控制构造 + 原操作固有数据类型的操作算法的执行时间算法的执行时间 = = 原操作原操作(i)(i)的执行次数的执行次数原操作原操作(i)(i)的执行时间的执行时间数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组4040 o算法的特性与度量算法的特性与度量(7)o算法的执行效率算法的执行效率例例1：NXN矩阵相乘矩阵相乘 for ( i=1; i=n; i+) n+1 for ( j=1; j=n; j+) n*(n+1) cij=0; n*n for (k=1; k=n; k+) n*n*(n+1) cij+=aik*bkj; n*n*n T(n)=2n3+3n2+2n+1=O( n3)数据结构概述2007东北大学网络学院计算机软件技术基础课程组东北大学网络学院计算机软件技术基础课程组4141 o算法的特性与度量算法的特性与度量(7)o算法的执行效率算法的执行效率o结论结论o随着随着n值的增大，增长速度各不一样，存值的增大，增长速度各不一样，存在以下关系在以下关系o当当f(n)为对数函数、幂函数、或它们的为对数函数、幂函数、或它们的乘积时，算法的运转时间是可以接受的，乘积时，算法的运转时间是可以接受的，称这些算法是有效算法；当称这些算法是有效算法；当f(n)为指数为指数函数或阶乘函数时，算法的运转时间是不函数或阶乘函数时，算法的运转时间是不可接受的，称这些算法是无效的算法可接受的，称这些算法是无效的算法慢慢 O(1) 常量阶常量阶 O(n) 线性阶线性阶 O(logn) 对数阶对数阶 O(n2) 平方阶平方阶 O(nk) 多项式阶多项式阶快快 O(2n) 指数阶指数阶