算法效率的度量

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,算法效率的度量,（固有数据类型的操作）,时间复杂度计算,时间复杂度计算,时间复杂度计算,时间复杂度计算,时间复杂度分析,时间复杂度分析,空间复杂度,本章的,重点,是了解数据结构的,逻辑结构,、,存储结构,、,数据的运算,三方面的概念及相互关系，,难点,是,算法复杂度,的分析方法。,课堂小结,需要达到,层次的内容有：,算法,、算法的,时间复杂度,和,空间复杂度,、最坏的和平均时间复杂度等概念，,算法描述,和算法分析的方法、对一般的算法要能分析出时间复杂度。,需要达到,层次的基本概念和术语有：,数据,、,数据元素,、,数据项,、,数据结构,。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。,数 据 结 构 习 题 一,1.1,简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。,数据：,指能够被计算机识别、存储和加工处理的信息载体。,数据元素：,就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。,数据类型：,是一个值的集合以及在这些值上定义的一组操作的总称。,数据结构：,指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容,:,数据的逻辑结构、存储结构和数据的运算。,逻辑结构：,指各数据元素之间的逻辑关系。,存储结构：,就是数据的逻辑结构用计算机语言的实现。,线性结构：,数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。,非线性结构：,数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。,1.2,试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。,例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录,(,有姓名，学号，成绩等字段,),就是一个结点，对于整个表来说，只有一个开始结点,(,它的前面无记录,),和一个终端结点,(,它的后面无记录,),，其他的结点则各有一个也只有一个直接前趋和直接后继,(,它的前面和后面均有且只有一个记录,),。这几个关系就确定了这个表的,逻辑结构,。,那么我们怎样把这个表中的数据存储到计算机里呢,?,用高级语言如何表示各结点之间的关系呢,?,是用一片连续的内存单元来存放这些记录,(,如用数组表示,),还是随机存放各结点数据再用指针进行链接呢,?,这就是,存储结构,的问题。,最后，我们有了这个表,(,数据结构,),，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是,数据的运算,问题了。,1.3,常用的存储表示方法有哪几种,?,常用的存储表示方法有四种,:,顺序存储方法：,它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。,链接存储方法：,它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。,索引存储方法：,除建立存储结点信息外，还建立附加的索引表来标识结点的地址。,散列存储方法：,就是根据结点的关键字直接计算出该结点的存储地址。,1.4,设三个函数,f,g,h,分别为,f(n,)=100n,3,+n,2,+1000,g(n,)=25n,3,+5000n,2,h(n,)=n,1.5,+5000nlgn,请判断下列关系是否成立：,(1),f(n,)=,O(g(n,)(2),g(n,)=,O(f(n,)(3),h(n,)=O(n,1.5,)(4),h(n,)=,O(nlgn,),渐近时间复杂度的表示法的严格定义,:,“,若,T(n,),和,f(n,),是定义在正整数集合上的两个函数，则,T(n,)=,O(f(n,),表示存在正的常数,C,和,n,0,使得当,nn,0,时都满足,0T(n)Cf(n),。,”,(1),成立。,（,2,）成立。,（,3,）成立。,（,4,）不成立。,这两个函数当整型自变量,n,趋向于无穷大时，两者的比值是一个不等于,0,的常数,。,1.5,设有两个算法在同一机器上运行，其执行时间分别为,100n,2,和,2,n,要使前者快于后者，,n,至少要多大,?,最简单最笨的办法就是拿自然数去代呗。假定,n,取为,10,，则前者的值是,10000,，后者的值是,1024,小于前者，那我们就加个,5,，用,15,代入得前者为,22500,，后者为,32768,，已经比前者大但相差不多，那我们再减个,1,，用,14,代入得，前者为,19600,后者为,16384,，又比前者小了，所以结果得出来就是,n,至少要是,15,。,1.6,设,n,为正整数，利用大,O,记号，将下列程序段的执行时间表示为,n,的函数。,1.7,算法的时间复杂度仅与问题的规模相关吗,?,No,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。,1.8,按增长率由小至大的顺序排列下列各函数：,2,100,(2/3),n,，,(3/2),n,，,n,n,n!,，,2,n,，,lgn,n,lgn,n,(3/2),n,(1/2),分析如下：,2,100,是常数阶；,(2/3),n,和,(3/2),n,是指数阶,其中前者是随,n,的增大而减小的；,n,n,是指数方阶；,n,(1/2),是方根阶,n!,就是,n(n-1)(n-2).,就相当于,n,次方阶；,2,n,是指数阶，,lgn,是对数阶,n,lgn,是对数方阶,n,(3/2),是,3/2,次方阶。根据以上分析按增长率由小至大的顺序可排列如下：,(2/3),n,2,100,lgn,n n,(3/2),n,lgn,(3/2),n,2,n,n!,n,n,1.9,有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大,“,O”,记号表示。,例如，设,T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0lgn+O(n),这两个式子表示，当,n,足够大时,T1(n),优于,T2(n),，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当,n,足够大时，哪一个较优，哪一个较劣,?,