算法效率分析基础ppt课件.ppt

《算法效率分析基础ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法效率分析基础ppt课件.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 主要内容：主要内容： 2.1 分析框架分析框架 2.2 渐进符号和基本效率类型渐进符号和基本效率类型 2.3 非递归算法的数学分析非递归算法的数学分析 2.4 递归算法的数学分析递归算法的数学分析 一般而言，对于一个算法的分析主要是对算法效率的分析，包括了衡量其运行速度的时间效率以及衡量算法运行需要占用空间大小的空间效率。对于早期的计算机来说，时间与空间都是极其珍贵的资源。半个世纪以来，硬件技术的发展大大提高了计算机的存储容量，使得存储容量的局限性对于算法的影响大大降低了。但时间效率并没有得到相同程度的提高。因此，算法的时间效率是算法分析中的关键部分。 一个显而易见的事实是：大部分算法的执行

2、时间随着输入量的增加而增大。例如在对一个数组进行排序时，数组越大，排序需要的时间就越长。因此从逻辑上来说，算法的效率应该是输入量的函数。 2.1.2 运行时间的度量单位 算法时间包括了编译该算法的时间以及运行该算法的时间。因此衡量算法时间的单位很自然的会想到用“秒”、“毫秒”等实际的时间单位。这对于算法的测试者而言是很直观的，但是存在的问题是：编译算法的时间与编译程序的好坏有关，即使只考虑算法运行时间，得到的时间也受到了运行该算法的计算机速度的影响。因此一个算法在某一台计算机上实现得到的时间对于其他的计算机是没有参考意义的。 统计算法每一步操作的执行次数不可行。统计算法中最重要的操作基本操作的

3、执行次数。 排序的基本操作：比较 矩阵乘法的基本操作：乘法 多项式求值的基本操作：乘法这样，我们建立起了一个算法事件效率的分析框架。它提出，对于输入规模为n的算法，我们可以统计它的基本操作执行次数，来对其效率进行度量。执行次数C(n)是输入规模n的函数，算法运行时间T(n)是执行次数的函数：Basic operation: the operation that contributes most towards the running time of the algorithm. T(n) copC(n)running timeexecution timefor basic operationN

4、umber of times basic operation is executedinput size 如果这个算法运行在一台比我们现有机器快如果这个算法运行在一台比我们现有机器快10倍的机器上，它运行得有多快？倍的机器上，它运行得有多快？ 答案：答案：10倍倍 另外：假设另外：假设C(n)=1/2n(n-1)，如果输入规，如果输入规模翻倍，该算法会运行多长时间？模翻倍，该算法会运行多长时间？ 答案：大约需答案：大约需4倍倍 只要只要n的值不是非常小，就有：的值不是非常小，就有：22212121) 1(21)(nnnnnnC421)2(21)()2()()2(22nnnCcnCcnTnTop

5、op 小规模的输入在运行时间上不能区分高效小规模的输入在运行时间上不能区分高效的算法与低效的算法，要考虑对于大规模的算法与低效的算法，要考虑对于大规模输入时执行次数的增长次数。输入时执行次数的增长次数。n log2n nlog2n n2 n3 2n n! 10 3.3 3.310 102 103 103 3.6106102 6.6 6.6102 104 106 1.31030 3.610157103 10 1.0104 106 109105 17 1.7106 1010 1015 一个需要指数级操作次数的算法只能用来一个需要指数级操作次数的算法只能用来解决规模非常小的问题解决规模非常小的问题

6、算法最差效率：当输入规模为算法最差效率：当输入规模为n时，算法在最坏情时，算法在最坏情 况下的效率。况下的效率。 算法最优效率：当输入规模为算法最优效率：当输入规模为n时，算法在最理想情时，算法在最理想情况下的效率。况下的效率。 算法平均效率：在算法平均效率：在“随机随机”或或“典型典型”输入时（规模输入时（规模仍为仍为n），算法的效率。），算法的效率。 平均效率的研究方法：一般将规模为平均效率的研究方法：一般将规模为n的实例分为几的实例分为几种类型，在假设各种输入的概率分布，推导出基本操种类型，在假设各种输入的概率分布，推导出基本操作的平均次数。作的平均次数。 算法的时间效率与空间效率都是算

7、法输入量的算法的时间效率与空间效率都是算法输入量的函数。函数。 时间效率的衡量通过算法基本操作执行次数的时间效率的衡量通过算法基本操作执行次数的估计进行，而空间效率的衡量是通过算法运行估计进行，而空间效率的衡量是通过算法运行所占用额外的存储器资源量进行的。所占用额外的存储器资源量进行的。 有些算法时空复杂度在相同输入量下可能由于有些算法时空复杂度在相同输入量下可能由于具体输入值的不同而不同，因此需要考虑最好具体输入值的不同而不同，因此需要考虑最好情况下、最坏情况下以及一般情况下的算法时情况下、最坏情况下以及一般情况下的算法时间复杂度。间复杂度。 算法的分析框架关注的内容是当输入量很大，算法的分

8、析框架关注的内容是当输入量很大，趋向无穷的时候，算法的时间复杂度是如何增趋向无穷的时候，算法的时间复杂度是如何增长，即使用算法的时间复杂度的渐进表示法。长，即使用算法的时间复杂度的渐进表示法。 O(2n)O(n!) O(nn)常见的指数阶常见的指数阶O(1) O(logn) O(n) O(nlogn) O(n2)O(n3) maxval maxval=Ai return maxval 输入规模：输入规模：n 确定基本操作：是赋值运算还是比较运算确定基本操作：是赋值运算还是比较运算? 算法中执行最频繁的操作在算法中执行最频繁的操作在for循环中。循环体中存在循环中。循环体中存在两种操作：比较运算

9、两种操作：比较运算Aimaxval和赋值运算和赋值运算maxval=Ai。 每做一次循环都会进行一次比较，而赋值运算并不是，每做一次循环都会进行一次比较，而赋值运算并不是，我们应该把我们应该把比较运算比较运算作为该算法的基本操作作为该算法的基本操作 求基本操作的执行次数求基本操作的执行次数记记C(n)为比较运算的执行次数，则为比较运算的执行次数，则C(n)=111ni 于是，于是，C(n)=n-1(n)分析的一般步骤：分析的一般步骤：1、决定哪些参数作为输入规模的度量、决定哪些参数作为输入规模的度量2、找出算法的基本操作、找出算法的基本操作3、检查基本操作的执行次数是否只依赖于输入、检查基本操

10、作的执行次数是否只依赖于输入规模规模4、求出基本操作的表达式、求出基本操作的表达式5、确定基本操作执行次数的增长次数。、确定基本操作执行次数的增长次数。 继续新的例子之前，我们可以再复习一下算继续新的例子之前，我们可以再复习一下算法分析中常用的求和公式及法则。其中，使法分析中常用的求和公式及法则。其中，使用得特别频繁的是求和运算的两个基本法则用得特别频繁的是求和运算的两个基本法则 以及两个求和公式：以及两个求和公式： u、l分别是上下限整数，分别是上下限整数， 且且luuliiuliiaccauliiuliiuliiibaba)(ulilu11201212) 1(.21nnnniinini 考

11、虑一下元素唯一性问题：验证给定数组考虑一下元素唯一性问题：验证给定数组中的元素是否全部唯一。算法如下：中的元素是否全部唯一。算法如下： UniqueElements(A0n-1) /验证给定数组中的元素是否全部惟一验证给定数组中的元素是否全部惟一 /输入：数组输入：数组A0n-1 /输出：如果输出：如果A中的元素全部惟一，返回中的元素全部惟一，返回“true” /否则，返回否则，返回“false” for i0 to n2 do for ji+1 to n-1 do if Ai=Ajreturn false return true 本题中，输入规模：数组元素本题中，输入规模：数组元素n 基本操

12、作：比较基本操作：比较 因为最内层循环只包含一个操作（两个元因为最内层循环只包含一个操作（两个元素的比较），可以把它作为该算法基本的素的比较），可以把它作为该算法基本的操作操作 根据定义，如果对某个数组所作的比较数根据定义，如果对某个数组所作的比较数Cworst(n)比其他数组都多，那么它是比其他数组都多，那么它是所有大小为所有大小为n的数组中的最差输入。的数组中的最差输入。 观察最内层的循环，有两种类型的最差输观察最内层的循环，有两种类型的最差输入（它们不会使算法过早地退出循环）：入（它们不会使算法过早地退出循环）：不包括相同元素的数组，以及最后两个元不包括相同元素的数组，以及最后两个元素是

13、惟一一对相同元素的数组。对于这样素是惟一一对相同元素的数组。对于这样的输入，最内层每执行一次就会进行一次的输入，最内层每执行一次就会进行一次比较，并且对于循环变量比较，并且对于循环变量j在在i+1和和n-1之之间的每个值都会做一次循环。而对外层循间的每个值都会做一次循环。而对外层循环变量环变量i在在0和和n-2之间的每个值，上述过之间的每个值，上述过程都会再重复一遍。程都会再重复一遍。 因此，我们有：因此，我们有：2220202020201120212) 1(2) 1)(2() 1(2) 1)(2(1) 1() 1()1( 1) 1() 1(1)(nnnnnnnnninininnCninini

14、nininijniworst 用下面这个方法计算用下面这个方法计算 会更快会更快20)1(niin2) 1(1.) 1() 1()1(20nnnninni对于两个给定的对于两个给定的n阶方阵阶方阵A和和B的乘积计算问题的乘积计算问题(C=AB)，求基于定义的算法的时间效率。根据定，求基于定义的算法的时间效率。根据定义，义，C是一个是一个n阶方阵，它的每个元素都是矩阵阶方阵，它的每个元素都是矩阵A的的行和行和B的列的点积：的列的点积：,*jiCCBA第第i行行第第J列列 对于对于i0和和jn-1的每一对下标，的每一对下标， Ci,j=Ai,0Bo,j+Ai,kBk,j+Ai,n-1Bn-1,j算

15、法伪代码：算法伪代码：MaxtrixMultiplication(A0.n-1,0.n-1,B0.n-1,0.n-1) for i=0 to n-1 do for j=0 to n-1 do Ci,j=0.0 for k=0 to n-1 do Ci,j=Ci,j+Ai,j*Bi,j return C分析：分析： 输入规模的度量：输入规模的度量：n 基本操作：乘法基本操作：乘法 执行次数表达式执行次数表达式 M(n)= 运行时间：运行时间：T(n)CmM(n) 其中其中Cm为执行一次乘法在某计算机上所需要的时间为执行一次乘法在某计算机上所需要的时间 若考虑加法，则若考虑加法，则 T(n)CmM

16、(n)+CaA(n)=cmn3+can3 =(cm+ca)n3 其中其中Ca为执行一次加法在某计算机上所需要的时间，为执行一次加法在某计算机上所需要的时间，A(n)为加法的执行次数。为加法的执行次数。310101010101nnninjninjnk例例1、n!的递归算法的递归算法(n为正整数为正整数) 。一般的方法：一般的方法： n! = 1*2*(n-1)*n递归的方法递归的方法 递归公式：递归公式： F(n)=F(n-1)n， 0！:=1 算法伪代码：算法伪代码： F(n) / 输入：非负整数输入：非负整数n /输出：输出：n!的值的值 if n=0 return 1 else retur

17、n F(n-1)*n时当时当 1 , )!1( 0 , 1!nnnnn C语言表示：语言表示： int factorial(int n) int x; if (n=0) x=1; else x=factorial (n-1)*n; return(x); / 在该函数在该函数factorial (n)求解过程中求解过程中,直接调用直接调用factorial (n-1)自身自身,所以所以它是一个直接递归函数它是一个直接递归函数 分析：分析： 基本操作：乘法基本操作：乘法 记记M(n)为乘法执行次数，则递归关系表达为乘法执行次数，则递归关系表达式为式为 M(n)=M(n-i)+i， M(0)=0 于

18、是，于是， M(n)=M(n-1)+1=M(n-n)+n=n 分析的一般步骤：分析的一般步骤：1、决定哪些参数作为输入规模的度量、决定哪些参数作为输入规模的度量2、找出算法的基本操作、找出算法的基本操作3、检查对于相同规模的不同输入，基本操作的执、检查对于相同规模的不同输入，基本操作的执 行次数是否不同行次数是否不同4、求出基本操作的递归关系表达式及初始条件、求出基本操作的递归关系表达式及初始条件5、解递归关系，得基本操作执行次数的增长次数、解递归关系，得基本操作执行次数的增长次数递归的思路 实际上, 递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小

19、问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决(此时分解到递归出口)。 但递归分解不是随意的分解,递归分解要保证“大问题”与“小问题”相似,即求解过程与环境都相似。并且有一个分解的终点。从而使问题可解。 递归的执行过程由分解过程和求值过程两部递归的执行过程由分解过程和求值过程两部分构成。分构成。 分解过程是分解过程是“量变量变”过程过程,即原来的即原来的“大问题大问题”在慢慢变小在慢慢变小,但尚未解决；遇到递归出口后但尚未解决；遇到递归出口后,便发便发生了生了“质变质变”,即原递归问题便转化成直接问题即原递归问题便转化成直接问题. fun(5) d1:fu

20、n(4) d2:fun(3) d3:fun(2) d4:fun(1) 返回 1 fun(2)=2 fun(3)=6 fun(4)=24 fun(5)=120 求解5!的过程如下： 盘子移动时必须遵守以下规则：每次只能移动一个盘子；盘子可以插在A,B和C中任一塔座；不能将一个较大的盘子放在较小的盘子上。Hanoi(n,a,b,c)Hanoi(n-1,a,c,b)；move(n,a,c)；Hanoi(n-1,b,a,c)n=4的情形分析：分析： 输入规模：盘子的数量输入规模：盘子的数量 记记H(n)为移动盘子的次数，则递归关系式为移动盘子的次数，则递归关系式 H(n)=H(n-1)+1+H(n-1

21、) H(1)=1 解该递归关系可得解该递归关系可得 H(n)=2n-1这是个指数级的算法，是算法不好吗？这是个指数级的算法，是算法不好吗？对这个问题而言，它是一个高效的算法对这个问题而言，它是一个高效的算法 问题：如果一对兔子每月能生一对小兔子，每对兔子在它出生后的第三个月又能开始生一对小兔子问由一对小兔子开始，50个月后共有多少对小兔子？ 写出斐波那契数列写出斐波那契数列: 0,1,1,2,3,5,8,13,21,34,55,89,. 得递归公式得递归公式: F(n)=F(n-1)+F(n-2) F(0)=0,F(1)=1 或写成或写成:1),2() 1(0,1,)(nnFibnFibnnn

22、Fib 用母函数法用母函数法: an=an-1+an-2 anxn=xan-1xn-1+x2an-2xn-222221212nnnnnnnnnxaxxaxxannnxaxs0)(记 得 s(x)-a0-a1x=x(s(x)-a0)+x2s(x) (1-x-x2)S(x)=x)1111(51)1)(1 (1)(2xxxxxxxxxSnnnnnnnnnnxxxxS)(51)(51)(000251),(51、其中nnna 算法算法Fib (n) : if n1 return n else rerurn Fib (n-1)+Fib(n-2) 此算法效率不高此算法效率不高. 下面分析下面分析n=5的递归

23、树的递归树斐波那契数列的递归调用树: 效率不高的原因效率不高的原因:重复计算相同的函数值重复计算相同的函数值. 改进的算法改进的算法:算法算法Fib(n) : Fib(0)=0;Fib(1)=1; for i=2 to n do Fib(i)=Fib(i-1)+Fib(i-2) return Fib(n) 通用方案通用方案 1、了解实验的目的、了解实验的目的 2、决定用来度量效率的量度和单位、决定用来度量效率的量度和单位 3、决定输入样本的特性、决定输入样本的特性 4、为实验准备算法的程序、为实验准备算法的程序 5、生成输入样本、生成输入样本 6、对样本运行算法，记录实验结果、对样本运行算法，记录实验结果 7、分析获得的实验数据（如用散点图）、分析获得的实验数据（如用散点图）