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

1、第2章第2章第2章第2章第2章第2章running timeexecution timefor basic operationNumber of times basic operation is executedinput size第2章第2章第2章nnCworst)()1bestCn()12(1)12(1)(1)(1)2avgppppCninnpnnnnpinnpnp nnp 第2章第2章常用函数符号：t(n)：一个算法运行的时间 C(n)：基本操作次数 g(n)：用来比较的函数第2章O的定义的定义：存在常数c0和非负整数n0，使得对所有nn0，有t(n)cg(n)则称函数t(n)包含在O(

2、g(n)中，记为t(n)O(g(n).也称函数 t(n)在n充分大时有上界g(n),并称 t(n)的阶不高于g(n)的阶.例如，4nlogn+7 O(nlogn)。第2章第2章的定义的定义：存在常数c0和非负整数n0，使得对所有nn0，有t(n)cg(n)则称函数t(n)包含在(g(n)中，记为t(n)(g(n)也称t(n)的阶不低于g(n)的阶.例如：2n2+11n-10 (n2)，n3(n2)第2章第2章 存在大于0的常数c1、c2和非负整数n0，使得对所有nn0，有 c1g(n)t(n)c2g(n)，则称函数t(n)包含在(g(n)中。记为t(n)(g(n)。例如：3n2+16n+68

3、(n2)的定义：第2章第2章1.O(f)+O(g)=O(max(f,g)2.O(f)+O(g)=O(f+g)3.O(f)O(g)=O(fg)4.如果 g(n)O(f(n),则 O(f)+O(g)=O(f)5.fO(f)6.O(cf(n)=O(f(n)第2章O(g1(n),t2(n)O(g2(n),则O(maxg1(n),g2(n)第2章0 ()O()()lim O(),()()()()n t ng nt nc t(g),tg tgg nt ng n，第2章例如例如 估计如下二重循环算法在最坏情况下时间复杂性估计如下二重循环算法在最坏情况下时间复杂性T(n)T(n)的阶的阶.for i:=1 t

4、o n do for j:=1 to i do s1,s2,s3,s4;/s1,s2,s3,s4为单一赋值语句分析:内循环体只需O(1)时间,故ij 1O(1)O()1O(1iij内循环共需 外循环共需)O)2)1(O()O()O(211(nnniinini第2章O(2O(2n n)O(n!)O(n!)O(nO(nn n)常见的指数阶常见的指数阶O(1)O(1)O(lognO(logn)O(n)O(n)O(nlognO(nlogn)O(nO(n2 2)O(nO(n3 3)4、常见的渐进时间效率类型第2章图2.4 时间函数的增长率第2章注1 对规模较小的问题,决定算法工作效率的可能是算法的简单性

5、而不是算法执行的时间。注2 当比较两个算法的效率时,若两个算法是同阶的,必须进一步考察阶的常数因子才能辨别优劣。第2章第2章第2章111ni 于是，C(n)=n-1(n)第2章第2章第2章310101010101nnninjninjnk第2章countnncountcountdoncountreturn2/11while11log2n第2章(n为正整数)。一般的方法：n!=1*2*(n-1)*n递归的方法时当时当 1,)!1(0,1!nnnnn第2章 C语言表示：int factorial(int n)int x;if(n=0)x=1;else x=factorial(n-1)*n;retur

6、n(x);/在该函数factorial(n)求解过程中,直接调用factorial(n-1)自身,所以它是一个直接递归函数第2章第2章第2章递归的思路 实际上,递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决(此时分解到递归出口)。但递归分解不是随意的分解,递归分解要保证“大问题”与“小问题”相似,即求解过程与环境都相似。并且有一个分解的终点。从而使问题可解。第2章 递归的执行过程由分解过程和求值过程两部分构成。分解过程是“量变”过程,即原来的“大问题”在慢慢变小,但

7、尚未解决；遇到递归出口后,便发生了“质变”,即原递归问题便转化成直接问题.第2章 fun(5)d1:fun(4)d2:fun(3)d3:fun(2)d4:fun(1)返回 1 fun(2)=2 fun(3)=6 fun(4)=24 fun(5)=120 求解5!的过程如下：第2章 盘子移动时必须遵守以下规则：每次只能移动一个盘子；盘子可以插在A,B和C中任一塔座；不能将一个较大的盘子放在较小的盘子上。第2章Hanoi(n,a,b,c)Hanoi(n-1,a,c,b)；move(n,a,c)；Hanoi(n-1,b,a,c)n=4的情形第2章对这个问题而言，它是一个高效的算法第2章1),2()1(0,1,)(nnFibnFibnnnFib第2章20arbrc()(1)(2)0ax nbx ncx n()()(2)0F nF nF n210rr 第2章1515()22nnF n1,2152r11,55 115115()2255nnF n第2章第2章斐波那契数列的递归调用树:第2章第2章第2章