第二章 算法分析基础ppt课件.ppt

《第二章 算法分析基础ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章算法分析基础2.1引论2.2算法时间复杂性的分析方法2.3时间与空间分析第二章算法分析基础2.1引论评估算法性能的5条准则正确性时间复杂性占用空间(指令、数据和环境栈空间)可读性坚固性(健壮性)还应该具有灵活性、可重用性和自适应性。1．正确性“正确”的含义在通常的用法中有很大的差别，大体可分为以下四个层次：①算法不含语法错误；②算法对于几组输入数据能够得出满足规格说明要求的结果；③算法对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；④算法对一切合法的输入数据都能产生满足规格说明要求的结果。√一个算法包括两方面内容：一是解决问题的方法，

2、二是实现这一方法的一系列指令（语句、步骤）。确认一个算法所用方法和（或）所用公式的正确性，可能需要相关的引理和定理。证明一系列语句确实做了符合规定的操作。正确性的验证：测试和证明。算法正确性证明是很困难的。Testing(测试)BlackBoxMethods黑盒法侧重测试程序的功能，不考虑程序是如何实现的，即代码结构。设计测试用例，检查是否能得到预想的结果。WriteBoxMethods白盒法侧重测试程序的代码结构StatementCoverage语句覆盖:使程序中的每一条语句都至少执行一次。DecisionCoverage分支覆盖：使程序中的每一个分支都至少执行一次。

3、2．时间复杂性度量算法的标准：（1）能告诉算法所采用的方法的时间效率；（2）与算法描述语言及设计风格无关；（3）与算法的许多细节无关；（4）足够精确和具有一般性。基本运算（关键操作）对所研究问题的基本操作时间复杂性一个算法的时间复杂性是指该算法的基本运算次数。3．占用的存储空间包括存储算法本身所占用的存储空间（指令空间），算法的输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间（数据空间）和环境栈空间。算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。它包括局部变量所占用的存储空间和系统为了实现递归所使用的堆栈这两个部分。算法的空间复杂性一般

4、以数量级的形式给出。4．可读性最简单和最直接的算法虽然不是最有效的，但却具有良好的可读性。可读性好的算法使得证明其正确性比较容易，同时便于编写、修改、阅读和调试，所以还是应当强调和不容忽视的。不过对于那些需要经常使用的算法来说，高效率（即尽量减少运行时间和压缩存储空间）比可读性更为重要。5．坚固性好的算法还应该具有可移植性易用性安全性灵活性可重用性自适应性可靠性6.最优算法定义如下：某算法A为最优，当且仅当被研究的解决同一领域同一问题的所有算法集合SA(A∈SA)中没有一个算法执行的基本运算次数比算法A更少。第二章算法分析基础2.2算法时间复杂性的分析方法问题：决定程序

5、（算法）运行时间的因素有哪些？基本运算次数平均运算次数加权平均定义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.1A是一个含有n个不同元素的实数数组，给出求A之最大和最小元素的算法。算法SM(A,n.max,min)SM1[初始化]max←min←A[1].SM2[比较]FORI=2TOnDO//2*(n

6、-2+1)次元素的比较（基本运算）(IFA[I]>maxTHENmax←A[I].IFA[I]

7、q设q（0≤q≤1）表示K在R中的概率，q通过计算我们可以得到算法F的期望复杂性为E(n)=∑{P(I)*T(I)}=(q/n)*1+(q/n)*2+…+(q/n)*n+(1-q)*nn项1项=1/2(n+1)q+(1-q)n如果已知K在R中，即q=1，则有E(n)=1/2(n+1)由算法F可以很容易看出该算法的最坏复杂性为W(n)=max{T(i)

8、1≤i≤n+1}=n例2.3算法SM的改进算法BS。算法BS（A，i，j.fmax，fmin）//在数组A的第i个元素到第j个元素之间寻找最大和最//小元素，已知ij。BS1[递归出口]I