第二章 算法分析基础.pptVIP

第二章 算法分析基础 2.1 引论 2.2 算法时间复杂性的分析方法 2.3 时间与空间分析 第二章 算法分析基础 2.1 引论 评估算法性能的5条准则 正确性 时间复杂性 占用空间(指令、数据和环境栈空间) 可读性 坚固性(健壮性) 还应该具有灵活性、可重用性和自适应性。 1．正确性 “正确”的含义在通常的用法中有很大的差别，大体可分为以下四个层次： ①算法不含语法错误； ②算法对于几组输入数据能够得出满足规格说明要求的结果； ③算法对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果； ④算法对一切合法的输入数据都能产生满足规格说明要求的结果。 一个算法包括两方面内容：一是解决问题的方法，二是实现这一方法的一系列指令（语句、步骤）。 确认一个算法所用方法和（或）所用公式的正确性，可能需要相关的引理和定理。 证明一系列语句确实做了符合规定的操作。 正确性的验证：测试和证明。 算法正确性证明是很困难的。 Testing (测试) Black Box Methods 黑盒法 侧重测试程序的功能，不考虑程序是如何实现的，即代码结构。 设计测试用例，检查是否能得到预想的结果。 Write Box Methods 白盒法 侧重测试程序的代码结构 Statement Coverage 语句覆盖: 使程序中的每一条语句都至少执行一次。 Decision Coverage 分支覆盖 ：使程序中的每一个分支都至少执行一次。 2．时间复杂性 度量算法的标准： （1）能告诉算法所采用的方法的时间效率； （2）与算法描述语言及设计风格无关； （3）与算法的许多细节无关； （4）足够精确和具有一般性。 基本运算（关键操作） 对所研究问题的基本操作 时间复杂性 一个算法的时间复杂性是指该算法的基本运算次数。 3．占用的存储空间 包括存储算法本身所占用的存储空间（指令空间），算法的输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间（数据空间） 和环境栈空间。 算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。 主要包括变量所占用的存储空间和系统为实现递归所使用的栈空间。 4．可读性 最简单和最直接的算法虽然不是最有效的，但却具有良好的可读性。可读性好的算法使得证明其正确性比较容易，同时便于编写、修改、阅读和调试，所以还是应当强调和不容忽视的。不过对于那些需要经常使用的算法来说，高效率（即尽量减少运行时间和压缩存储空间）比可读性更为重要。 添加注释有利于提高程序的可读性。 5．坚固性 对非法输入具有识别和处理能力。 好的算法还应该具有 可移植性 易用性 安全性 灵活性 可重用性 自适应性 可靠性 6. 在算法正确的前提下最优算法定义如下： 某算法A为最优，当且仅当被研究的解决同一领域同一问题的所有算法集合SA (A∈ SA)中没有一个算法执行的基本运算次数比算法A更少。 证明A是最优的常用策略： A的时间复杂性 = 该问题所需时间复杂性的下确界 2.2 算法时间复杂性的分析方法 问题：算法时间复杂性与那些因素有关？ 输入规模、输入性质、输入出现的频率 定义2.1 设一个领域问题的输入的规模为n，Dn是该领域问题的所有输入的集合，任一输入I?Dn，P(I)是I出现的频率，? P(I)=1，T(I)是算法在输入I下所执行的基本运算次数。该算法的期望复杂性定义为： E(n)= ?{P(I)*T(I)} 该算法的最坏时间复杂性为： W(n)=max{T(I)} 例2.1 A是一个含有n个不同元素的实数数组，给出求A之最大和最小元素的算法。 算法SM(A,n . max,min) SM1[初始化] max←min←A[1]. SM2[比较] FOR I=2 TO n DO // 2 *(n-2+1)次元素的比较（基本运算） ( IF A[I] max THEN max←A[I]. IF A[I] min THEN min←A[I]). ■ 算法SM的时间复杂性为2(n-1)。 例 2.2 实数数组R由n个元素组成，给定一个实数K，试确定K是否是R的元素。 算法F(R, n, K. i) F