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