算法设计与分析-第2章-算法分析基础.pptx

《算法设计与分析-第2章-算法分析基础.pptx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章算法分析基础2.2算法的渐进分析2.3最好、最坏和平均情况2.4非递归算法的分析2.5递归算法的分析2.1算法分析的基本概念2.1算法分析的基本概念一、算法分析（AlgorithmAnalysis）：对算法所需要的两种计算机资源——时间和空间进行估算时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）二、算法分析的目的：设计算法——设计出复杂性尽可能低的算法选择算法——在多种算法中选择其中复杂性最低者三、算法分析的两个阶段1、事前分析—求出该算法的一个时间限界函数。2、事后测试—收集此算法的执行时间和实际占用空间的统计资料。2.1算法分析

2、的基本概念2.2算法的渐进分析一、相关概念算法的渐进分析是一种事前估算的方法，是指忽略具体机器、编程语言和编译器的影响，只关注在输入规模增大时算法运行时间的增长趋势。渐进时间复杂性当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此，可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。确定一个算法时间的数量级是十分重要的，它在本质上反映了一个算法所需要的计算时间。语句频度：语句执行的次数算法的语句频度f(n)：f(n)=∑(语句(i)的执行次数）算法中基本操作重复执行的次数之和算法

3、的执行时间：是所有语句的执行时间之和T（n）=∑(语句(i)的执行次数×语句的执行时间)(假设每条语句执行的时间相等)渐进时间复杂度表示：随着问题规模n的增长，算法执行时间的增长率和算法的语句频度f（n）的增长率相同，则可记作：T（n）=O（f（n））称T（n）为算法的(渐近)时间复杂度2.2算法的渐进分析2.2算法的渐进分析二、表示方法1.大O符号--运行时间的上界定义1.1若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c×f(n)大O符号描述增长率的上限，表示T(n)

4、的增长最多像f(n)增长的那样快当说一个算法具有O(f(n))的计算时间时，指的是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于f(n)的一个常数倍。所以f(n)是计算时间T(n)的一个上界函数，T(n)的数量级就是f(n)典型的增长阶:O(1),O(lgn),O(n),O(nlgn),O(n2),O(n3),O(2n),O(n!)2.2算法的渐进分析算术运算：O(f(n))+O(g(n))=O(max{f(n),g(n)})；O(f(m))+O(g(n))=O(f(m)+g(n))；O(f(n))*O(g(n))=O(f(n)*g(n))；O(cf(

5、n))=O(f(n))；若g(n)=O(f(n))则O(f(n))+O(g(n))=O(f(n))。若T(n)是关于n的k阶多项式，那么T(n)=O(nk)2.2算法的渐进分析证明：取n0=1,当n>=n0时，利用T(n)的定义和一个简单的不等式，有取c=

6、am

7、+….+

8、a0

9、定理得证.事实上，只要将n0取得足够大，可以证明只要c是比

10、am

11、大的任意一个常数，此定理都成立。定理1.1若T(n)=amnm+…+a1n+a0是一个m次多项式，则T(n)=O(nm)。此定理表明，变量n的固定阶数为m的任一多项式，与此多项式的最高阶nm同阶.2.2算法的渐进分析2.2算法的渐进分析示

12、例2.2算法的渐进分析2.2算法的渐进分析例.1）假设某算法在输入规模是时为.在某台计算机上实现并完成该算法的时间是秒.现有另一台计算机,其运行速度为第一台的64倍,那么,在这台计算机上用同一算法在秒内能解决规模为多大的问题?规模语句频度运行时间/每语句总时间关系式:算法语句频度*运行速度(时间/每语句)=运行总时间解:设在新机器上秒内能解决规模为的问题，由于新机器运行速度提高64倍，则运行时间/每语句变为由关系式，得解，得2.2算法的渐进分析由于此时，新机器的运行速度/每语句为：2)若上述算法改进后，新算法,则在新机器上用秒时间能解决输入规模为多大的问题？代入关系式，得设在新

13、机器上用t秒时间能解决输入规模为N的问题，则解，得2.2算法的渐进分析思考：以上说明了什么问题？2.大Ω符号--运行时间的下界定义1.2若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)=Ω(g(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c×g(n)2.2算法的渐进分析大Ω符号用来描述增长率的下界也就是说，T(n)=Ω(g(n))是当输入规模为n时，算法消耗时间的最小值。与大Ｏ符号对称，这个下限的阶越高，结果就越有价值。问题的计算时间下界为