《简介与算法时间复杂性.ppt》由会员分享，可在线阅读，更多相关《简介与算法时间复杂性.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构数据结构数据结构数据结构刘士军L山东大学计算机学院1学习本课的目的？学习本课的目的？学习本课的目的？学习本课的目的？用数字计算机解决任何应用问题都离不开数据表示和数据处理。而数据表示和数据处理的核心问题之一就是数据结构及其操作的实现。算法设计提供了使用计算机解决问题的基本思维方式。算法分析是关于算法评价的科学方法。2讲述内容讲述内容讲述内容讲述内容数据结构与算法分析概论 1 1线性结构11栈和队列11数组和广义表1树结构22图结构23搜索24排序253第一章第一章第一章第一章 绪论绪论绪论绪论 41.11.1数据结构讨论的范畴数据结构讨论的范畴数据结构讨论的范畴数据结构讨论的范畴 Ni
2、klaus WirthAlgorithm+Data Structures=Programs程序设计:为计算机处理问题编制一组指令集 算法:处理问题的策略数据结构:问题的数学模型例如:数值计算的程序设计问题 结构静力分析计算 线性代数方程组 全球天气预报 环流模式方程非数值计算的程序设计问题5例例例例1 1 书目自动检索系统书目自动检索系统书目自动检索系统书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表6例例例例2 2 人机对奕问题人机对奕问题人机对奕问题人机对奕问题树.7例例例例3 3多叉路口交通灯管理问题多叉路口交通灯
3、管理问题多叉路口交通灯管理问题多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图8数据结构定义数据结构定义数据结构定义数据结构定义:是一门研是一门研是一门研是一门研究非数值计算的程序设计问题中究非数值计算的程序设计问题中究非数值计算的程序设计问题中究非数值计算的程序设计问题中计算机的操作对象以及它们之间计算机的操作对象以及它们之间计算机的操作对象以及它们之间计算机的操作对象以及它们之间的关系和操作等等的学科的关系和操作等等的学科的关系和操作等等的学科的关系和操作等等的学科9数据所有能被输入到计算机中，且被计算机处理的符号的集合 是计算机操作的对象的总称 是计
4、算机处理的信息的某种特定的符号表示形式数据元素数据的基本单位，也称节点或记录数据项有独立含义的数据最小单位数据结构数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构集合数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图1.21.2基本概念和术语基本概念和术语基本概念和术语基本概念和术语10数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关算法设计 逻辑结构算法实现 存储结构存储结构分为：顺序存储结构借助元素在
5、存储器中的相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系1.21.2基本概念和术语基本概念和术语基本概念和术语基本概念和术语11元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储1.21.2基本概念和术语基本概念和术语基本概念和术语基本概念和术语121536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 134
6、5 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 .14001400 元素元素2 2 1536 1536 .1536 1536 元素元素3 3 1346 1346 链式存储链式存储 h1.21.2基本概念和术语基本概念和术语基本概念和术语基本概念和术语13数据类型高级语言中指数据的取值范围及其上可进行的操作的总称例 C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef 自己定义数据类型typedef struct int num;char na
7、me20;float score;STUDENT;STUDENT stu1,stu2,*p;1.21.2基本概念和术语基本概念和术语基本概念和术语基本概念和术语14抽象数据类型抽象数据类型抽象数据类型抽象数据类型是指一个数学模型以及定义在此数学模型上的一组是指一个数学模型以及定义在此数学模型上的一组操作操作 例例如如：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵矩阵的抽象数据类型抽象数据类型 数据结构+定义在此数据结构上的一组操作=抽象数据类型抽象数据类型的描述方法抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集
8、。ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本操作：基本操作的定义基本操作：基本操作的定义 ADT 抽象数据类型名抽象数据类型名 15 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构研究的三个方面数据结构研究的三个方面数据结构研究的三个方面数据结构研究的三个方面16
9、算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列算法特性1.3 1.3 算法的描述和算法的描述和算法的描述和算法的描述和算法分析简介算法分析简介算法分析简介算法分析简介17算法的五个特性算法的五个特性算法的五个特性算法的五个特性1有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；2确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；3可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现
10、之4有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；5有输出 它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。18问题的定义问题（problem）：需要回答的一般性提问 通常含有若干参数 问题的描述：对问题参数的一般性描述(input)解满足的条件(objective)问题的实例（instance）:给问题的参数一组赋值后得到的问题的特例问题的定义问题的定义问题的定义问题的定义19实例(instance):C=c1,c2,c3,c4,d(c1,c
11、2)=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的置换且满足 20非形式定义 有限条指令的序列 输入个数大于等于0 输出个数大于0形式定义 对所有的有效输入停机的Turing机算法A解问题P：把问题P的任何实例作为算法A的输入，A能够在有限步停机，并输出该实例的正确的解。算法的定义算法的定义算法
12、的定义算法的定义21算法的例子算法的例子算法的例子算法的例子给定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)22算法的评价算法的评价算法的评价算法的评价算法的评价衡量算法优劣的标准正确性(correctness)可读性(read
13、ability)健壮性(robustness)效率与低存储量23定义：在给定有效输入后,算法经过有限时间的计算并产生正确的答案,就称算法是正确的.首先，算法应当满足满足以特定的“规格说明规格说明”方式给出的需求需求。其次，对算法是否“正确正确”的的理解可以有以下四四个层次个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；c程序对于精心选择的、典型、苛刻切带有刁难程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；性的几组输入数据能够得出满足要求的结果；d程序对于一切合法的输入数据都能得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算
14、法是否合格的标准。算法的正确性算法的正确性算法的正确性算法的正确性24算法主要是为了人的阅阅读读与与交交流流，其次才是为计算机执行。因此算法应该易易于于人的理理解解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；算法的可读性算法的可读性算法的可读性算法的可读性25当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。算法的健壮性算法的健壮性算法的健壮性算法的健壮性26简单性 含义：算法简单，程序结构简单.好处：容易验证正确性 便于程序调试 简单
15、的算法效率不一定高.要在保证一定效率的前提下力求得到简单的算法.简单性简单性简单性简单性27 计量工作量的标准:对于给定问题,该算法所执行的基本运算的次数.基本运算的选择：根据问题选择适当的基本运算 问题 基本运算 在表中查找x 比较 实矩阵相乘 实数乘法 排序 比较 遍历二叉树 置指针 两种时间复杂性:最坏情况下的复杂性W(n)平均情况下的复杂性A(n)计算时间计算时间计算时间计算时间28基本运算的例子：算术运算：加，减，乘，除 比较和逻辑运算 赋值，包括给指针赋值。Note!与输入的性质有关，例如冒泡排序算法，当输入的数字已经排好序时，时间是O(n),当顺序相反时时间为O(n2)与机器无关
16、。算法的运行时间算法的运行时间算法的运行时间算法的运行时间29算法效率用依据该算法编制的程序在计算机上执行所消耗的时间来度量1.事后统计利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点：必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 2.事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不合适30算法的时间复杂性算法的
17、时间复杂性算法的时间复杂性算法的时间复杂性与输入的性质无关只与输入的大小有关两种时间复杂性（time complexity）最坏情况下的时间复杂性W(n)：对任何一个n，W(n)等于解决大小为n的最坏的实例所用的时间。（不作特殊说明时，一般指这种时间复杂性）例：冒泡排序的时间复杂性为O(n2).平均情况下的复杂性A(n)：对任何一个n，对解决大小为n的实例所用的时间均值。（Hard!需要知道大小为n的实例的概率分布情况）。31时间复杂性的渐进估计时间复杂性的渐进估计时间复杂性的渐进估计时间复杂性的渐进估计时间复杂性一般表示成输入大小（输入规模）的函数我们一般更关心输入规模比较大的时候，时间复杂
18、性的变化趋势这种变化趋势用时间复杂性的渐进估计来表示32算法的存储空间需求算法的存储空间需求算法的存储空间需求算法的存储空间需求算法的空间复杂度 S(n)=O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括:1输入数据所占空间;2程序本身所占空间；3辅助变量所占空间。若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。33时间复杂度：基本操作重复执行的次数的阶数 T(n)=o(f(n)空间复
19、杂度：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;34例子：假设算法，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)的增长趋势时，当n很大时，c,d的作用可以忽略不计，而g(n)显然比h(n)增长的慢。所以，我们可以称算法A,B,C的运行时间分别
20、是 阶（in the order of)n2logn，n2，n 的。算法的渐进时间复杂性（asymptotic time complexity）：从一个算法的运行时间函数中去掉低阶部分以及最高阶的系数后所得到的函数是这个算法的渐进时间复杂性（asymptotic time complexity）。上面的例子中算法A,B,C的渐进时间复杂性分别是n2logn，n2，n。35函数：logrithmic logknsublinear nclogkn,c0,使得对任意的n=n0，有f(n)+f(n)/g(n)存在，则这个极限不等于就意味着f(n)=O(g(n)。f(n)=O(g(n)说明c.g(n)是
21、 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)。37 的定义的定义的定义的定义定义：令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)
22、=5n3+7n2-2n+13,则可以记做f(n)=(n3).如果一个算法A的时间复杂性是f(n)=(g(n),则称它的时间复杂性是(g(n)。f(n)=O(g(n)g(n)=(f(n)38时间复杂性的例子时间复杂性的例子时间复杂性的例子时间复杂性的例子例子：设一个算法的时间复杂性是：则有，T(n)=O(n2)，T(n)=(n),但是我们不知道T(n)的确切的阶。39时间复杂性的性质时间复杂性的性质时间复杂性的性质时间复杂性的性质设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,c
23、1,使得当 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).40估计时间复杂性的基本规则估计时间复杂性的基本规则估计时间复杂性的基本规则估计时间复杂性的基本规则一般的，算法的运行时间是很难估计的，没有一套完整的规则可用。以下的规则仅供参考：基本语句的运行时间为O(1)。如果一个语句中调用了另一个过程，则这个语句的时间为被调用过程的运行时间。语
24、句序列的运行时间为最长的语句的运行时间。If-else-then语句的运行时间为判定条件所需时间加上各种条件下的执行语句的时间的和。循环语句的时间为循环次数乘上循环体的时间加上判定循环结束时间。41作业作业第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、2342有些算法的时间复杂性函数以递推方程的方式给出。例如分而治之（divide-and-conquer）,动态规划等。求解方法 展开 换元法 迭代归纳法 尝试法 M
25、aster定理递推方程递推方程递推方程递推方程43mergesort(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/2;return(Merge(mergesort(L1,n/2),mergesort(L2,n/2);end if例子：合并排序算法例子：合并排序算法例子：合并排序算法例子：合并排序算法44Merge(L1,L2):把两个排好序的表合成一个新的表
26、。时间复杂性O(|L1|+|L2|).Merge(L1,L2)1.begin2.xL11;yL21;Lnull;3.i0;j0;x=0;4.While(i=|L1|-1and jL2j)Lx=L2j;j+;x+;else Lx=L1i;i+;x+;end ifend whileif(i|L1|-1)LxLx+L1ielse LxLx+L2jend if5.end每次循环，至少一个数字被排进L中，所以有(|L1|+|L2|次循环，每次循环有常数次运算45时间复杂性分析时间复杂性分析时间复杂性分析时间复杂性分析Let T(n)be the time complexity function of m
27、ergesort.Then we can write T(n)in the following recursive way:n 是2的幂,当不是时可修正，得到同样的结果。46展开法求展开法求展开法求展开法求T(n)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)47尝试法求尝试法求尝试法求尝试法求T(n)T(n)考虑到有lgn重循环，每重循环至多要做O(n)次运算，猜测T(n)=f(n)=anlg
28、n.但是当n=1时，f(1)=0C1,不对，猜测f(n)=anlgn+b,其中a,b的值后面决定。当n=1时，要求T(1)=C1=f(1)=b.假定对所有k=T(k),Then,对k=n/2,有T(n/2)=an/2lg(n/2)+b;从而，T(n)=2T(n/2)+C2n =2(an/2lg(n/2)+b)+C2n =anlgn-an+2b+C2n要想证明T(n)=f(n)=anlgnb,只需证明anlgn-an+2b+C2n=C2+b.Let b=C1,a=C2+C1,then,we conclude by induction that for all n=1,T(n)=2 /n is p
29、ower of bExpand49一类递推方程的一般解法一类递推方程的一般解法一类递推方程的一般解法一类递推方程的一般解法Since n=bk,k=logbn,ak=alogbn=nlogba.第一项ak=alogbn=nlogba称作齐次解，称d(n)为驱动函数。若d(n)=0,则齐次解成为精确解。齐次解描述了所有子问题用的时间。第二项 称为特解，他描述产生子问题以及合并子问题的解为原问题的解所用时间。一般不好解特解。50d(n)为乘函数的讨论为乘函数的讨论乘函数f(xy)=f(x)f(y),e.g.,f(n)=na,then f(xy)=(xy)a=xaya=f(x)f(y).若 d(n)
30、为乘函数，则上述问题的特解为：511.若ad(b)，则特解为O(ak),从而整个问题的解等于O(ak)=O(nlogba).减小a,增大b可以改善运行效率。2.若ad(b),则特解为O(d(b)k)=O(nlogbd(b),从而整个问题的解等于O(nlogbd(b)。减小d(n)的增长率，增大b.3.若a=d(b),特解等于4.特解等于齐次解的log bn倍52例子：T(1)=11.T(n)=4T(n/2)+n2.T(n)=4T(n/2)+n23.T(n)=4T(n/2)+n3均有a=4,b=2,齐次解等于O(ak)=O(nlogba)=O(n2).在1中，d(b)=d(2)=24=a,故特解
31、是O(n3)，所以T(n)=O(n3).53例子：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).54例子：T(1)=1T(n)=2T(n/2)+nlogna=b=2,齐次解等于n，而驱动函数不是乘函数，但是可直接对特解求和：55小结小结数据结构的定义及术语数据结构的研究内容算法的定义和特征算法分析递归算法渐进时间复杂度的简单推导56