时间复杂解说PPT学习教案

1、会计学1时间复杂解说时间复杂解说第1页/共48页第2页/共48页2/2/)1(6/)12)(1(2/)1(1111111 nnnnniijniijjkniniij第3页/共48页第4页/共48页往往是我们最关注的。第5页/共48页第6页/共48页第7页/共48页第8页/共48页（2）下界函数第9页/共48页)()(ngnT（3） “平均情况”限界函数第10页/共48页第11页/共48页第12页/共48页第13页/共48页第14页/共48页用数学归纳法来证明。第15页/共48页第16页/共48页（2）反向替换法例如：X(n)=x(n-1)+n 使用所讨论的递推关系，将x(n-1)表示为x(n-2

2、)得函数，然后把这个结果代入原始方程，来把x(n)表示为x(n-2)的函数。重复这一过程。X(n)=x(0)+1+2+3+4+5+n=0+1+2+3=4 = n(n+1)/2第17页/共48页bknfnf)/()( 上面形式的在递推关系式，一个规模为n的问题，每一次递归调用后，都简化为n/k规模的问题，为了方便求解，我们通常设定：n=km，则，上面的求解过程可简化为： f(n)= f(km-1)+b = f(km-2)+2b = = f(k0)+mb = f(1) + blog n 第18页/共48页int BinSrch(Type A,int i, int n, Type x)/Ai.n是非

3、递减排列 且 1=i=n; if(n=i) if(x=Ai) return i; else return 0; else int mid=(i+n)/2; if(x=Amid) return mid; -基本操作基本操作 else if(xAmid) return BinSrh(A, mid+1, n, x);递归调用 第19页/共48页11nn1)2/(1)(nCnC因为规模每一次递归调用后，缩减为原来的1/2，所以采用换名方法求解，设 n = 2k：C(n) = C(2k)= C(2k-1)+1 = C(2k-2) + 2 = =C(2k-k)+k =C(1) + k = logn+1第2

4、0页/共48页39 17 21 34 57 69 84 92 1039 17 2157 69 84 92 10317 2157 6992 10691021第21页/共48页第22页/共48页int Select(int data,int p,int r,int k) if(pr) return -1; /p不能大于r if(p=r) return datap; /pk) int r1= Select(data,p,s-1,k);-递归调用递归调用 return r1; else /sk int r1=Select(data,s+1,r,k-s);-递归调用递归调用 return r1; 第23

5、页/共48页1)1()2/(11)(nnnTnnT因为每一次规模都减到原来的1/2，所以用换名的方法设 n = 2k：T(n) = T(n/2) + (n-1) = T(2k-1) + (2k-1) =T(2k-2) + (2k-1-1)+ (2k-1) = =T(2k-k) + (21-1) + +(2k-1-1) +(2k-1) =T(1)+(2k+1-2)-k =2n-logn-1第24页/共48页1)1()2/(11)(nnnTnnT算法的复杂度有两部分决定：递归和合并，递归的复杂度是：logn，合并的复杂度是 n。第25页/共48页)()2/(2)(1)2(nOnTnTT第26页/共

6、48页第27页/共48页不失一般性，设规模为n的问题，每一次有分解为m个子问题，设n =mk，则：)()/()(1) 1 (nOmnmTnTT第28页/共48页第29页/共48页算法的复杂度有两部分决定：递归和合并，递归的复杂度是：n，合并的复杂度是 nlogn。)()/()(1)1 (nOmnmTnTT第30页/共48页1) 2/(*3) 2/(11)(2nnnTnnT第31页/共48页所以：O(n2)第32页/共48页Recursive_Miltiply(x,y)if n=1if (X=1)and(Y=1) return(1) else return(0) x1 =X的左边n/2位; x0

7、 =X的右边n/2位; y1 =Y的左边n/2位; y0 =Y的右边n/2位; p = Recursive_Miltiply(x1+x0,y1+y0);递归调用递归调用x1y1 = Recursive_Miltiply(x1,y1);递归调用递归调用x0y0 = Recursive_Miltiply(x0,y0);递归调用递归调用return x1y1*2n + (p-x1y1-x0y0)*2n/2+x0y0;基本操作基本操作第33页/共48页11)()2/(3) 1 ()(nnnOnTOnTkkkkikikkkTTTTT3)2(3)2(3)2(3)2(3)2(221设，n=2k, 用反向替换法对它求解：585.13loglog223)(nnnTn第34页/共48页11)()2/(3) 1 ()(nnnOnTOnT第35页/共48页=O(n2)=O(2n)=O(1)=O(logn)=O(n)第36页/共48页定义1 如果存在两个正常数c和n0，对于所有的nn0，有 |f(n)| c|g(n)| 则记作f(n) = (g(n)O(1) = O(2) 相差的只是常数因子第37页/共48页设新机器用统一算法能解输入规模为n1的问题，则： t=3*2n1/64=3*2n1-6 所以，n1=n+6第38页/共48页n12=64n2=(8n)2能解规模为8n的问题第39页/共48页由于T