1、主要学习内容数据数据结构构相关概念相关概念12数据数据结构构课程学程学习的内容的内容3算法性能分析算法性能分析4算法及特点算法及特点数据结构相关概念v1、数据、数据v2、数据元素、数据元素v3、数据、数据项v4、数据、数据对象象v5、数据、数据结构构逻辑结构存储结构概念数据(Data)v所有能所有能输入入到到计算机中，并被算机中，并被计算机算机识别和和处理理的符号的的符号的总称称。v数数值型数据：整数、型数据：整数、实数数等；等；v非数非数值型数据：字符、文本、声音、型数据：字符、文本、声音、图像、像、视频等；等；v数据是数据是计算机程序加工的原料算机程序加工的原料，是信息的，是信息的编码表示
2、。表示。文字翻译程序处理的数据是各国语言文本字符串；视频编辑软件则处理的是视频、图片、音乐等多媒体数据。数据元素(Data Element)v数据集合中的数据集合中的一个个体一个个体。v是是数数据据的的基基本本单位位，在在计算算机机程程序序中中通通常常将将其其作作为一一个个逻辑整整体体进行行处理。理。v如如一一个个整整数数30，一一个个字字符符串串hello world，一一个个商商品品，一一节讲课视频等。等。v在在不不同同场合合下下，数数据据元元素素也也常常被被称称为元元素素、结点点、顶点点和和记录等。等。v当一个数据元素包含有多个部分信息当一个数据元素包含有多个部分信息时，通常被称，通常被
3、称为记录。v当当一一个个数数据据元元素素（记录）包包含含有有多多个个部部分分信信息息时，其其中中每每个个部部分的信息被分的信息被称称为一个一个数据数据项。v如如一一件件商商品品的的记录可可能能包包含含商商品品名名称称、编号号、类别、价价格格等等多多个数据个数据项。v数数据据项是是构构成成数数据据元元素素的的不不可可分分割割的的最最小小单位位，也也被被称称为字字段段、域域或或属性属性。数据项(Data Item)数据对象(Data Object)v数据数据对象是性象是性质相同的数据元素的集合，是数据的一个子集。相同的数据元素的集合，是数据的一个子集。v例例如如，整整数数的的数数据据对象象是是集集
4、合合0,1,2,，英英文文字字母母的的数数据据对象是集合象是集合a,A,b,B,。v在在具具体体应用用中中，一一个个数数据据对象象中中的的元元素素通通常常相相互互之之间存存在在某某种种关系关系。v相互之相互之间存在一种或多种特定关系的数据元素的集合；存在一种或多种特定关系的数据元素的集合；v带关关系系的的数数据据元元素素的的集集合合（Collection of relational data elements）。）。数据结构（Data Structure）结 构构 =实 体体 +关关 系系数据数据结构构 =数据元素数据元素+关关 系系ABv最最外外面面的的大大圆圈圈表表示示数数据据这个大集合；
5、个大集合；v标识为A和和B的的两两个个圆圈圈分分别表示表示2个数据个数据对象集合；象集合；v除除此此之之外外的的各各圆圈圈表表示示各各种不同大小的数据元素；种不同大小的数据元素；v数数据据对象象A、B中中分分别包包含含若干相同若干相同类型的数据型的数据元素元素；vB数数据据对象象中中的的数数据据元元素素之之间存存在在关关系系，即即形形成成了了一一种数据种数据结构。构。数据的层次v数据数据结构的概念由构的概念由C.A.R.Hoare和和N.Wirth在在1966年提出年提出。vAlgorithms+Data Structures=Programs-N.Wirth1976年年提出。提出。v精心精心
6、选择的的数据数据结构构可以可以带来更高的来更高的运行运行效率效率。v实现大大型型的的复复杂程程序序，必必须对程程序序所所处理理的的数数据据结构构进行行深深入入研究研究。数据结构（Data Structure）v数据数据结构构是是带关系的数据元素的集合。关系的数据元素的集合。v数据数据结构的构的2个个层面：面：逻辑结构存储结构数据结构（Data Structure）v逻辑结构构是是指指数数据据元元素素之之间的的内内在在关关系系（The intrinsic relations between data elements）。）。v根根据据数数据据元元素素之之间关关系系的的不不同同特特性性，数数据据结
7、构构被被抽抽象象为四四类逻辑结构构：线性结构线性结构（linear structure）树形结构树形结构（tree）图状结构图状结构（graph）集合结构集合结构（set）逻辑结构（Logical Structure）逻辑逻辑结构示意图结构示意图v线性性结构构(一一对一一)v树形形结构构(一一对多多)v图状状结构构(多多对多多)v集合集合(松散松散)逻辑结构（Logical Structure）v独立于独立于计算机，与是否算机，与是否存存储在在计算机算机中无关；中无关；v逻辑结构是构是从具体从具体问题中抽象出来的中抽象出来的数学模型；数学模型；vLogical_Structure=(D,R)其
8、中其中：D是数据元素的有限集合，是数据元素的有限集合，R是是D上关系的有限集合。上关系的有限集合。逻辑结构（Logical Structure）【例例1】设有数据有数据结构构G=(D,R)，其中：，其中：D=A,B,C,D,ER=,画出画出逻辑结构示意构示意图。逻辑结构（Logical Structure）vPython语言内置言内置数据数据类型中：型中：线性结构列表列表类型（型（list）、元）、元组类型（型（tuple）和字符串（）和字符串（str）等）等；集合结构集合（集合（set）和字典（）和字典（dict）等）等。逻辑结构（Logical Structure）v存存储结构是指数据构是
9、指数据结构在构在计算机的算机的内存内存中的存中的存储表示表示方法（映方法（映像方法），存像方法），存储内容包括：内容包括：数据元素数据元素本身；本身；数据元素之数据元素之间的的关系关系；存储结构（Storage structure）v数据元素映象方法数据元素映象方法根据数据根据数据元素的性元素的性质选取取对应的的类型型进行存行存储，最，最终对应于若干于若干个字个字节的二的二进制位串。制位串。如如Python语言中，整数言中，整数对象存象存储了相了相应的的对象象头部和若干字部和若干字节的的该值的二的二进制制补码。存储结构（Storage structure）v元素之元素之间关系的关系的映象映象方
10、法方法1顺序存序存储结构构2链式存式存储结构构3索引存索引存储结构构4哈希存哈希存储结构构存储结构（Storage structure）如：表示如：表示 x,yx,y 的的方法：方法：x yxy（a）元素内置的）元素内置的顺序存序存储（b）元素外置的）元素外置的顺序存序存储v1.顺序存序存储结构构 Contiguous implementation元素间的物理位置反映其逻辑关系存储结构（Storage structure）xyv2.链式存式存储结构构Linked implementation逻辑上相上相邻的元素，其物理位置不一定的元素，其物理位置不一定相相邻；元素元素之之间的的逻辑关系由关系由
11、附加的附加的链域域（指（指针域）来域）来指示；指示；表示表示 x,yx,y 的方法：的方法：在存在存储x对象的同象的同时附加存附加存储一个地址，一个地址，该地址地址为y对象的内存象的内存映像的位置，称映像的位置，称为指向指向y的指的指针。存储结构（Storage structure）v2.链式存式存储结构构Linked implementation元元素素在在内内存存中中的的映映像像包包含含：元元素素值和和指指针域域，这两两个个部部分分的的整整体体，称称为结点点；每每个个结点点的的存存储空空间是是单独独分分配配的的，因因此此存存储这些些结点点的的内内存存空空间不一定是不一定是连续的；的；通通过
12、指指针域将每一域将每一个个结点点连接接起来起来，形成，形成链式存式存储结构。构。v链式存式存储结构存构存储线性表性表 存储结构（Storage structure）v3.索引存索引存储结构构主主数据表用数据表用顺序表序表存存储元素信息的同元素信息的同时，再建立附加的，再建立附加的索引表索引表。该方法主要用于方法主要用于快速快速查找找数据元素。数据元素。详见11章。章。存储结构（Storage structure）块间有序块内可以无序v4.哈希存哈希存储结构构也称也称哈希表，哈希表，散列散列表，表，通常通常是一个稀疏是一个稀疏顺序表，用于存序表，用于存储集合集合，元素的存元素的存储位置由关位置由
13、关键字字值决定。决定。该方法主要用于方法主要用于快速快速查找找数据元素数据元素。详见11章章。Python中的字典中的字典dict和集合和集合set底底层就是用哈希存就是用哈希存储结构构实现的。的。存储结构（Storage structure）v顺序存序存储结构构和和链式存式存储结构构是两种最基本、最常用的存是两种最基本、最常用的存储结构。在构。在实际应用用中常将两者中常将两者进行行组合运用。合运用。v同一种同一种逻辑结构构可可采用采用不同的存不同的存储方案方案，得到，得到不同的存不同的存储结构构。v表示某种表示某种逻辑结构构时选择何种存何种存储结构构，应视不同的不同的应用用场合合确定。通常确
14、定。通常从从存存储结构的空构的空间性能性能、常用基本操作的常用基本操作的时间性性能能以及以及算法的算法的简便性便性等角度等角度进行考行考虑。存储结构（Storage structure）v线性表与性表与Python的的list的关系的关系线性表是逻辑结构概念，list是线性表在Python中的一种内置存储实现方法，线性表可以有其它存储方式；Python的list中的数据元素可以不同构。问题讨论v高高级语言中的概念言中的概念。v用于区分不同用于区分不同性性质的数据并的数据并对它它们做不同操作。做不同操作。v某某种种特特定定语言言中中，确确定定了了对象象的的数数据据类型型，也也就就确确定定了了该对
15、象象的的取取值范范围、存、存储方法和可方法和可进行的操作行的操作。v例例如如Python语言言中中的的整整数数数数据据类型型用用于于存存储所所有有整整数数，采采用用变长结构构进行行存存储，可可进行行的的操操作作有有加加、减减、乘乘、除除、求求余余数数等。等。数据类型（Data Type）vPython语言言的的数数据据类型型包包括括内内置置的的数数据据类型型、模模块中中定定义的的数数据据类型型和和用用户自自定定义的的类型型。内内置置数数据据类型型包包括括数数值类型型、序序列列类型型、集集合合类型型等等，数数值类型型则包包括括整整数数、浮浮点点数数、复复数和布数和布尔类型。型。v按按照照对象象值
16、是是否否可可分分解解，数数据据类型型分分为原原子子类型型和和组合合类型型。例例如如：Python数数值对象象的的值不不可可再再分分解解，属属于于原原子子类型型；而而序列序列类型和集合型和集合类型的型的对象包括了多个成分，象包括了多个成分，属于属于组合合类型型。数据类型（Data Type）v抽抽象象数数据据类型型是是指指一一个个数数学学模模型型及及定定义在在该模模型型上上的的一一组操操作作，简称称ADT。这个个概概念念允允许我我们定定义现实世世界界中中的的任任何何对象象，但但它它去去除除了了数数据据类型型概概念念中中关关于于具具体体存存储方方法法的的描描述述，仅包包含含两两个个方方面面：一一是
17、是对该数数学学模模型型本本身身性性质的的描描述述，二二是是对该模型的基本操作的描述模型的基本操作的描述。vADT定定义的两个方面的两个方面对应于：于：数据结构的逻辑结构和对该数据结构的操作；因此可以用ADT定义来描述数据结构，但注意ADT定义与计算机内部表示和实现无关，因此此时描述的数据结构也不涉及具体的存储方案。抽象数据类型（Abstract Data Type）v在在C+和和Java语言言中中，可可以以用用抽抽象象类来来描描述述抽抽象象数数据据类型型，然然后再后再设计普通普通类来来实现抽象抽象类完成完成对它的表示和操作它的表示和操作。v在在Python语言言中中，可可以以通通过引引入入AB
18、C模模块利利用用抽抽象象基基类来来描描述述抽象数据抽象数据类型，型，ABC是是Abstract Base Class的的缩写写。抽象数据类型（Abstract Data Type）抽象数据类型“容器”的定义v利利用用ABC模模块定定义一一个个抽抽象象基基类AbsrtactContainer来来表表示示抽抽象象数据数据类型型“容器容器”。v一个容器一个容器类型的型的对象可以容象可以容纳多个元素，并且具有以下操作：多个元素，并且具有以下操作：返回容器中元素个数；判断容器是否为空；在容器中放入元素item；在容器中删除元素item；判断容器中是否包含元素item；清空容器中的所有元素；输出容器中的所
19、有元素。from abc import ABCMeta,abstractproperty,abstractmethodclass AbstractContainer(metaclass=ABCMeta):抽象容器类，metaclass=ABCMeta表示将AbstracContainer类作为ABCMeta的子类 继承于abc.ABCMeta的类可以使用abstractproperty,abstractmethod修饰器声明虚属性与虚方法 abstractmethod def size(self):返回容器中元素的个数 abstractmethod def empty(self):判断容器是否
20、为空 abstractmethod def insert(self,item):在容器中放入元素item abstractmethod def remove(self,item):在容器中删除元素item abstractmethod def contains(self,item):判断容器中是否包含元素item abstractmethod def clear(self):清空容器中的所有元素 abstractmethod def output(self):输出容器中的所有元素 抽象数据类型“容器”的定义v定定义一一个普通个普通类AContainervAContainer继承抽象基承抽象基类
21、AbstractContainervAContainer实现AbstractContainer的各个方法的各个方法抽象数据类型“容器”的实现class AContainer(AbstractContainer):def _init_(self,source=):self.data=source def size(self):return len(self.data)def empty(self):return len(self.data)=0 def insert(self,key):self.data.append(key)def contains(self,x):return x in s
22、elf.data def remove(self,key):return self.data.remove(key)def clear(self):self.data.clear()def output(self):print(self.data)a=AContainer(3,4)a.insert(5)a.insert(6)a.remove(4)a.output()a.clear()a.output()抽象数据类型“容器”的实现v数据数据结构、构、ADT与与Python类的关系的关系用ADT来描述数据结构的逻辑结构及其操作用Python的抽象类来定义ADT用Python的普通类来实现ADT，即
23、实现数据结构的逻辑结构、存储结构和基本操作当然，同一ADT可以有多种不同的实现方案。v数据数据结构通常包括构通常包括2个个层次：次：逻辑结构：元素之构：元素之间的关系，与的关系，与计算机无关算机无关存存储结构：数据构：数据结构的存构的存储，与，与计算机相关算机相关问题数据结构课程学习的内容v要要在在某某城城市市新新区区的的各各小小区区之之间铺设通通讯线路路,要要求求连通通每每个个小小区，并使得区，并使得总投投资最小。最小。请设计一个方案。一个方案。v假假设该新新区区共共有有n个个小小区区，要要连通通n个个小小区区，至至少少需需要要铺设多多少条少条线路？路？n-1如4个小区，必须要有3条线路才能
24、连通它们v到底到底选哪几条哪几条线路呢路呢？例：最小代价铺设通讯线路例：最小代价铺设通讯线路a、b、c、d四四个个小小区区，测算算出出每每两两个个小小区区之之间铺设通通讯线路路的的造造价，并用一个价，并用一个带权图来表示；来表示；图的的顶点点表表示示小小区区，顶点点之之间的的边及及权值表表示示对应小小区区间架架设通通讯线路路时所所需需的的代代价价，如如连通通a、b小区的代价是小区的代价是12万；万；这个个最最小小代代价价连通通的的问题对应于于图的最小生成的最小生成树的求解的求解问题；整整个个问题归结为图的的存存储表表示示和和最小生成最小生成树求解的求解的问题。算法实现/算法分析外部对象（小区）
25、实现功能（最小代价连通）逻辑结构（带权图）基本操作（求解最小生成树）存储结构（邻接矩阵或邻接表）数据抽象问题抽象数据表示算法抽象应用程序编程调试与计算机无关与计算机无关数据结构课程数据结构课程研究研究内容内容抽象数据抽象数据类型类型v在于在于解决两个主要解决两个主要问题：根据实际问题选择一种好的数据结构；设计一个好的算法，好的算法在很大程度上取决于描述实际问题的数据结构。vPrograms=Algorithm+Data Structures （程序（程序=算算 法法+数数 据据 结 构构 ）数据结构：问题的数学模型，它反映数据元素之间关系。算 法：解决问题的策略、步骤程序设计的实质v1.确定求
26、解确定求解问题的的数学模型数学模型（逻辑结构构）；v2.确定存确定存储结构；构；v3.设计算法；算法；v4.性能分析与性能分析与改改进；v5.编程、程、调试、测试程序设计的主要步骤课程内容 方面方面过程过程数据数据表示表示数据数据处理处理抽象抽象逻辑结构逻辑结构基本运算基本运算实现实现存储结构存储结构算法算法评价评价不同数据结构的比较、不同数据结构的比较、选择和选择和和和算法性能分析算法性能分析应用应用使用经典数据结构编写程序使用经典数据结构编写程序剖析剖析分析分析PythonPython的典型数据结构的典型数据结构Asymptotic Time Complexity（时间复复杂度）度）Asy
27、mptotic Space Complexity（空空间复复杂度）度）v掌掌握握线性性表表、栈、队列列、树、二二叉叉树、图等等常常见的的数数据据结构构的的基本概念、特点、存基本概念、特点、存储表示、基本操作的表示、基本操作的实现及及应用；用；v掌掌握握算算法法的的设计方方法法，并并学学会会对算算法法进行行性性能能分分析析，进而而设计出出更更高高效效的的算算法法；掌掌握握计算算机机中中最最常常见的的查找找、排排序序等等操操作作的算法原理、的算法原理、实现方法，并分析比方法，并分析比较各算法的性能；各算法的性能；v采采用用Python语言言描描述述和和实现各各基基本本数数据据结构构的的存存储与与操
28、操作作，将将Python语言言的的内内置置数数据据结构构作作为基基本本数数据据结构构的的具具体体案案例例进行行剖析。剖析。v培培养养、训练学学生生选用用合合适适的的数数据据结构构，编写写质量量高高、风格格好好的的应用程序的用程序的能力能力。课程学习目标算法及特点v算算法法（Algorithm）是是对特特定定问题求求解解步步骤的的一一种种描描述述（Description of the particular steps of the process of a problem），是是指指令令的的有有限限序序列列，其其中中每每一一条条指指令令表表示示一一个个或或多个操作多个操作。什么是算法v对一一个个
29、特特定定问题，用用某某种种方方法法描描述述一一个个求求解解过程程，对该问题的的每每个个实例例，该过程程都都能能给出出解解，这个个描描述述就就是是解解决决该问题的的一个算法。一个算法。v对一一个个特定特定问题，可能有，可能有不同的算法不同的算法，也可能没有算法。，也可能没有算法。求任意正实数a的平方根的算法（牛顿迭代法）1.任取一个非任取一个非 0 的初始的初始值 x（例如取例如取 x=1）；2.当当x2 与与 a之之间的差大于的差大于误差，差，执行循行循环：x=x-(x2-a)/(2x)；3.将将x 作作为 a 的平方根返回；的平方根返回；v有有穷性性，算算法法必必须在在执行行有有穷步步骤后后
30、结束束，而而且且其其中中的的每每一步一步骤都是有都是有穷的的；v可可行行性性，算算法法的的每每一一条条指指令令所所对应的的操操作作可可以以完完全全机机械械地地进行，并且可在有限的行，并且可在有限的时间、空、空间资源下源下完成；完成；v确确定定性性，算算法法中中的的每每条条指指令令应确确切切定定义、没没有有歧歧义，即即对于某个确定的于某个确定的输入，算法的入，算法的执行路径和行路径和执行行结果都是唯一的果都是唯一的；v输入入，算法，算法有明确有明确定定义的的0个或多个个或多个输入；入；v输出出，算算法法有有明明确确定定义的的1个个或或多多个个输出出，表表示示算算法法的的处理理结果果。算法的性质v
31、算算法法描描述述了了一一个个问题的的解解决决过程程，用用于于人人与与人人之之间的的交交流流，交交流流的的内内容容是是某某一一问题的的求求解解过程程，主主要要目目的的是是帮帮助助人人们理理解解和思考相和思考相应问题的求解思想、方法、所用技的求解思想、方法、所用技术和和过程。程。v在在抽抽象象考考虑一一个个计算算过程程，或或考考虑该求求解解过程程的的抽抽象象性性质时，常用常用“算法算法”作作为术语。v在在考考虑一一个个求求解解过程程在在某某种种高高级语言言下下的的具具体体实现时，常常用用“程序程序”这一一术语。算法和程序 v程序程序是一个或多个算法的具体是一个或多个算法的具体实现，而，而算法算法是
32、程序是程序的的抽象、精髓和灵魂抽象、精髓和灵魂；v同同一算法可用不同的一算法可用不同的计算机算机语言言实现。v程程序序的的性性能能由由其其蕴含含的的算算法法和和运运行行的的环境境决决定定。通通常常语言言越越高高级，程程序序的的效率效率越差。越差。v每每一一个个程程序序的的背背后后，都都隐藏藏着着一一个个或或一一些些算算法法，正正确确实现的的程程序序能能解解决决相相关关算算法法所所解解决决的的问题，其其（运运行行时的的）动态性性质反反应了了相相关关算算法法的的特特征征（是相（是相应算法的合理算法的合理实现）v程程序序用用某某种种计算算机机能能处理理的的具具体体编程程语言言描描述述，通通常常会会包
33、包含含一一些些与与具具体体语言有关的言有关的细节结构和描述方式方面的特征。构和描述方式方面的特征。v算算法法具具有有有有穷性性，程程序序不不需需要要具具备有有穷性性。一一般般的的程程序序都都会会在在有有限限时间内内终止止，但但有有的的程程序序却却可可以以不不在在有有限限时间内内终止止，如如操操作作系系统在在正正常常情情况况下下永永远都不会都不会终止。止。算法和程序v算法可以用不同的方式描述算法可以用不同的方式描述需要在易易读易理解易理解和严格性格性之间取得某种平衡v用用自然自然语言描述言描述的的计算算过程（可能易程（可能易读，但可能出，但可能出现歧歧义）在自然语言描述中结合一些数学形式的描述（
34、减少歧义）v流程流程图等框等框图v采用采用伪代代码形式形式，结合高合高级语言和自然言和自然语言言用 Python 语言，结合自然语言帮助说明利用Python语言的函数或类的方法来描述一个特定算法，采用自顶向下逐步求精的思想进行算法设计，通常使得每个函数或方法完成相对较集中的一个功能。算法的描述方法1.任取一个非任取一个非 0 的初始的初始值 x（例如取例如取 x=1）；2.当当x2 与与 a 之之间的差大于的差大于误差，差，执行循行循环：x=x-(x2-a)/(2x),即：即：x=(x+a/x)/23.将将x 作作为 a 的平方根返回的平方根返回；求任意实数a的平方根的算法（牛顿迭代法）def
35、 my_square_root(a,delta):x=1 while math.fabs(x*x-a)delta:x=(x+a/x)/2 return xv实际应用中的算法用中的算法，具体，具体实现注定注定千差万千差万别。但也有许多算法的设计思想有相似之处可以对它们分类，进行学习和研究v设计算法的一些通用思想称算法的一些通用思想称为算法算法设计模式模式。如。如：暴力枚举法贪心法分治法回溯法动态规划法分支限界法算法设计算法性能分析（1）正正确确性性：要要求求算算法法能能够正正确确地地执行行，并并满足足预先先设定定的的功功能和性能要求，大致分能和性能要求，大致分为以下以下4个个层次：次：不含语法错
36、误。对于若干组输入数据，能够得出满足要求的结果。对于精心选择的典型、苛刻而带有刁难性的输入数据，能够得出满足要求的结果。对于一切合法的输入数据，都能够得出满足要求的结果。算法设计的目标（2）可可读性性：算算法法应该容容易易阅读，一一个个容容易易阅读的的算算法法便便于于人人们理理解解，人人们才才有有可可能能基基于于该算算法法写写出出正正确确的的程程序序。提提高高算算法法可可读性的方法主要有两性的方法主要有两个个:注释：一是给算法添加注释，以方便程序设计者和后续维护人员阅读和查错。命名：要注意对函数、变量等对象进行合理命名。如何评价一个算法的好坏（3）健壮）健壮性性算法应具有容错处理的功能，当输入
37、的数据不合法或运行环境改变时，算法都能恰当地做出反应或进行处理，而不是产生莫名其妙的输出结果。可以通过在算法中增加异常处理语句，对算法进行不断测试和优化达到算法的健壮性。如何评价一个算法的好坏（4）高效率）高效率算法算法的效率分的效率分为时间效率效率和和空空间效率效率；时间效率效率高高：运行运行速度快速度快的算法；的算法；空空间效率效率高高：算法算法执行行过程中占用内存空程中占用内存空间少少；时间效效率率和和空空间效效率率常常常常不不能能同同时兼兼顾，时间效效率率较高高的的算算法法可可能是能是牺牲了部分空牲了部分空间效率而效率而获得得。通常通常更关注更关注时间效率效率。如何评价一个算法的好坏（
38、4）高效率高效率在在一一些些应用用中中，为了了获得得理理想想的的时间效效率率，甚甚至至会会降降低低算算法法的的正正确性要求确性要求。天天气气预报的的程程序序，明明天天的的天天气气预报计算算至至少少要要在在今今天天下下午午完完成；成；数数字字相相机机的的人人脸识别程程序序，必必须在在几几分分之之一一秒秒完完成成工工作作。用用户不会接受更慢的算法。不会接受更慢的算法。如何评价一个算法的好坏v选取最取最优的的算法算法v对当前当前算法的不足加以算法的不足加以改改进v根根据据算算法法分分析析的的结果果进一一步步优化化数数据据结构构的的逻辑结构构和和存存储结构构算法分析的目的v事后事后统计法步法步骤：将算
39、法编制成完整的程序在不同问题规模、不同输入案例下执行程序统计程序的绝对运行时间来度量和研究算法的时间效率。衡量算法时间效率方法一：事后统计法v利利用用高高级语言言中中的的时间函函数数测量量程程序序运运行行所所花花的的绝对挂挂钟时间，并并对时间数据数据进行分析；行分析；v在在Python语言言中中，可可使使用用time模模块的的或或perf_counter()或或time()等函数；等函数；v也也可可以以引引入入 timeit 模模块，通通过在在 timeit 模模块 中中创建建Timer 对象象并并进行行相相应操操作作，可可以以测量量出出指指定定语句句执行行一一定定次次数数（默默认100万次）
40、所花万次）所花费的的时间。具体方法61v1其其它它因因素素可可掩掩盖盖算算法法本本质，并并不不是是客客观的的算算法法性性能能评价价方方法。法。程序的绝对运行时间与软硬件环境有关，受硬件环境（如处理器性能、内存和硬盘容量）以及算法运行的软件环境（如操作系统，程序设计语言）等的影响。v2必必须编写完整程序并运行。写完整程序并运行。事后统计法的缺点程序运行时间相关因素v程序程序在在计算机上运行所花算机上运行所花时间取决于下列因素：取决于下列因素：算法选用何种策略；问题的规模；所使用的程序设计语言，就同一个算法而言，用级别越高的语言实现，其执行的效率越低；编译程序所产生的机器代码的质量；处理器性能、内
41、存和硬盘容量等。v独立独立于所有于所有软硬件因素，并不硬件因素，并不获得程序得程序执行的精准行的精准时间值；v用用称称为“时间复复杂度度”的的数数量量级的的量量度度，反反映映出出随随着着问题规模模的的增大增大，算法运行算法运行时间的增的增长趋势；v在算法在算法编制成完整程序前即制成完整程序前即可衡量出可衡量出算法的算法的性能性能。衡量算法时间效率方法二：事前分析估算v将将算算法法运运行行总总工工作作量量用用算算法法中中所所有有语句句执行行原原操操作作的的次次数数之和之和T(n)表示，表示，T(n)称称为时间函数或函数或时间代价函数。代价函数。原操作是指运行时间是常量时间的操作；数值类型数据的赋
42、值、所有数学运算、原子类型数据的输入和输出等都是原操作；而判断值x是否在长度为n的列表中的in操作则不是原操作，它包含了若干次值的比较原操作。v当当n 时，时间函函数数T(n)的的数数量量级表表示示称称为渐进时间复复杂度，度，简称称时间复复杂度度，记为T(n)=O(f(n)。v表表示示当当n趋于于无无穷大大时，算算法法运运行行时间由由f(n)决决定定，运运行行时间的增的增长率与率与f(n)的增的增长率相同率相同。衡量算法时间效率方法二：事前分析估算例1程序段语句执行原操作的次数for i in range(0,n):for j in range(0,n):mcij=maij+mbij时间函数渐
43、进时间复杂度nn2n2T(n)=2n2+n取时间函数的最高次项，得：T(n)=O(n2)解释v在在方方阵相相加加算算法法中中，将将所所有有原原操操作作执行行次次数数加加起起来来，得得到到时间函函数数T(n)=2n2+n，n是是方方阵的的阶数数（问题的的规模模，规模模因因子子）。v当当n足足够大大时，对T(n)的的值起起决决定定性性影影响响的的是是第第一一项2n2，第第二二项可可以以忽忽略略不不计，即即可可以以认为T(n)的的值接接近近于于2n2，进而而认为该算算法法运运行行时间的的增增长率率与与n2的的增增长率率是是相相同同的的，表表示示为T(n)=O(n2)。v这种种时间性性能能的的表表示示
44、方方法法称称为算算法法的的渐进时间复复杂度度，是是一一个个数数量量级的的概概念念，用用大大O记号号表表示示，反反映映出出在在规模模n趋于于无无穷大的大的过程中，算法代价增程中，算法代价增长的速度。的速度。vT(n)=O(n2)，称，称为平方平方阶的的时间复复杂度。度。v当当且且仅当当存存在在正正常常数数c和和n0，当当nn0，T(n)cf(n)总是是成成立立，则称称该算法的算法的时间复复杂度度为O(f(n)，记为T(n)=O(f(n)。上例中，T(n)=2n2+n存在正常数c=3和n0=1，当nn0时，T(n)=2n2+n2n2+n2cn2，总是成立，因此T(n)=O(n2)。v以以大大O表表
45、示示的的时间复复杂度度，是是对算算法法执行行时间的的一一种种保保守守估估计，是是算算法法性性能能的的上上界界，即即对于于规模模为n的的任任意意输入入，算算法法的的运运行行时间都都不会超不会超过O(f(n)，即，即时间性能不会差于性能不会差于O(f(n)。时间复杂度的数学定义例2程序段语句执行原操作的次数m=0;for i in range(1,n+1):for j in range(i,n+1):m+=1时间函数渐进时间复杂度1nn(n+1)/2n(n+1)/2T(n)=n2+2n+1取时间函数的最高次项，得T(n)=O(n2)v（1）将将所所有有语句句的的原原操操作作执行行次次数数之之和和作
46、作为算算法法的的运运行行时间函数函数T(n)。v（2）忽忽略略时间函函数数T(n)的的低低次次项部部分分和和最最高高次次项的的系系数数，只只取取时间函数的最高次函数的最高次项，并，并辅以大以大O记号表示号表示。n指的是问题的规模，如被排序的数组中元素的个数，矩阵的阶数等。时间复杂度计算方法时间函数时间复杂度(1)n2+1000n(2)3n3+100n2(3)10+3log10n(4)10n+20nlog10n(5)12+n3+2n(6)1000nO(n2)O(n3)O(log10n)O(nlog10n)O(2n)O(n)v从从算算法法中中选取取对于于所所研研究究的的问题来来说是是关关键操操作作
47、的的语句句，以以该关关键操操作作语句句中中重重复复执行行原原操操作作的的次次数数的的数数量量级作作为算算法法运运行行时间效率的量度。效率的量度。关键操作通常是循环最深层的一句语句，是算法中执行原操作的次数数量级最高的一句语句，当执行次数最高的语句有多句时，可以选择任意一句为其关键操作，通常选取算法中完成主要任务的语句为关键操作。求解时间复杂度简化方法算法时间复杂度def f3(lst,i):lsti=lsti+1def f4(lst,n):for i in range(0,n,2):lsti=lsti+1def f5(x,n):for i in range(0,n):for j in rang
48、e(0,n):x=x+1def f6(n):i=1 while i m，所以将n-1号开始一直到j号位置的元素依次后移k-m个位置，即从9开始到3的全部元素后移3个位置，再将,a,b,c,d,e,依次赋给a_list1-a_list5。def prime(n):for i in range(2,int(math.sqrt(n)+1):if n%i=0:return False return True其它情况def insertion_sort(lst):for i in range(1,len(lst):j=i-1 current=lsti while j=0:if lstjcurrent:l
49、stj+1=lstj else:break j-=1 lstj+1=currentv若若算法中不存在算法中不存在循循环-O(1)?如算法中的每一句语句都为原操作，则算法时间复杂度为常量阶；v若算法中若算法中仅存在一重循存在一重循环-O(n)?循环体内仅包含原操作决定算法时间复杂度的是该循环中关键语句的原操作执行次数；如循环变量以常数递增或递减，。v若若算法中算法中存在存在m重循重循环-O(nm)?决定算法时间复杂度的是循环嵌套层数最深的关键语句的原操作的执行次数。问题？算法的空间复杂度v与与算算法法的的时间复复杂度度类似似，算算法法的的空空间复复杂度度也也认为是是问题规模模n的函数，并以数量的
50、函数，并以数量级的形式的形式给出，出，记作作S(n)=O(g(n)v程序程序在在计算机运行算机运行时所占用的存所占用的存储空空间包括以下部分包括以下部分：输入数据所占用的存储空间程序本身所占用的存储空间临时变量所占用的存储空间v在在对算算法法的的空空间复复杂度度进行行研研究究时，只只分分析析临时变量量所所占占用用的的存存储空空间。算法的空间复杂度举例def sum(lst):result=0 for i in range(0,len(lst):result+=lsti return resultv不不计形形参参lst所所占占用用的的空空间，只只计算算局局部部变量量i和和result所所占占用用
