算法设计与分析课案.ppt

算法设计与分析 云南大学 廖鸿志 内容 计算模型和计算复杂性的测度 数据结构与递归技术 分治与平衡 排序 动态规划 贪心法 回溯法 分枝限界法 第一章 计算模型和计算复杂性的测度 1.1引言 1.算法的概念 基本上几乎所有的程序都是为了实现某种算法，简言之算法就是处理问题的步骤与逻辑，它是有穷规则的有序集合。算法分为数值算法与非数值算法。 数值算法有：概率统计计算、线性代数计算、数值逼近、数值微分、数值积分、数学规划等。 数值算法是通用的，一般可用解析式表示：而非数值算法只是思想或思路，要根据具体问题按这种思想或思路进行设计。 1.1引言 2 算法的特征 (1)有穷性：算法应该是有穷规则，在有穷步骤后终止。 (2)确定性：算法的任何一步都应该有且仅有一个解释。 (3)能行性：算法应该符合问题的要求，应该在有限时间内完成。 (4)输入与输出：有零个或多个外部量作为算法的输入，算法产生至少一个量作为输出。 1.1引言 程序与算法不同，程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。例如操作系统，它是在无限循环中执行的程序，因而它并不是算法。然而可以将它的各种任务看成一些单独的问题。每一个问题由操作系统的一个子程序通过特定的算法实现。该子程序在得出输出结果后便终止。 1.1引言 3 算法设计与分析的步骤 (1)问题的描述：明确输入与输出。 (2)建立模型：将核心内容模型化，逻辑化。 (3)算法设计与正确性证明：对所有正确的输入都能得到正确的输出（一般需要用谓词逻辑来证明）。 (4)程序实现：用某种程序设计语言来实现。 (5)算法分析：在程序实现之前进行。 1.2计算复杂性的测度 算法的计算复杂性(computational complexity)是衡量算法计算难度的尺度，使用最普遍的标准是一个算法需要耗费的时间和空间。算法所需要的时间或空间，通常是问题规模的函数，这个函数就叫做算法的时间或空间复杂度。在实际中用算法主操作的重复次数来表示算法的时间复杂度。 1.2计算复杂性的测度 问题的规模：也就是该问题所谓的体积，或者说是大小。一个问题的体积可以用一个整数来表示，它是对问题的输入数据或初始数据的多少的一种量度。 定义：如果一个问题的体积是n，解决这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称作这一算法的“时间复杂性”。当输入量n逐渐增大时，T(n)的极限情形就称作算法的“渐近时间复杂性”，类似可定义算法的空间复杂性。但实际上人们主要是研究算法的时间复杂性而很少讨论它们的空间耗费。 1.2计算复杂性的测度 一个算法的复杂性函数的量级是反映算法效能的重要标准。当输入量急剧地增大时，如果设有高效能的算法，单纯依靠提高计算机的速度，有时是很不理想的。 设有五个算法A1，A2，A3，A4，A5，它们的时间复杂性函数如下表所示：表中，一个算法的时间复杂性是它处理完一个大小为n的输入所需要的的单位时间数。 例 例1. 39个景点的全排列 39！=2.04×1046 用每秒处理1亿次（108）逻辑的计算机，需耗时6.5×1022亿年 例2. 下围棋 3361=1.74×10172=5.52×10146亿年 例3. 电梯从1楼到10楼，有多少种可能的方式？ 算法 时间复杂性函数 A1 T1(n)=n A2 T2(n)=nlog2n(nlogn) A3 T3(n)=n2 A4 T4(n)= n3 A5 T5(n) =2? 1.2计算复杂性的测度 算法 时间复杂性 一秒钟内所能处理的最大输入量 一分钟内所能处理的最大输入量 一小时内所能处理的最大输入量 A1 A2 A3 A4 A5 n n㏒2n n2 n3 2? 1000 140 31 10 9 6×104 4893 244 39 15 3.6×106 2.0×105 1897 153 21 1.2计算复杂性的测度 算法 时间复杂性 速度提高前单位时间 里所能处理的数据量 速度提高十倍后单位时 间里所能处理的数据量 速度提高一万倍后单位 时间里所能处理的数据量 A1 A2 A3 A4 A5 n n㏒2n n2 n3 2? S1 S2 S3 S4 S5 10S1 (S2很大)10S2 3.16S3 2.15S4 S5+3.32 10000S1 (㏒2S2≥9 ㏒29000) 9000S2 100S3 21.54S4 S5+13.32 1.2计算复杂性的测度 1.2计算复杂性的测度 现有问题可以分为以下三类： 无法写出算法的问题； 有以多项式为界的算法存在的问题，即Ｐ类问题； 介于前两类问题之间的问题，“ＮＰ——完全”问题。 1.3随机存取模型 自学 第二章 数据结构和递归技术 表、树、图 表：a1,a2,a3,