第5章 算法与复杂性.ppt

《第5章 算法与复杂性.ppt》由会员分享，可在线阅读，更多相关《第5章 算法与复杂性.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5 5章章 算法与复杂性算法与复杂性2计算机科学导论计算机科学导论学习目标学习目标了解算法的概念和特性、算法的描述工具、评价、算法设了解算法的概念和特性、算法的描述工具、评价、算法设计策略、分布式算法、可计算性理论基础、计策略、分布式算法、可计算性理论基础、NPNP问题、自动问题、自动机理论、加密算法、几何算法、并行算法等。机理论、加密算法、几何算法、并行算法等。掌握几种经典算法的基本思想。掌握几种经典算法的基本思想。一个好的算法是程序设计的关键，本章首先介绍算法的基一个好的算法是程序设计的关键，本章首先介绍算法的基本知识、常用算法及算法评价的基础知识，然后介绍几种本知识、常用算法及算法评

2、价的基础知识，然后介绍几种常用的算法，为今后进一步学习算法及其复杂性打好基础。常用的算法，为今后进一步学习算法及其复杂性打好基础。第第5 5章章 算法与复杂性算法与复杂性3计算机科学导论计算机科学导论5.1 算法分析基础算法分析基础 5.1.1 算法的概念算法的概念算法（算法（Algorithm）是一组明确的、可以执行步骤）是一组明确的、可以执行步骤的有序集合，在有限的时间内终止并产生结果。的有序集合，在有限的时间内终止并产生结果。算法和数据结构之间存在密切联系，数据结构是算法和数据结构之间存在密切联系，数据结构是算法的基础，数据结构不同，通常采用的算法也算法的基础，数据结构不同，通常采用的算

3、法也不同。不同。4计算机科学导论计算机科学导论5.1.2 算法的特性算法的特性算法反映了求解问题的方法和步骤，不同的问题算法反映了求解问题的方法和步骤，不同的问题需要用不同的算法来解决，同一个问题也可能有需要用不同的算法来解决，同一个问题也可能有多种不同的算法。一个算法必须具有以下特性：多种不同的算法。一个算法必须具有以下特性：u1.有穷性有穷性(可终止性可终止性)一个算法必须在有限的操作步骤内以及合理的时一个算法必须在有限的操作步骤内以及合理的时间内执行完成。间内执行完成。u2.确定性确定性算法中的每一个操作步骤都必须有明确的含义，算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。

4、不允许存在二义性。5计算机科学导论计算机科学导论u3.有效性有效性(可行性可行性)包括以下两个方面：包括以下两个方面：算法中每一个步骤必须能够实现，如算法中每一个步骤必须能够实现，如在算法中不允许出现分母为在算法中不允许出现分母为0的情况。的情况。算法执行的结果要能够达到预期的目算法执行的结果要能够达到预期的目的，实现预定的功能。的，实现预定的功能。u4.输入数据与输出数据的要求输入数据与输出数据的要求一个算法应该有一个算法应该有0个或多个输入数据、有个或多个输入数据、有1个或多个输出数据。个或多个输出数据。5.1.2 算法的特性算法的特性6计算机科学导论计算机科学导论5.2 常用算法介绍常用

5、算法介绍1.递归算法递归算法如果一个过程（函数，子程序）直接或间接地调如果一个过程（函数，子程序）直接或间接地调用它本身，则称该过程是递归的。用它本身，则称该过程是递归的。7计算机科学导论计算机科学导论5.2 常用算法介绍常用算法介绍2.迭代算法迭代算法迭代是指重复执行一组指令或操作步骤，在每次迭代是指重复执行一组指令或操作步骤，在每次执行这组指令时，都在原来的解的基础上推出一执行这组指令时，都在原来的解的基础上推出一个新解，新的解比原来的解值更加接近真实的解。个新解，新的解比原来的解值更加接近真实的解。这个过程不断重复，直到最后计算得到的解与真这个过程不断重复，直到最后计算得到的解与真实的解

6、的误差满足实践的要求。实的解的误差满足实践的要求。8计算机科学导论计算机科学导论5.2 常用算法介绍常用算法介绍3.穷举算法穷举算法穷举算法亦称枚举算法，该算法首先根据问题的穷举算法亦称枚举算法，该算法首先根据问题的部分条件确定问题的大致范围，然后在此范围内部分条件确定问题的大致范围，然后在此范围内对所有可能的情况逐一进行验证，直到全部情况对所有可能的情况逐一进行验证，直到全部情况验证完毕。验证完毕。若某个情况使验证结果符合题目的条件，则为本若某个情况使验证结果符合题目的条件，则为本题的一个答案，若全部情况验证完成后均不符合题的一个答案，若全部情况验证完成后均不符合题目条件，则判定该问题无解。

7、题目条件，则判定该问题无解。9计算机科学导论计算机科学导论5.2 常用算法介绍常用算法介绍4.贪婪算法贪婪算法贪婪算法也称贪心算法，是通过一系列的选择，贪婪算法也称贪心算法，是通过一系列的选择，最终得到问题的解。算法做出的每一个选择都是最终得到问题的解。算法做出的每一个选择都是在当前状态下的最优选择。在当前状态下的最优选择。10计算机科学导论计算机科学导论5.3 算法描述工具算法描述工具算法是要通过程序才能加以实现的。常用的算法描述方式算法是要通过程序才能加以实现的。常用的算法描述方式:u1.自然语言自然语言自然语言就是人们日常使用的语言，可以是中文、英文等。自然语言就是人们日常使用的语言，可

8、以是中文、英文等。例如，求例如，求3个数中最大者的问题，可以描述为：个数中最大者的问题，可以描述为：比较前两个数。比较前两个数。将将中较大的数与第三个数进行比较。中较大的数与第三个数进行比较。步骤步骤中较大的数即为所求。中较大的数即为所求。11计算机科学导论计算机科学导论u2.流程图流程图流程图是用规定的一组图形符号、流程线和文字说明来描述算法流程图是用规定的一组图形符号、流程线和文字说明来描述算法的一种表示方法。的一种表示方法。(1)顺序结构。程序执行完顺序结构。程序执行完A语句后接着执行语句后接着执行B语句，如图所示。语句，如图所示。(2)选择结构。当条件选择结构。当条件P成立时，则执行成

9、立时，则执行A语句，否则执行语句，否则执行B语句，语句，如图所示。如图所示。P成立AB不成立5.3 算法描述工具算法描述工具12计算机科学导论计算机科学导论(3)当型循环结构。当条件当型循环结构。当条件P成立时，则成立时，则循环执行循环执行A语句，如图所示语句，如图所示(4)直到型循环结构。循环执行直到型循环结构。循环执行A语句，语句，直到条件直到条件P1成立为止，如图所示。成立为止，如图所示。5.3 算法描述工具算法描述工具13计算机科学导论计算机科学导论u3.伪代码伪代码伪代码是用一种介于自然语言与计算机语言之间的文字和符伪代码是用一种介于自然语言与计算机语言之间的文字和符号来描述算法，它

10、比计算机语言形式灵活、格式紧凑，没有号来描述算法，它比计算机语言形式灵活、格式紧凑，没有严格的语法。严格的语法。例如，求两个数的较大者，用伪代码描述算法如下：例如，求两个数的较大者，用伪代码描述算法如下：Find the bigger Input:two number s:a,b 1.if(the first number a is greater than or equal to the second number b)then 1.1 return a else 1.2 return b end if end5.3 算法描述工具算法描述工具14计算机科学导论计算机科学导论5.4 算法的评价

11、算法的评价u对于一个算法的评价，通常要从正确性、可理解性、对于一个算法的评价，通常要从正确性、可理解性、健壮性、时间复杂度健壮性、时间复杂度(Time Complexity)及空间复杂度及空间复杂度(Space Complexity)等多个方面加以衡量。等多个方面加以衡量。1算法的时间复杂度算法的时间复杂度时间复杂度是度量时间的复杂性，即算法的时间效率的指标。时间复杂度是度量时间的复杂性，即算法的时间效率的指标。2算法的空间复杂度算法的空间复杂度 算法的空间复杂度是度量空间的复杂性，即执行算法的程序在计算法的空间复杂度是度量空间的复杂性，即执行算法的程序在计算机中运行时所占用空间的大小。算机中

12、运行时所占用空间的大小。15计算机科学导论计算机科学导论5.5 算法设计策略算法设计策略一个优秀的算法可以运行在比较慢的计算机上，但一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。算法设计往往处于核心地位。要想充分理解算法并有效地应用于实际问题中，关要想充分理解算法并有效地应用于实际问题中，关键是对算法的分析。通常可以利用实验对比分析、键是对算法的分析。通常可以利用实验对比分析、数学方法来分析算

13、法。数学方法来分析算法。16计算机科学导论计算机科学导论5.6 分布式算法分布式算法分布式算法是用于解决多个互连处理器运行问题的算法。分布式算法是用于解决多个互连处理器运行问题的算法。分布式算法的各部分并发和独立地运行，每一部分只承载分布式算法的各部分并发和独立地运行，每一部分只承载有限的信息。即使处理器和通信信道以不同的速度运作，有限的信息。即使处理器和通信信道以不同的速度运作，或即使某些构件出了故障，这些算法仍然能工作正常。或即使某些构件出了故障，这些算法仍然能工作正常。应用：如今天的电话系统、航班订票系统、银行系统、全应用：如今天的电话系统、航班订票系统、银行系统、全球信息系统、天气预报

14、系统以及飞机和核电站控制系统都球信息系统、天气预报系统以及飞机和核电站控制系统都依赖于分布式算法。依赖于分布式算法。17计算机科学导论计算机科学导论5.7 可计算性理论基础可计算性理论基础研究计算的可行性和函数算法的理论，又称算法研究计算的可行性和函数算法的理论，又称算法理论，是算法设计与分析的基础，也是计算机科理论，是算法设计与分析的基础，也是计算机科学的理论基础。可计算性是函数的一个特性。学的理论基础。可计算性是函数的一个特性。18计算机科学导论计算机科学导论5.8 NP问题问题uNP(Non-deterministic Polynomial)问题是非确定问题是非确定性多项式问题，是指算法

15、无法直接计算出结果，性多项式问题，是指算法无法直接计算出结果，只能通过进行一些有选择的只能通过进行一些有选择的“猜算猜算”来得到结果。来得到结果。uNP问题的研究结果有两种可能：问题的研究结果有两种可能：一种是找到了求解问题的算法；一种是找到了求解问题的算法；另一种就是求解问题的算法是不存在的，那么就另一种就是求解问题的算法是不存在的，那么就要从数学理论上证明它为什么不存在。要从数学理论上证明它为什么不存在。19计算机科学导论计算机科学导论5.9 自动机理论自动机理论u数理语言学中研究抽象自动机的理论。抽象自动机是一种数理语言学中研究抽象自动机的理论。抽象自动机是一种能够识别语言的抽象装置，它

16、不是具有物理实体的机器，能够识别语言的抽象装置，它不是具有物理实体的机器，而是表示计算机运算方式的抽象的逻辑关系系统。而是表示计算机运算方式的抽象的逻辑关系系统。u美国语言学家美国语言学家N.Chomsky等人建立了形式文法和自动机之等人建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着以下间的联系，证明语言的形式文法与自动机之间存在着以下的对应关系：的对应关系：若某一语言能用图灵机来识别，则它就能用若某一语言能用图灵机来识别，则它就能用O形文法生形文法生成；反之亦然。成；反之亦然。若某一语言能用线性有界自动机来识别，则它就能用上若某一语言能用线性有界自动机来识别，则它就能

17、用上下文敏感文法生成；反之亦然。下文敏感文法生成；反之亦然。20计算机科学导论计算机科学导论 若某一语言能用后进先出自动机来识别，则若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成；反之亦然。它就能用上下文自由文法生成；反之亦然。若某一语言能用有限自动机来识别，则它就若某一语言能用有限自动机来识别，则它就能用有限状态文法生成；反之亦然。能用有限状态文法生成；反之亦然。u这种关于形式文法与自动机的关系，反映了语这种关于形式文法与自动机的关系，反映了语言的生成过程与识别过程的内在联系，它已成言的生成过程与识别过程的内在联系，它已成为计算机科学的基石之一。为计算机科学的基石之一。5.

18、9 自动机理论自动机理论21计算机科学导论计算机科学导论5.10 加密算法加密算法数据加密的基本过程就是对原来为明文的文件或数据按数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码，通常某种算法进行处理，使其成为不可读的一段代码，通常称为称为“密文密文”该过程的逆过程为解密，即将该编码信息转化为其原来该过程的逆过程为解密，即将该编码信息转化为其原来数据的过程。数据的过程。加密技术通常分为加密技术通常分为“对称式对称式”和和“非对称式非对称式”两大类。两大类。对称式加密就是加密和解密使用同一个密钥，对称式加密就是加密和解密使用同一个密钥，非对称式加密就是加

19、密和解密所使用的不是同一个密钥，非对称式加密就是加密和解密所使用的不是同一个密钥，通常有两个密钥，称为通常有两个密钥，称为“公钥公钥”和和“私钥私钥”，它们两个，它们两个必须配对使用，否则不能打开加密文件。必须配对使用，否则不能打开加密文件。22计算机科学导论计算机科学导论u常见加密算法有如下：常见加密算法有如下：(1)DES(Data Encryption Standard)：数据加密标准，速度较快，：数据加密标准，速度较快，适用于加密大量数据的场合。适用于加密大量数据的场合。(2)3DES(Triple DES)：是基于：是基于DES，对一块数据用，对一块数据用3个不同的密个不同的密钥进行

20、钥进行3次加密，强度更高；次加密，强度更高；(3)RC2和和RC4：用变长密钥对大量数据进行加密，比：用变长密钥对大量数据进行加密，比DES快。快。(4)IDEA(International Data Encryption Algorithm)国际数据加国际数据加密算法，使用密算法，使用128位密钥提供非常强的安全性。位密钥提供非常强的安全性。(5)RSA：由：由RSA公司发明，是一个支持变长密钥的公共密钥算法，公司发明，是一个支持变长密钥的公共密钥算法，需要加密的文件块的长度也是可变的。需要加密的文件块的长度也是可变的。(6)DSA(Digital Signature Algorithm)：

21、数字签名算法，是一种：数字签名算法，是一种标准的标准的DSS(数字签名标准数字签名标准)。5.10 加密算法加密算法23计算机科学导论计算机科学导论5.11 几何算法几何算法几何算法的内容不属于欧几里德的几何证明公理化范畴，几何算法的内容不属于欧几里德的几何证明公理化范畴，而是属于欧几里德几何构造，即由算法和复杂性构成。而是属于欧几里德几何构造，即由算法和复杂性构成。在一个几何构造过程中，执行原始运算的总次数称为该过在一个几何构造过程中，执行原始运算的总次数称为该过程的复杂性度量，这个概念对应于算法的时间复杂度。同程的复杂性度量，这个概念对应于算法的时间复杂度。同样，还有对应于算法的空间复杂度

22、的概念。这是欧几里德样，还有对应于算法的空间复杂度的概念。这是欧几里德几何构造过程复杂性的定量测度。几何构造过程复杂性的定量测度。24计算机科学导论计算机科学导论5.12 并行算法并行算法并行算法是在给定并行模型下的一种具体、明确的并行算法是在给定并行模型下的一种具体、明确的计算方法和步骤，其有不同的分类方法。计算方法和步骤，其有不同的分类方法。根据并行计算任务的大小分类，可以分为粗粒度并根据并行计算任务的大小分类，可以分为粗粒度并行算法、中粒度并行算法和细粒度并行算法行算法、中粒度并行算法和细粒度并行算法3类。类。根据并行计算的基本对象可分为数值并行计算和非根据并行计算的基本对象可分为数值并

23、行计算和非数值并行计算。数值并行计算。根据并行计算进程间的依赖关系，可以分为同步并根据并行计算进程间的依赖关系，可以分为同步并行算法和异步并行算法。行算法和异步并行算法。一个高效的并行算法设计过程比较复杂。一般编程一个高效的并行算法设计过程比较复杂。一般编程设计过程可以分为任务划分、通信分析、任务组合设计过程可以分为任务划分、通信分析、任务组合和处理器映射和处理器映射4步。步。25计算机科学导论计算机科学导论5.13 本章小结本章小结算法是计算机科学的重要组成部分，作为计算机科学中非正算法是计算机科学的重要组成部分，作为计算机科学中非正式的定义，算法是按部就班解决某个问题的方法。具体到计式的定

24、义，算法是按部就班解决某个问题的方法。具体到计算机科学中，算法是有限的、有序的、有效的计算机指令集算机科学中，算法是有限的、有序的、有效的计算机指令集合。合。算法有输入、输出，虽然步骤有限，但每一步都是有效的。算法有输入、输出，虽然步骤有限，但每一步都是有效的。算法的迭代结构有顺序搜索法、循环控制和插入排序算法。算法的迭代结构有顺序搜索法、循环控制和插入排序算法。算法可以用算法可以用3种方式表示，即自然语言、流程图和伪代码。种方式表示，即自然语言、流程图和伪代码。自然语言有定义明确的语言基本块集合；流程图是算法图形自然语言有定义明确的语言基本块集合；流程图是算法图形化的表示；伪代码是算法的符号和结构化的原语表示。对于化的表示；伪代码是算法的符号和结构化的原语表示。对于一个算法的评价，通常要从正确性、可理解性、健壮性、时一个算法的评价，通常要从正确性、可理解性、健壮性、时间复杂度及空间复杂度等多个方面加以衡量。间复杂度及空间复杂度等多个方面加以衡量。