《算法时间复杂性.pptx》由会员分享，可在线阅读，更多相关《算法时间复杂性.pptx（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、先看一个实例：改进冒泡如排序算法的基本步骤如下：fori1ton-1doflag1forj1ton-idoifajaj+1then交换aj、aj+1flag0/*发生了交换*/ifflagthenbeak/*没有交换，排序结束*/enddo如果将ifajAmthenLI+1elseUm-1第7页/共34页规则7对于break语句。为了便于表达从循环体的中途跳转到循环体的结束,引入break语句。在时间复杂性分析时可以假设它不需要任何额外的时间。规则8对于过程调用和函数调用语句，它们需要的时间包括两部分，一部分用于实现控制转移，另一部分用于执行过程(或函数)本身，这时可以根据过程(或函数)调用的
2、层次，由里向外运用规则(l)-(7)进行分析，一层一层地剥，直到计算出最外层的运行时间便是所求。如果过程(或函数)出现直接或间接的递归调用，则根据过程(或函数)的内涵建立起这些待定函数之间的递归关系得到递归方程。最后用求递归方程解的渐进阶的方法确定最坏情况下的复杂性的渐进阶。第8页/共34页 经验和技巧是非常重要的BUILD-MAX-HEAP(A)1heap-sizeAlengthA2forilengthA/2downto1n/2次3doMAX-HEAPIFY(A,i)归结到分析MAX-HEAPIFY(A,i)的时间例：建最大堆算法的复杂性分析第9页/共34页MAX-HEAPIFY(A,i)1
3、lLEFT(i)2rRIGHT(i)3iflheap-sizeAandAlAi/与左孩子比较，不满足堆的条件4thenlargestl /记下较大者的下标5 elselargesti6ifrheap-sizeAandArAlargest7thenlargestr /与右孩子比较，不满足堆的条件8iflargesti9thenexchangeAiAlargest10MAX-HEAPIFY(A,largest)每层比较2次，整理时间与i的高度成正比。第10页/共34页整理堆的实例有n个节点的堆，最大整理时间为 2 log n。粗略分析建堆的时间为 n log n，但似乎太不精确了。第11页/共34
4、页考察实例的建堆过程，总体比较时间为所有节点的整理时间之和，各层上的节点的整理时间是相同的。第12页/共34页BUILD-MAX-HEAP(A)1heap-sizeAlengthA2forilengthA/2downto13doMAX-HEAPIFY(A,i)i在第h层上，整理的时间与h成正比，用O(h)表示。第h层的节点数为n/2h+1整理时间为n/2h+1 O(h)。建构堆的时间：第13页/共34页复杂性的渐近性态的概念一个算法的时间复杂度(TimeComplexity)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)
5、称为算法的复杂性的渐近性态（渐进时间复杂度）。第14页/共34页分析算法的时间复杂性的目的是为了比较完成同一功能的程序的算法之间的最主要的差别。如果两个算法执行步数分别是3n+2，3n+20，时间复杂性至多相差一个常数倍。对于两个具有时间复杂性：2n，cn对于充分大的n，两者的复杂性差别是很大的。所以，我们要引进渐进性，用复杂性的阶描述算法的复杂性。2.2 复杂性的渐近性态第15页/共34页设T(N)是关于算法A的复杂性函数。一般说来，当N单调增加且趋于时,T(N)也将单调增加趋于。对于T(N)，如果存在T(N)，使得当N时有：(T(N)-T(N)/T(N)0那么，我们就说T(N)是T(N)当
6、N时的渐近性态，或叫T(N)为算法A当N的渐近复杂性，因为在数学上，T(N)是T(N)当N时的渐近表达式。T(N)是T(N)中略去低阶项所留下的主项。所以它无疑比T(N)来得简单。第16页/共34页例如T(n)=3N 2+4Nlog2N+7时，T(N)的一个答案是3N 2。显然3N2比3N2+4Nlog2N+7简单得多。由于当N时T(N)渐近于T(N)，我们有理由用T(N)来替代T(N)作为算法A在N时的复杂性的度量。这种替代是对复杂性分析的一种简化。第17页/共34页即当问题的规模充分大时，只要考察算法复杂性在渐近意义下的阶。有3种渐近性态和其意义下的记号：、需要掌握。第18页/共34页f(
7、n)是某一算法的时间复杂性函数，g(n)是某一函数，当且仅当存在正的常数C和N0，使得对于所有的n=N0，有f(n)=Cg(n)，记作f(n)=O(g(n)即函数f至多是函数g的C倍，当充分大时，g是f的一个上界函数，在相差一个非零常数倍的情况下。通常情况下，g取下列单项的形式：1，logn，n，nlogn，n2，n3，2n，n！渐进符号O的定义第19页/共34页例：C0=O(1):f(n)等于非零常数 3n+2=O(n):取C4，N02。100n+6=O(n):取 C=101，N 06。62n+n2=O(n2):取C=7，N0=4.3log n+2n+n2=O(n2).nlog n+n2=O
8、(n2).3n2+2=O(n2)g也称作f的阶函数。对于多项式情形的复杂性函数，其阶函数可取该多项式的最高项。第20页/共34页按照大的定义，有如下运算规则：1)(f)+(g)=(max(f,g)；2)(f)+(g)=(f+g)；3)(f)(g)=(fg)；4)如果g(N)=(f(N)，则(f)+(g)=(f)；5)(Cf(N)=(f(N)，其中C是一个正的常数；6)f=(f)；第21页/共34页规则1的证明：设F(N)=(f)。根据记号的定义，存在正常数C1和自然数N1，使得对所有的NN1，有F(N)C1 f(N)。类似地，设G(N)=(g)，则存在正的常数C2和自然数N2使得对所有的NN2
9、有G(N)C2g(N)，令：C3=max(C1,C2)，N3=max(N1,N2)和对任意的非负整数N，h(N)=max(f,g),则对所有的NN3有：F(N)C1f(N)C1h(N)C3h(N)类似地，有：G(N)C2g(N)C2h(N)C3h(N)因而(f)+(g)=F(N)+G(N)C3h(N)+C3h(N)=2C3h(N)=(h)=(max(f,g)作业：证明规则 2)6)第22页/共34页分析冒泡排序算法的时间复杂性。fori1ton-1doforj1ton-idoifaj=N0，有f(n)Cg(n)，记作f(n)=(g(n)当n充分大时，在相差一个非零常数倍的情况下，g是f的一个下
10、界函数。同理，这个下界的阶越高，则评估就越精确，结果就越有价值。第25页/共34页符号的定义 当且仅当存在正的常数C1和C2，使得对于所有的n=N0，有C1g(n)f(n)C2g(n)，记作：f(n)=(g(n)例：算法Search在最坏情况下的时间复杂性Tmax(m)。已有Tmax(m)=(m)和Tmax(m)=(m)，所以有Tmax(m)=(m)，这是对Tmax(m)的阶的精确估计。第26页/共34页Procedurehanoi(n,a,b,c)T(n)if(n=1)thenmove(a,c);1elsehanoi(n-1,a,c,b);T(n-1)move(a,c);1hanoi(n-1
11、,b,a,c);T(n-1)end.设hanoi(n,a,b,c)的时间复杂性函数为T(n),第27页/共34页这是一个递归方程。可以用迭代法，迭代法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和。T(n)=2T(n-1)+1 =22T(n-2)+1+1=22T(n-2)+2+1 =23T(n-3)+22+2+1 =2n-1T(1)+2n-2+.2+1 =2n-1第28页/共34页递归方程：递归方程组解的渐进阶的求法母函数法设关于T(n)的递归方程的解的母函数为：(1)-(2)-(3)得(1)(2)(3)第29页/共34页根据G(x)的形式：有T(n)=a2-b2第3
12、0页/共34页作业1分析算法的时间复杂性intHorner(intcoeff,intn,constintx)/计算n次多项式的值，coeff0:n为多项式的系数intvalue=coeffnfor(inti=1;i=n;i+)value=value*x+coeffn-ireturnvalue第31页/共34页2、有三个矩阵A,B,C，它们的阶分别为32、26、61，要求计算3个矩阵的连乘：ABC。a)统计乘法运算的次数b)最少需要做几次乘法？3、分析折半查找（二分检索）的最坏情况下的时间复杂性，证明其达到了问题复杂度的下界。第32页/共34页证明下列运算规则(f)+(g)=(f+g)；(f)(g)=(fg)；如果g(N)=(f(N)，则(f)+(g)=(f)；(Cf(N)=(f(N)，其中C是一个正的常数；第33页/共34页感谢您的观看！第34页/共34页