2-算法效率分析基础2350.pptx

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

1、 2-算法效率分析基础算法效率分析基础陆伟CollegeofSoftwareandMicroelectronics算法设计与分析算法设计与分析Introduction to the Design and Analysis of Algorithms 28March2023NorthwesternPolytechnicalUniversityLecture Overview1.算法效率的度量2.函数的渐进的界3.算法的基本复杂性类型4.算法复杂性分析的基本方法5.非递归算法的复杂性分析6.递归算法的复杂性分析7.递归算法与非递归算法比较8.经验分析方法9.算法可视化2算法效率的度量算法效率的度量

2、算法效率的高低体现在运行该算法所需要耗费资源的多少，对于计算机来讲，最重要的资源是时间和空间，因此，算法效率又可分为时间效率和空间效率。分别用N，I和A表示要解决问题的规模、算法的输入和算法本身，用C表示复杂性，那么，应该有C=F(N,I,A)。如果吧时间复杂性与空间复杂性分开，分别用T和S表示，则T=F(N,I,A)，S=F(N,I,A)。T=T(N,I)，S=S(N,I)。3算法效率的度量算法效率的度量计算机存储容量的发展使得算法空间复杂性已经不再是关注的重点，但时间复杂性仍然十分重要。因此，我们后续也将主要讨论算法的时间复杂性，但是所讨论的方法对于空间复杂性分析也是适用的。根据T=T(N

3、,I)的概念，它应该是算法在一台“抽象的计算机”上运行所需要的时间。4算法效率的度量算法效率的度量设该“抽象的计算机”所提供的元运算有k种，分别记为O1,O2,Ok，又设每执行一次这些元运算所耗费的时间分别为t1,t2,tk。对于给定算法A，统计其执行过程中用到的元运算Oi的次数，记为ei，i=1,2,k。ei=ei(N,I)。其中，ti是与N和I无关的常数。5算法效率的度量算法效率的度量我们不可能对规模为N的每一种合法输入I都去统计ei(N,I)，i=1,2,k。关于摊销效率6函数的渐进的界函数的渐进的界函数的渐进的界设f 和g 是定义域为自然数集N上的函数(1)f(n)=O(g(n)若存在

4、正数c和n0使得对一切nn0有0f(n)cg(n)(2)f(n)=(g(n)若存在正数c和n0使得对一切nn0有0cg(n)f(n)(3)f(n)=o(g(n)对任意正数c存在n0使得对一切nn0有0f(n)cg(n)(4)f(n)=(g(n)对任意正数c存在n0使得对一切nn0有0cg(n)1和0，logbn=o(n)，n=o(bn)。n!=o(nn)，n!=(2n)，log(n!)=(nlogn)12算法的基本复杂性类型算法的基本复杂性类型13算法复杂性分析的基本方法算法复杂性分析的基本方法（1）决定表示输入规模的参数。（2）找出算法的基本操作。（3）检查基本操作的执行次数是否只依赖于输入

5、规模。如果还依赖于输入的其它特性，考虑最差、平均以及最优情况下的复杂性。（4）对于非递归算法，建立算法基本操作执行次数的求和表达式；对于递归算法，建立算法基本操作执行次数的递推关系及其初始条件。（5）利用求和公式和法则建立一个操作次数的闭合公式，或者求解递推关系式，确定增长的阶。14非递归算法的复杂性分析非递归算法的复杂性分析对于等差数列ak，对于等比数列aqk，对于调和级数1/k，对数求和，15非递归算法的复杂性分析非递归算法的复杂性分析例16算法算法 MaxElement(A0.n-1/求给定数组中的最大元素/输入：实数数组A0.n-1/输出：A中的最大元素maxval A0fori 1t

6、on-1doifAimaxvalmaxvalAireturnmaxval非递归算法的复杂性分析非递归算法的复杂性分析（1）算法输入规模：可以用数组元素个数n度量（2）基本操作：比较与赋值两种，选择比较（3）比较操作只与输入规模相关，不用考虑最坏、平均、最好情况（4）建立基本操作执行次数求和表达式（5）确定增长的阶17非递归算法的复杂性分析非递归算法的复杂性分析18算法算法 UniqueElements(A0.n-1/验证给定数组中的元素是否全部唯一/输入：实数数组A0.n-1/输出：如果A中的元素全部唯一，返回“true”，否则，返回“false”fori1ton-2doforji+1ton-

7、1doifAi=Ajreturnfalsereturntrue非递归算法的复杂性分析非递归算法的复杂性分析19templatevoid insertion_sort(Type*a,int n)Type key;/cost times for(int i=1;i=0&ajkey)/c4 sum of ti aj+1=aj;/c5 sum of(ti-1)j-;/c6 sum of(ti-1)aj+1=key;/c7 n-1 非递归算法的复杂性分析非递归算法的复杂性分析20在最好情况下，ti=1,for1i n;在最坏情况下，tii+1,for1i 0，（2）若，（3）若，0，递归算法的复杂性分析

8、递归算法的复杂性分析当f(n)为常数时当f(n)=cn时23递归算法的复杂性分析递归算法的复杂性分析例24inthanoi(intn,inta,intb,intc)if(n=1)move(a,c);elsehanoi(n-1,a,c,b);move(a,c);hanoi(n-1,b,a,c);递归算法的复杂性分析递归算法的复杂性分析T(n)=T(n/3)+T(2n/3)+n25递归算法与非递归算法比较递归算法与非递归算法比较阶乘问题26递归算法与非递归算法比较递归算法与非递归算法比较27intfactorial(intn)if(n=0)return1;returnn*factorial(n-1

9、);intfactorial(intn)intfn=1;for(inti=2;i=n;i+)fn=fn*i;returnfn;递归算法与非递归算法比较递归算法与非递归算法比较Fibonacci数列28边界条件边界条件递归方程递归方程intfibonacci(intn)if(n=1)returnn;returnfibonacci(n-1)+fibonacci(n-2);递归算法与非递归算法比较递归算法与非递归算法比较29递归算法与非递归算法比较递归算法与非递归算法比较30staticintFibonacci2(intn)inta=newintn;a0=1;a1=1;for(inti=2;in;i

10、+)ai=ai-1+ai-2;returnan-1;递归算法与非递归算法比较递归算法与非递归算法比较31递归算法与非递归算法比较递归算法与非递归算法比较32并非所有递归算法都有非递归定义。Ackerman函数Ackerman函数A(n,m)有两个独立的整型变量m0和 n0，定义如下：当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。递归算法与非递归算法比较递归算法与非递归算法比较Ackerman函数33A(n，m)的自变量m的每一个值都定义了一个单变量函数：m=0时，A(n,0)=n+2m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，A(1,1)=2故A(n,1)=2nm=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=2n。m=3时，类似的可以推出A(n,3)=m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。经验分析法经验分析法数学远远不是万能的，即使许多貌似简单的算法，有时也很难用数学的精确性和严格性来分析，尤其是在做平均效率分析的时候。除了可以对算法的效率做数学分析以外，另一种主要方法是对算法的效率做实验和经验分析。34经验分析法经验分析法35算法可视化算法可视化参考36Summary