时间复杂度复习资料(最全版).pdf

《时间复杂度复习资料(最全版).pdf》由会员分享，可在线阅读，更多相关《时间复杂度复习资料(最全版).pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.2.21.2.2算法分析算法分析算法分析的两个主要方面是算法的时间复杂度和空底复杂度，其目的主要是考察算法 的时间和空间效率.以求改进算法或对不同的算法进行比较一般情况下，崟于运算空间(内 存)较为充足，所以把算法的时间复杂度作为分析的重点.所谓一个语句的频度，即指该语句在算法中被重豆执行的次数。算法中所有语句的频 度之和记做T(n),T(n),它是该算法所求解问题规模n n的函数。当阿题的规模D趋向无穷大时，T(n)T(n)的数量级称为渐近时间复杂度，置称为时间复杂度，记作T(n)-O(fln)eT(n)-O(fln)e上述表达式中“0”“0”的含义是T(n)T(n)的数量级，其严格的数

2、学定义是，若T(n)T(n)和Rn)Rn)是定义在正整数集合上的两个函数，则存在正的常数C C和n n。，使得当nNncnNnc时，总是满足总是满足OWT(n)WCOWT(n)WCRn)Rn)但是我们总是考虑在最坏情况下的时间复杂度，以保证算法的运行时 间不会比它更长。FUNCTIONNAME(spuoo(Ds=lu)6ucuna:(spuoo(Ds=lu)6ucuna:0 90 80 70 60 50 40 30 20 10 0 8 6 4 2 00 90 80 70 60 50 40 30 20 10 0 8 6 4 2 00 0clogNConstantLogarithmicLog-sq

3、uaredlinearlog2NNNlogNN?N，2可NogNQuadraticCubicExponentialExponentialInput Size(N)Input Size(N)(5)若Ti(n)-(CApuooag)(CApuooag)O OE E一-(一次)(n 次)nk)g2n+l0001og2nf丁血-亦)净3-100010既，Tn-lOWlonT4(n)=2nlofi2n-1000kg涕中,则其中渐进时间最小的是T血)&提提示示：T|(n)=nhg2n+1000iog2n=0(nlogzii),T血户nk)*3】0001d&n0(ii)，Tn户r?-1OOOlogjnKMn

4、2).Tnhlnlofcn-lOOOlQn-CXnlogzn).【练【练习12】下述函数中渐近时间最小的是嘿些？(1)TL(nhnlognH-1 OOOhgiDa 1000a 1000(2)20002000300030004000 50004000 5000T如)=nT000k)g：n600060007000 B000 9000 1000C7000 B000 9000 1000C(3)Tj(nn2-10001og2n(4)T4(n)=2nlog2n 1 OOOlogan【解】【解】I(nO(nlag)i T血)=0(扑小)T3(n)=O(n T4(n)=O(nlog2n)fl从中看到.Ti(n

5、)x T/ti)最小但Ti(nXnT000)kg2n，T4(n)=(2n-1000)log2n显然,n足够大时,Ti(n)vT4(fi)所以，渐近时间最小的是T(心0(1)Temp=i;i=j；j=temp;以上三条单个语句的频度均为法的时间复杂度为常数阶，记作复杂度是 0(1)。O(nA2)2.1.交换 i 和 j 的内容 sum=O;for(i=1:i=n;i+)for(j=1;j=n;j+)(M2 次)sum+;(nA2 次解：T(n)=2nA2+n+1=0(nA2)1,该程序段的执行时间是一个与问题规模n 无关的常数。算n 的增加此类算法的时间T(n)=0(1)。如果算法的执行时间不随

6、着问题规模而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。for(i=1;in;i+)y=y+1;for(j=0;j=(2*n);j+)解：语句 1 的频度是 n-1语句 2 的频度是(n-1)*(2n+1)=2nA2-n-1f(n)=2nA2-n-1+(n-1)=2nA2-2该程序的时间复杂度T(n)=0(nA2).0(n)a=0;b=1;for(i=1:i=n;i+)s=a+b;b=a;a=s;解：语句 1 的频度：2,语句 2 的频度：n,语句 3 的频度：n-1,语句 4 的频度：n-1,语句 5 的频度：n-1,T(n)=2+n+3(n-1)=4n-1=0(n).O

7、(log2n)2.4.i=1;while(i=n)i=i*2;解：语句 1 的频度是 1,设语句 2 的频度是 f(n),贝 U：2Af(n)=n;f(n)=log2n 取最大值 f(n)=log2n,T(n)=O(log2n)O(nA3)2.5.for(i=0;in;i+)(for(j=0;ji;j+)(for(k=0;kj;k+)x=x+2;解：当 i=m,j=k 的时候，内层循环的次数为k 当 i=m 时，j 可以取 0,1,.,m-1,所以这里最内循环共 进行了 0+1+.+m-1=(m-1)m/2 次所以,i 从 0 取到 n,则 循环共进行了：0+(1-1)*1/2+.+(n-1)

8、n/2=n(n+1)(n-1)/6 所以时间复杂度为 O(n，3).我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最O(nA2)，但期望时间是 O(nlogn)。通过每次都仔细(即 O(nA2)情况)的概率减小到几乎等于(O(nlogn)时间运行。下面是一些常用的记法：访问数组中的元素是常数时间操作，或说 O(1)操作。一个算法如果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 用 strcmp 比较两个具有 n 个字符的串需要 O(n)时间。常规的矩阵乘算法是O(nA3)，因为算出每个元素都需要将有元素的个数是 nA2。指数时间算法通常来源于需要求出所有可能结果。例如，n

9、个元素的集合共有 2n 个子集，所以要求出所有子集的算法将是运行时间加倍。不幸的是，确实有许多问题的算法替代之。坏情况运行时间是地选择基准值，我们有可能把平方情况0。在实际中，精心实现的快速排序一般都能以O(logn)时间。n 对元素相乘并加到一起，所O(2n)的。：-D-D 指数算法一般说来是太复杂了，除非 n 的值非常小，因为，在这个问题中增加一个元 素就导致(如著名的巡回售货员问题”)到目前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果常见的时间复杂度，按数量级递增排列依次为：常数阶 0(1)0(1)、对数阶 O(log2n)O(log2n)、线性阶 O(

10、n)O(n)、线性对数阶 O(nlog2n)O(nlog2n)、平方阶 0(n0(nA A2)2)、立方阶 0(n0(nA A3)3)、k k 次方阶 O(nO(nA Ak)k)、指数阶 0(25)0(25)。下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。1、设三个函数 f,g,h 分另 U 为 f(n)=100nA3+nA2+1000h(n)=nA1.5+5000nlgn请判断下列关系是否成立:(1)(2)(3)(4)f(n)=O(g(n)g(n)=O(f(n)h(n)=O(nA1.5)h(n)=O(nlgn),g(n)=25nA3+5000nA2(1)成立。题中由于两个函数的最

11、高次项都是nA3,因此当 noo 时，两个函数的比值是一个常数，所以这个关系式是成立的。(2)成立。与上同理。(3)成立。与上同理。(4)不成立。由于当 noo 时 nAl.5 比 nlgn 递增的快，所以 h(n)与 nlgn 的比值不是常数，故不成立。2、设 n 为正整数，利用大O记号，将下列程序段的执行时间表示为n 的函数。(1)i=1;k=0while(i1while(x=(y+1)*(y+1)y+;解答：T(n)=n1/2,T(n)=O(n1/2),最坏的情况是 y=0,那么循环的次数是个按平方根阶递增的函数。n1/2 次，这是一x=91;y=100;while(y0)if(x100

12、)(x=x-10;y-;else x+;解答：T(n)=O(1),这个程序看起来有点吓人，总共循环运行了没有？没。这段程序的运行是和常数阶的函数。1000 次，但是我们看到 nn 无关的，就算它再循环一万年，我们也不管他，只是一个一个经验规则有如下复杂度关系c log2N n n*Log2N nc log2N n n*Log2N n人人2 n2 n人人3 23 2人人n 3n 3人人n n!n n!其中 c 是一个常量，如果一个算法的复杂度为c、log2N、n、n*log2N，那么这个算法居时间效率比较高，如果是 2An,3An,n!，那么稍微大一些的 n 就会令这个算法不能动了，于中间的几个则差强人意。