《算法效率分析基础》由会员分享，可在线阅读，更多相关《算法效率分析基础（47页珍藏版）》请在金锄头文库上搜索。
1、第第2章章 算法效率分析基算法效率分析基础主要内容：主要内容： 2.1 分析框架分析框架 2.2 渐进符号和基本效率符号和基本效率类型型 2.3 非非递归算法的数学分析算法的数学分析 2.4 递归算法的数学分析算法的数学分析2.1 算法分析的基本框架 一般而言，对于一个算法的分析主要是对算法效率的分析，包括了衡量其运行速度的时间效率以及衡量算法运行需要占用空间大小的空间效率。对于早期的计算机来说，时间与空间都是极其珍贵的资源。半个世纪以来，硬件技术的发展大大提高了计算机的存储容量，使得存储容量的局限性对于算法的影响大大降低了。但时间效率并没有得到相同程度的提高。因此，算法的时间效率是算法分析中
2、的关键部分。 2.1.1 输入规模的度量一个显而易见的事实是：大部分算法的执行时间随着输入量的增加而增大。例如在对一个数组进行排序时，数组越大，排序需要的时间就越长。因此从逻辑上来说，算法的效率应该是输入量的函数。 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)runnin
4、g timeexecution timefor basic operationNumber of times basic operation is executedinput size其中其中: c: copop为为特定特定计计算机上一个基本操作的算机上一个基本操作的执执行行时间时间，是常量。，是常量。 如果如果这这个算法运行在一台比我个算法运行在一台比我们现们现有机器快有机器快10倍的机器上，它运行得有多快？倍的机器上，它运行得有多快？答案：答案：10倍倍另外：假另外：假设设C(n)=1/2n(n-1)，如果，如果输输入入规规模模翻倍，翻倍，该该算法会运行多算法会运行多长时间长时间？答案：大
5、答案：大约约需需4倍倍只要只要n的的值值不是非常小，就有：不是非常小，就有：2.1.3 增长次数小小规规模的模的输输入在运行入在运行时间时间上不能区分高效上不能区分高效的算法与低效的算法，要考的算法与低效的算法，要考虑对虑对于大于大规规模模输输入入时执时执行次数的增行次数的增长长次数。次数。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、级操作次数的算法只能用来操作次数的算法只能用来解决解决规规模非常小的模非常小的问题问题2.1.4 算法最优、最差和平均效率算法最差效率：当算法最差效率：当输入入规模模为n时，算法在最坏情，算法在最坏情 况下的效率。况下的效率。算法最算法最优效率：当效率：当输入入规模模为n时，算法在最理想情况，算法在最理想情况下的效率。下的效率。算法平均效率：在算法平均效率：在“随机随机”或或“典型典型”输入入时（规模模仍仍为n），算法的效率。），算法的效率。平均效率的研究方法：一般将平均效率的研究方法：一般将规模模为n的的实例分例分为几种几种类型，在假型，在假设各种各种输入的概率分布，推入的概率分布，推导出基
7、本操作出基本操作的平均次数。的平均次数。2.1 小结: 算法分析框架的要点算法的算法的时间效率与空效率与空间效率都是算法效率都是算法输入量的入量的函数。函数。 时间效率的衡量通效率的衡量通过算法基本操作算法基本操作执行次数的行次数的估估计进行，而空行，而空间效率的衡量是通效率的衡量是通过算法运行算法运行所占用所占用额外的存外的存储器器资源量源量进行的。行的。 有些算法有些算法时空复空复杂度在相同度在相同输入量下可能由于入量下可能由于具体具体输入入值的不同而不同，因此需要考的不同而不同，因此需要考虑最好最好情况下、最坏情况下以及一般情况下的算法情况下、最坏情况下以及一般情况下的算法时间复复杂度。
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)= 于是，于是，C(n)=n-1(n)2.3.2 分析非递归算法效率的通用方案分析的一般步分析的一般步骤：1、决定哪些参数作、决定哪些参数作为输入入规模的度量模的度量2、找出算法的基本操作、找出算法的基本操作3、检查基本操作的基本操作的执行次数是否只依行次数是否只依赖于于输入入规模模
10、4、求出基本操作的表达式、求出基本操作的表达式5、确定基本操作、确定基本操作执行次数的增行次数的增长次数。次数。 继续继续新的例子之前，我新的例子之前，我们们可以再复可以再复习习一下算法一下算法分析中常用的求和公式及法分析中常用的求和公式及法则则。其中，使用得。其中，使用得特特别频别频繁的是求和运算的两个基本法繁的是求和运算的两个基本法则则以及两个求和公式：以及两个求和公式： u、l分分别别是上下限整数，是上下限整数， 且且lu 考考虑一下元素唯一性一下元素唯一性问题：验证给定数定数组中的元素是否全部唯一。算法如下：中的元素是否全部唯一。算法如下：UniqueElements(A0n-1)/验
11、证给定数定数组中的元素是否全部惟一中的元素是否全部惟一/输入：数入：数组A0n-1/输出：如果出：如果A中的元素全部惟一，返回中的元素全部惟一，返回“true”/否否则，返回，返回“false”for i0 to n2 do for ji+1 to n-1 do if Ai=Ajreturn falsereturn true 本本题题中，中，输输入入规规模：数模：数组组元素元素n基本操作：比基本操作：比较较因因为为最内最内层层循循环环只包含一个操作（两个元只包含一个操作（两个元素的比素的比较较），可以把它作），可以把它作为该为该算法基本的算法基本的操作操作根据定根据定义义，如果，如果对对某个数
12、某个数组组所作的比所作的比较较数数Cworst(n)比其他数比其他数组组都多，那么它是都多，那么它是所有大小所有大小为为n的数的数组组中的最差中的最差输输入。入。 观观察最内察最内层层的循的循环环，有两种，有两种类类型的最差型的最差输输入（它入（它们们不会使算法不会使算法过过早地退出循早地退出循环环）：）：不包括相同元素的数不包括相同元素的数组组，以及最后两个元，以及最后两个元素是惟一一素是惟一一对对相同元素的数相同元素的数组组。对对于于这样这样的的输输入，最内入，最内层层每每执执行一次就会行一次就会进进行一次行一次比比较较，并且，并且对对于循于循环变环变量量j在在i+1和和n-1之之间间的每
13、个的每个值值都会做一次循都会做一次循环环。而。而对对外外层层循循环变环变量量i在在0和和n-2之之间间的每个的每个值值，上述，上述过过程都会再重复一遍。程都会再重复一遍。因此，我因此，我们们有：有： 用下面用下面这这个方法个方法计计算算 会更快会更快2.3.3 计算两个n阶方阵乘积的例子 对于两个于两个给定的定的n阶方方阵A和和B的乘的乘积计算算问题(C=AB)，求基于定，求基于定义的算法的的算法的时间效率。根据定效率。根据定义，C是一个是一个n阶方方阵，它的每个元素都是矩，它的每个元素都是矩阵A的的行和行和B的列的点的列的点积：第第i行行第第J列列 对对于于i0和和jn-1的每一的每一对对下
14、下标标，Ci,j=Ai,0Bo,j+Ai,kBk,j+Ai,n-1Bn-1,j 算法算法伪代代码：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为执行一次乘法在某行一次乘法在某计算机上所需要的算机上所需要的时间
15、若考若考虑加法，加法，则 T(n)CmM(n)+CaA(n)=cmn3+can3 =(cm+ca)n3 其中其中Ca为执行一次加法在某行一次加法在某计算机上所需要的算机上所需要的时间，A(n)为加法的加法的执行次数。行次数。2.4 递归算法的数学分析例例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 return F(n-1)*n C语
16、言表示：言表示： 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 于是，于是， M(n)=M(n-1)+1=M(n-n)+n=n分析递归算法效率的通用方案分析的一般步分析的一般
17、步骤：1、决定哪些参数作、决定哪些参数作为输入入规模的度量模的度量2、找出算法的基本操作、找出算法的基本操作3、检查对于相同于相同规模的不同模的不同输入，基本操作的入，基本操作的执 行次数是否不同行次数是否不同4、求出基本操作的、求出基本操作的递归关系表达式及初始条件关系表达式及初始条件5、解、解递归关系，得基本操作关系，得基本操作执行次数的增行次数的增长次数次数递归的思路 实际上, 递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决(此时分解到递归出口)。 但递归分解
18、不是随意的分解,递归分解要保证“大问题”与“小问题”相似,即求解过程与环境都相似。并且有一个分解的终点。从而使问题可解。 递归的的执行行过程由分解程由分解过程和求程和求值过程两部程两部分构成。分构成。 分解分解过程是程是“量量变”过程程,即原来的即原来的“大大问题”在慢慢在慢慢变小小,但尚未解决；遇到但尚未解决；遇到递归出口后出口后,便便发生了生了“质变”,即原即原递归问题便便转化成直接化成直接问题.求解5!的过程如下：例：汉诺塔（Tower of Hanoi）问题 盘子移动时必须遵守以下规则：每次只能移动一个盘子；盘子可以插在A,B和C中任一塔座；不能将一个较大的盘子放在较小的盘子上。Han
19、oi(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) H(1)=1解解该递归关系可得关系可得 H(n)=2n-1这是个指数是个指数级的算法，是算法不好的算法，是算法不好吗？对这个个问题而言，它是一个高效的算法而言，它是一个高效的算法2.5 例题：斐波那契数列问题：如果一对兔子每月能生一对小兔子，每对兔子在它出生后的第三个月又能开始生一对小兔子问由一对小兔子开始，50个月后共有多少
20、对小兔子？写出斐波那契数列写出斐波那契数列: 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 或写成或写成:2.5.1 计算斐波那契数列的精确解法用母函数法用母函数法: an=an-1+an-2 anxn=xan-1xn-1+x2an-2xn-2 得 s(x)-a0-a1x=x(s(x)-a0)+x2s(x)(1-x-x2)S(x)=x2.5.2 计算斐波那契数列的递归算法算法算法Fib (n) : if n1 return n else rerurn Fib (n-1)+Fib(n-2) 此算
21、法效率不高此算法效率不高. 下面分析下面分析n=5的的递归树斐波那契数列的递归调用树:效率不高的原因效率不高的原因:重复重复计算相同的函数算相同的函数值.改改进的算法的算法:算法算法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)2.6 算法的经验分析通用方案通用方案 1、了解、了解实验的目的的目的 2、决定用来度量效率的量度和、决定用来度量效率的量度和单位位 3、决定、决定输入入样本的特性本的特性 4、为实验准准备算法的程序算法的程序 5、生成、生成输入入样本本 6、对样本运行算法，本运行算法，记录实验结果果 7、分析、分析获得的得的实验数据（如用散点数据（如用散点图）谢 谢! !
