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

数据结构,刘士军Lsj山东大学计算机学院,2,学习本课的目的？,用数字计算机解决任何应用问题都离不开数据表示和数据处理。而数据表示和数据处理的核心问题之一就是数据结构及其操作的实现。算法设计提供了使用计算机解决问题的基本思维方式。算法分析是关于算法评价的科学方法。,3,讲述内容,数据结构与算法分析概论11线性结构11栈和队列11数组和广义表1树结构22图结构23搜索24排序25,第一章绪论,5,1.1数据结构讨论的范畴,NiklausWirthAlgorithm+DataStructures=Programs程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型例如:数值计算的程序设计问题结构静力分析计算线性代数方程组全球天气预报环流模式方程非数值计算的程序设计问题,6,例1书目自动检索系统,书目文件,7,例2人机对奕问题,8,例3多叉路口交通灯管理问题,9,数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科,10,数据所有能被输入到计算机中，且被计算机处理的符号的集合是计算机操作的对象的总称是计算机处理的信息的某种特定的符号表示形式数据元素数据的基本单位，也称节点或记录数据项有独立含义的数据最小单位数据结构数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构集合数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图,1.2基本概念和术语,11,数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,1.2基本概念和术语,12,1.2基本概念和术语,13,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,1.2基本概念和术语,14,数据类型高级语言中指数据的取值范围及其上可进行的操作的总称例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef自己定义数据类型,typedefstructintnum;charname20;floatscore;STUDENT;STUDENTstu1,stu2,*p;,1.2基本概念和术语,15,抽象数据类型,是指一个数学模型以及定义在此数学模型上的一组操作例如：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型数据结构+定义在此数据结构上的一组操作=抽象数据类型抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT抽象数据类型名数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义ADT抽象数据类型名,16,数据结构研究的三个方面,17,算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性,1.3算法的描述和算法分析简介,18,算法的五个特性,1有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；2确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；3可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之4有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；5有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,19,问题的定义问题（problem）：需要回答的一般性提问通常含有若干参数问题的描述：对问题参数的一般性描述(input)解满足的条件(objective)问题的实例（instance）:给问题的参数一组赋值后得到的问题的特例,问题的定义,20,实例(instance):C=c1,c2,c3,c4,d(c1,c2)=10,d(c1,c3)=5,d(c1,c4)=9d(c2,c3)=6,d(c2,c4)=9,d(c3,c4)=3,例1旅行售货员问题input：有穷个城市的集合C=c1,c2,cm,以及城市之间的距离正整数d(ci,cj)=d(cj,ci),1ijm.Objective:求经过每个城市恰好一次的路线,使得k1,k2,km是1,2,m的置换且满足,21,非形式定义有限条指令的序列输入个数大于等于0输出个数大于0形式定义对所有的有效输入停机的Turing机算法A解问题P：把问题P的任何实例作为算法A的输入，A能够在有限步停机，并输出该实例的正确的解。,算法的定义,22,算法的例子,给定n个数，设计一个算法把它们递减排序。Program:Pseudo-code:for(inti=1;in+1;i+)fori=1tonfor(intj=i+1;jn+1;j+)forj=i+1tonif(xixj)ifxixjz=xi;change(xi,xj);xi=xj;output:x1,x2,xnxj=z;System.out.println(X);空间复杂度：s(n)=o(f(n),23,算法的评价,算法的评价衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量,24,定义：在给定有效输入后,算法经过有限时间的计算并产生正确的答案,就称算法是正确的.首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；c程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；d程序对于一切合法的输入数据都能得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。,算法的正确性,25,算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；,算法的可读性,26,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,算法的健壮性,27,简单性含义：算法简单，程序结构简单.好处：容易验证正确性便于程序调试简单的算法效率不一定高.要在保证一定效率的前提下力求得到简单的算法.,简单性,28,计量工作量的标准:对于给定问题,该算法所执行的基本运算的次数.基本运算的选择：根据问题选择适当的基本运算问题基本运算在表中查找x比较实矩阵相乘实数乘法排序比较遍历二叉树置指针两种时间复杂性:最坏情况下的复杂性W(n)平均情况下的复杂性A(n),计算时间,29,基本运算的例子：算术运算：加，减，乘，除比较和逻辑运算赋值，包括给指针赋值。Note!与输入的性质有关，例如冒泡排序算法，当输入的数字已经排好序时，时间是O(n),当顺序相反时时间为O(n2)与机器无关。,算法的运行时间,30,算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量1.事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适,31,算法的时间复杂性,与输入的性质无关只与输入的大小有关两种时间复杂性（timecomplexity）最坏情况下的时间复杂性W(n)：对任何一个n，W(n)等于解决大小为n的最坏的实例所用的时间。（不作特殊说明时，一般指这种时间复杂性）例：冒泡排序的时间复杂性为O(n2).平均情况下的复杂性A(n)：对任何一个n，对解决大小为n的实例所用的时间均值。（Hard!需要知道大小为n的实例的概率分布情况）。,32,时间复杂性的渐进估计,时间复杂性一般表示成输入大小（输入规模）的函数我们一般更关心输入规模比较大的时候，时间复杂性的变化趋势这种变化趋势用时间复杂性的渐进估计来表示,33,算法的存储空间需求,算法的空间复杂度S(n)=O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括:1输入数据所占空间;2程序本身所占空间；3辅助变量所占空间。若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,34,时间复杂度：基本操作重复执行的次数的阶数T(n)=o(f(n)空间复杂度：s(n)=o(f(n),例1：NXN矩阵相乘for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=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)。,38,的定义,定义：令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),39,时间复杂性的例子,例子：设一个算法的时间复杂性是：则有，T(n)=O(n2)，T(n)=(n),但是我们不知道T(n)的确切的阶。,40,时间复杂性的性质,设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)=c1f(n)+c2g(n)=(c1+c2)maxf(n),g(n),令c0=c1+c2.得证。T1(n)*T2(n)=O(f(n)g(n)（嵌套或调用）T1(n)*T2(n)=c1f(n)*c2g(n)=c0(f(n)g(n).,41,估计时间复杂性的基本规则,一般的，算法的运行时间是很难估计的，没有一套完整的规则可用。以下的规则仅供参考：基本语句的运行时间为O(1)。如果一个语句中调用了另一个过程，则这个语句的时间为被调用过程的运行时间。语句序列的运行时间为最长的语句的运行时间。If-else-then语句的运行时间为判定条件所需时间加上各种条件下的执行语句的时间的和。循环语句的时间为循环次数乘上循环体的时间加上判定循环结束时间。,42,作业,第2章3、7、11、13、21、22第3章2、3、4、11、12、13第4章1、3、4第5章9、10第6章2、3、12、15、19、26、36、43第7章1、7、9、10、11第9章2、9、19第10章1、12、23,43,有些算法的时间复杂性函数以递推方程的方式给出。例如分而治之（divide-and-conquer）,动态规划等。求解方法展开换元法迭代归纳法尝试法Master定理,递推方程,44,mergesort(L:list;n:integer):list:长度为n的表，以L的排序形式输出，假定n是2的幂。mergesort(L,n)ifn=1thenreturn(L);elsebeginbreakLintohalvesL1andL2,eachoflengthn/2;return(Merge(mergesort(L1,n/2),mergesort(L2,n/2);endif,例子：合并排序算法,45,Merge(L1,L2):把两个排好序的表合成一个新的表。时间复杂性O(|L1|+|L2|).Merge(L1,L2)beginxL11;yL21;Lnull;i0;j0;x=0;While(iL2j)Lx=L2j;j+;x+;elseLx=L1i;i+;x+;endifendwhileif(i|L1|-1)LxLx+L1ielseLxLx+L2jendifend,每次循环，至少一个数字被排进L中，所以有(|L1|+|L2|次循环，每次循环有常数次运算,46,时间复杂性分析,LetT(n)bethetimecomplexityfunctionofmergesort.ThenwecanwriteT(n)inthefollowingrecursiveway:n是2的幂,当不是时可修正，得到同样的结果。,47,展开法求T(n),T(n)=2