算法的时间复杂性.pptx

2.1时间复杂性函数T(N,I)是算法在一台抽象的计算机上运行所需的时间。设此抽象的计算机所提供的元运算有k种，他们分别记为O1,O2,.,Ok；设这些元运算每执行一次所需要的时间分别为t1,t2,.,tk。n对于给定的算法A，用到元运算Oi的次数为ei，i=1,2,.,k，很明显，对于每一个i，ei是n和I的函数，即ei=ei(n,I)。那么有：其中ti，i=1,2,.,k,是与N,I无关的常数。先看一个实例：改进冒泡如排序算法的基本步骤如下：fori1ton-1doflag1forj1ton-idoifajaj+1then交换aj、aj+1flag0/*发生了交换*/ifflagthenbeak/*没有交换，排序结束*/enddo如果将ifajAmthenLI+1elseUm-1n规则规则7对于break语句。为了便于表达从循环体的中途跳转到循环体的结束,引入break语句。在时间复杂性分析时可以假设它不需要任何额外的时间。n规则规则8对于过程调用和函数调用语句，它们需要的时间包括两部分，一部分用于实现控制转移，另一部分用于执行过程(或函数)本身，这时可以根据过程(或函数)调用的层次，由里向外运用规则(l)-(7)进行分析，一层一层地剥，直到计算出最外层的运行时间便是所求。如果过程(或函数)出现直接或间接的递归调用，则根据过程(或函数)的内涵建立起这些待定函数之间的递归关系得到递归方程。最后用求递归方程解的渐进阶的方法确定最坏情况下的复杂性的渐进阶。经验和技巧是非常重要的BUILD-MAX-HEAP(A)1heap-sizeAlengthA2forilengthA/2downto1n/2次3doMAX-HEAPIFY(A,i)归结到分析MAX-HEAPIFY(A,i)的时间例：建最大堆算法的复杂性分析MAX-HEAPIFY(A,i)1lLEFT(i)2rRIGHT(i)3iflheap-sizeAandAlAi/与左孩子比较，不满足堆的条件4thenlargestl /记下较大者的下标5 elselargesti6ifrheap-sizeAandArAlargest7thenlargestr /与右孩子比较，不满足堆的条件8iflargesti9thenexchangeAiAlargest10MAX-HEAPIFY(A,largest)每层比较2次，整理时间与i的高度成正比。整理堆的实例有n个节点的堆，最大整理时间为2logn。粗略分析建堆的时间为nlogn，但似乎太不精确了。考察实例的建堆过程，总体比较时间为所有节点的整理时间之和，各层上的节点的整理时间是相同的。BUILD-MAX-HEAP(A)1heap-sizeAlengthA2forilengthA/2downto13doMAX-HEAPIFY(A,i)i在第h层上，整理的时间与h成正比，用O(h)表示。第h层的节点数为n/2h+1整理时间为n/2h+1O(h)。建构堆的时间：复杂性的渐近性态的概念一个算法的时间复杂度(TimeComplexity)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的复杂性的渐近性态（渐进时间复杂度）。分析算法的时间复杂性的目的是为了比较完成同一功能的程序的算法之间的最主要的差别。如果两个算法执行步数分别是3n+2，3n+20，时间复杂性至多相差一个常数倍。对于两个具有时间复杂性：2n，cn对于充分大的n，两者的复杂性差别是很大的。所以，我们要引进渐进性，用复杂性的阶描述算法的复杂性。2.2 复杂性的渐近性态设T(N)是关于算法A的复杂性函数。一般说来，当N单调增加且趋于时,T(N)也将单调增加趋于。对于T(N)，如果存在T(N)，使得当N时有：(T(N)-T(N)/T(N)0那么，我们就说T(N)是T(N)当N时的渐近性态，或叫T(N)为算法A当N的渐近复杂性，因为在数学上，T(N)是T(N)当N时的渐近表达式。T(N)是T(N)中略去低阶项所留下的主项。所以它无疑比T(N)来得简单。例如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时的复杂性的度量。这种替代是对复杂性分析的一种简化。即当问题的规模充分大时，只要考察算法复杂性在渐近意义下的阶。有3种渐近性态和其意义下的记号：、需要掌握。f(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的定义的定义例：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(n2).3n2+2=O(n2)g也称作f的阶函数。对于多项式情形的复杂性函数，其阶函数可取该多项式的最高项。按照大的定义，有如下运算规则：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)；规则1的证明：设F(N)=(f)。根据记号的定义，存在正常数C1和自然数N1，使得对所有的NN1，有F(N)C1 f(N)。类似地，设G(N)=(g)，则存在正的常数C2和自然数N2使得对所有的NN2有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)分析冒泡排序算法的时间复杂性。fori1ton-1doforj1ton-idoifaj=N0，有f(n)Cg(n)，记作f(n)=(g(n)当n充分大时，在相差一个非零常数倍的情况下，g是f的一个下界函数。同理，这个下界的阶越高，则评估就越精确，结果就越有价值。符号符号的定义的定义 当且仅当存在正的常数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)的阶的精确估计。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,b,a,c);T(n-1)end.设hanoi(n,a,b,c)的时间复杂性函数为T(n),这是一个递归方程。可以用迭代法，迭代法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数，然后求级数的和。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递归方程：递归方程：递归方程组解的渐进阶的求法递归方程组解的渐进阶的求法母函数法母函数法设关于T(n)的递归方程的解的母函数为：(1)-(2)-(3)得(1)(2)(3)根据G(x)的形式：有T(n)=a2-b2作业1分析算法的时间复杂性nintHorner(intcoeff,intn,constintx)n/计算n次多项式的值，coeff0:n为多项式的系数nintvalue=coeffnnfor(inti=1;i=n;i+)nvalue=value*x+coeffn-inreturnvaluenn2、有三个矩阵A,B,C，它们的阶分别为32、26、61，要求计算3个矩阵的连乘：ABC。a)统计乘法运算的次数b)最少需要做几次乘法？3、分析折半查找（二分检索）的最坏情况下的时间复杂性，证明其达到了问题复杂度的下界。证明下列运算规则(f)+(g)=(f+g)；(f)(g)=(fg)；如果g(N)=(f(N)，则(f)+(g)=(f)；(Cf(N)=(f(N)，其中C是一个正的常数；