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

《简介与算法时间复杂性.ppt》由会员分享，可在线阅读，更多相关《简介与算法时间复杂性.ppt（56页珍藏版）》请在三一办公上搜索。

1、数据结构,刘士军L山东大学计算机学院,2,学习本课的目的？,用数字计算机解决任何应用问题都离不开数据表示和数据处理。而数据表示和数据处理的核心问题之一就是数据结构及其操作的实现。算法设计提供了使用计算机解决问题的基本思维方式。算法分析是关于算法评价的科学方法。,3,讲述内容,数据结构与算法分析概论 1 1线性结构11栈和队列11数组和广义表1树结构22图结构23搜索24排序25,第一章 绪论,5,1.1数据结构讨论的范畴,Niklaus WirthAlgorithm+Data Structures=Programs程序设计:为计算机处理问题编制一组指令集 算法:处理问题的策略数据结构:问题的数

2、学模型例如:数值计算的程序设计问题 结构静力分析计算 线性代数方程组 全球天气预报 环流模式方程非数值计算的程序设计问题,6,例1 书目自动检索系统,书目文件,7,例2 人机对奕问题,8,例3多叉路口交通灯管理问题,9,数据结构定义:是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科,10,数据所有能被输入到计算机中，且被计算机处理的符号的集合 是计算机操作的对象的总称 是计算机处理的信息的某种特定的符号表示形式数据元素数据的基本单位，也称节点或记录数据项有独立含义的数据最小单位数据结构数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据

3、结构集合数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图,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等基本数据类型，数组、结构体、共用体、

4、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef 自己定义数据类型,typedef struct int num;char name20;float score;STUDENT;STUDENT stu1,stu2,*p;,1.2基本概念和术语,15,抽象数据类型,是指一个数学模型以及定义在此数学模型上的一组操作 例如：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型 数据结构+定义在此数据结构上的一组操作=抽象数据类型抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT

5、抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,16,数据结构研究的三个方面,17,算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性,1.3 算法的描述和算法分析简介,18,算法的五个特性,1有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；2确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；3可行性 算法中的所有操作都必须足够基本，都

6、可以通过已经实现的基本操作运算有限次实现之4有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；5有输出 它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,19,问题的定义问题（problem）：需要回答的一般性提问 通常含有若干参数 问题的描述：对问题参数的一般性描述(input)解满足的条件(objective)问题的实例（instance）:给问题的参数一组赋值后得到的问题的特例,问题的定义,20,实例(instance):C=c1,c2,c3

7、,c4,d(c1,c2)=10,d(c1,c3)=5,d(c1,c4)=9 d(c2,c3)=6,d(c2,c4)=9,d(c3,c4)=3,例1 旅行售货员问题input：有穷个城市的集合C=c1,c2,cm,以及城市之间的距离 正整数d(ci,cj)=d(cj,ci),1 i j m.Objective:求经过每个城市恰好一次的路线,使得k1,k2,km是1,2,m的置换且满足,21,非形式定义 有限条指令的序列 输入个数大于等于0 输出个数大于0形式定义 对所有的有效输入停机的Turing机算法A解问题P：把问题P的任何实例作为算法A的输入，A能够在有限步停机，并输出该实例的正确的解。,

8、算法的定义,22,算法的例子,给定n个数，设计一个算法把它们递减排序。Program:Pseudo-code:for(int i=1;in+1;i+)for i=1 to nfor(int j=i+1;jn+1;j+)for j=i+1 to n if(xixj)if xixj z=xi;change(xi,xj);xi=xj;output:x1,x2,xn xj=z;System.out.println(X);空间复杂度：s(n)=o(f(n),23,算法的评价,算法的评价衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率与低

9、存储量,24,定义：在给定有效输入后,算法经过有限时间的计算并产生正确的答案,就称算法是正确的.首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；c程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；d程序对于一切合法的输入数据都能得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。,算法的正确性,25,算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而

10、难以调试；,算法的可读性,26,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,算法的健壮性,27,简单性 含义：算法简单，程序结构简单.好处：容易验证正确性 便于程序调试 简单的算法效率不一定高.要在保证一定效率的前提下力求得到简单的算法.,简单性,28,计量工作量的标准:对于给定问题,该算法所执行的基本运算的次数.基本运算的选择：根据问题选择适当的基本运算 问题 基本运算 在表中查找x 比较 实矩阵相乘 实数乘法 排序 比较 遍历二叉树

11、置指针 两种时间复杂性:最坏情况下的复杂性W(n)平均情况下的复杂性A(n),计算时间,29,基本运算的例子：算术运算：加，减，乘，除 比较和逻辑运算 赋值，包括给指针赋值。Note!与输入的性质有关，例如冒泡排序算法，当输入的数字已经排好序时，时间是O(n),当顺序相反时时间为O(n2)与机器无关。,算法的运行时间,30,算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量1.事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 2.事前分析估计一个高级语言程

12、序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适,31,算法的时间复杂性,与输入的性质无关只与输入的大小有关两种时间复杂性（time complexity）最坏情况下的时间复杂性W(n)：对任何一个n，W(n)等于解决大小为n的最坏的实例所用的时间。（不作特殊说明时，一般指这种时间复杂性）例：冒泡排序的时间复杂性为O(n2).平均情况下的复杂性A(n)：对任何一个n，对解决大小为n的实例所用的时间均值。（H

13、ard!需要知道大小为n的实例的概率分布情况）。,32,时间复杂性的渐进估计,时间复杂性一般表示成输入大小（输入规模）的函数我们一般更关心输入规模比较大的时候，时间复杂性的变化趋势这种变化趋势用时间复杂性的渐进估计来表示,33,算法的存储空间需求,算法的空间复杂度 S(n)=O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括:1输入数据所占空间;2程序本身所占空间；3辅助变量所占空间。若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需

14、存储量依赖于特定的输入，则通常按最坏情况考虑。,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=n;k+)cij=cij+aik*bkj;,35,例子：假设算法，C 的运行时间分别为 f(n)=n2logn+10n2+n g(n)=cn2 h(n)=dn则当输入长度n很大时，f(n)中的最高阶部分 n2logn 决定着f(n)的值，而10n2+n可以忽略不计；如果B,C 是解决同一问题的两个不同的算法，当比较g(n)与h(n)

15、的增长趋势时，当n很大时，c,d的作用可以忽略不计，而g(n)显然比h(n)增长的慢。所以，我们可以称算法A,B,C的运行时间分别是 阶（in the order of)n2logn，n2，n 的。算法的渐进时间复杂性（asymptotic time complexity）：从一个算法的运行时间函数中去掉低阶部分以及最高阶的系数后所得到的函数是这个算法的渐进时间复杂性（asymptotic time complexity）。上面的例子中算法A,B,C的渐进时间复杂性分别是n2logn，n2，n。,36,函数：logrithmic logknsublinear nclogkn,c1 linear

16、 cnsubquadratic nlogn,n1.5quadratic n2 cubic n3 exponential 2n,3n,37,O的定义,定义：令f(n)与g(n)是定义在自然数域上的非副实函数，那么称f(n)=O(g(n)，如果存在一个自然数n0 和一个常数c0,使得对任意的n=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

17、(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,

18、时间复杂性的例子,例子：设一个算法的时间复杂性是：则有，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)

19、*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

20、、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)if n=1 then return(L);else begin break L into halves L1 and L2,each of length n/

21、2;return(Merge(mergesort(L1,n/2),mergesort(L2,n/2);end if,例子：合并排序算法,45,Merge(L1,L2):把两个排好序的表合成一个新的表。时间复杂性O(|L1|+|L2|).Merge(L1,L2)beginxL11;yL21;Lnull;i0;j0;x=0;While(iL2j)Lx=L2j;j+;x+;else Lx=L1i;i+;x+;end ifend whileif(i|L1|-1)LxLx+L1ielse LxLx+L2jend ifend,每次循环，至少一个数字被排进L中，所以有(|L1|+|L2|次循环，每次循环有常

22、数次运算,46,时间复杂性分析,Let T(n)be the time complexity function of mergesort.Then we can write T(n)in the following recursive way:n 是2的幂,当不是时可修正，得到同样的结果。,47,展开法求T(n),T(n)=2T(n/2)+C 2n=2*(2T(n/4)+C 2n/2)+C 2n=4T(n/4)+2C 2n=2kT(n/2k)+kC 2n(If n=2k,)=2k T(1)+kC2n=nC1+C 2 nlgn=O(nlgn),48,尝试法求T(n),考虑到有lgn重循环，每重循

23、环至多要做O(n)次运算，猜测T(n)=T(k),Then,对k=n/2,有T(n/2)=C2+b.Let b=C1,a=C2+C1,then,we conclude by induction that for all n=1,T(n)=f(n)=(C1+C2)nlgn+C1,that is T(n)=O(nlgn).,49,一类递推方程的一般解法,T(1)=1T(n)=aT(n/b)+d(n),n=2/n is power of bExpand,50,一类递推方程的一般解法,Since n=bk,k=logbn,ak=alogbn=nlogba.第一项ak=alogbn=nlogba称作齐次

24、解，称d(n)为驱动函数。若d(n)=0,则齐次解成为精确解。齐次解描述了所有子问题用的时间。第二项 称为特解，他描述产生子问题以及合并子问题的解为原问题的解所用时间。一般不好解特解。,51,d(n)为乘函数的讨论,乘函数f(xy)=f(x)f(y),e.g.,f(n)=na,then f(xy)=(xy)a=xaya=f(x)f(y).若 d(n)为乘函数，则上述问题的特解为：,52,若ad(b)，则特解为O(ak),从而整个问题的解等于O(ak)=O(nlogba).减小a,增大b可以改善运行效率。若ad(b),则特解为O(d(b)k)=O(nlogbd(b),从而整个问题的解等于O(nl

25、ogbd(b)。减小d(n)的增长率，增大b.若a=d(b),特解等于特解等于齐次解的log bn倍,53,例子：T(1)=1T(n)=4T(n/2)+nT(n)=4T(n/2)+n2T(n)=4T(n/2)+n3均有a=4,b=2,齐次解等于O(ak)=O(nlogba)=O(n2).在1中，d(b)=d(2)=24=a,故特解是O(n3)，所以T(n)=O(n3).,54,例子：T(1)=1T(n)=3T(n/2)+2n1.5驱动函数不是乘函数。令U(n)=1/2*T(n),则，U(1)=1U(n)=3U(n/2)+n1.5特解1/2*alogn=O(nloga)=O(n1.59);a=3,b=2,d(b)=b1.5=2.82a,故特解等于齐次解，从而U(n)=O(n1.59);T(n)=2U(n)=O(n1.59).,55,例子：T(1)=1T(n)=2T(n/2)+nlogna=b=2,齐次解等于n，而驱动函数不是乘函数，但是可直接对特解求和：,56,小结,数据结构的定义及术语数据结构的研究内容算法的定义和特征算法分析递归算法渐进时间复杂度的简单推导,