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

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

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

2、C和n。，使得当nNnc时，总是满足 OWT(n)WCRn)但是我们总是考虑在最坏情况下的时间复杂度，以保证算法的运行时 间不会比它更长。FUNCTION NAME c Constant logN Logarithmic log2N Log-squared N linear NlogN NogN N?Quadratic N，Cubic 2可 Exponential Input Size(N)00 90 80 70 60 50 40 30 20 10 0 8 6 4 2 0(spuoo(Ds=lu)6ucuna:Input Size(N)(5)若 Ti(n)-nk)g2n+l0001og2n f

3、丁血-亦)净3-100010既，Tn-lOWlon T4(n)=2nlofi2n-1000kg涕中,则其中渐进时间最小的是T血)&提示：T|(n)=nhg2n+1000iog2n=0(nlogzii),T血户nk)*3】0001d&n0(ii)，Tn户r?-1 OOOlogjnKMn2).Tnhlnlofcn-lOOOlQn-CXnlogzn).【练习12】下述函数中渐近时间最小的是嘿些？(1)TL(nhnlognH-1 OOOhgiD(2)T如)=nT000k)g：n(3)Tj(nn2-10001og2n(4)T4(n)=2nlog2n 1 OOOlogan【解】I(nO(nlag)i T血

4、)=0(扑小)T3(n)=O(n T4(n)=O(nlog2n)fl从中看到.Ti(n)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;以上三条单个语句的频度均为 1,该程序段的执行时间是一个与问题规模 n 无关的常数。算 法的时间复杂度为常数阶，记作 T(n)=0(1)。如果算法的执行时间不随着问题规模 n 的增加 而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间 复杂度是 0(1)。O(nA2)2.

5、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)for(i=1;in;i+)y=y+1;for(j=0;j=(2*n);j+)(CApuooag)OE一-a 1000 2000 3000 4000 5000 6000 7000 B000 9000 1000C(一次)(n 次)解：语句 1 的频度是 n-1 语句 2 的频度是(n-1)*(2n+1)=2nA2-n-1 f(n)=2nA2-n-1+(n-1)=2nA2-2 该程序的时间复杂度 T(n)=0(nA2).

6、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(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

7、=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)n/2=n(n+1)(n-1)/6 所以时间复杂度为 O(n，3).我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(nA2)，但期望时间是 O(nlogn)。通过每次都仔细 地选择基准值，我们有可能把平方情况(即 O(nA2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以(

8、O(nlogn)时间运行。下面是一些常用的记法：访问数组中的元素是常数时间操作，或说 O(1)操作。一个算法如果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用 strcmp 比较两个具有 n 个字符的串需要 O(n)时间。常规的矩阵乘算法是 O(nA3)，因为算出每个元素都需要将 n 对元素相乘并加到一起，所 有元素的个数是 nA2。指数时间算法通常来源于需要求出所有可能结果。例如，n 个元素的集合共有 2n 个子集，所以要求出所有子集的算法将是 O(2n)的。：-D 指数算法一般说来是太复杂了，除非 n 的值非常小，因为，在这个问题中增加一个元 素就导致运行时间

9、加倍。不幸的是，确实有许多问题(如著名的巡回售货员问题”)到目 前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果 的算法替代之。常见的时间复杂度，按数量级递增排列依次为：常数阶 0(1)、对数阶 O(log2n)、线性阶 O(n)、线性对数阶 O(nlog2n)、平方阶 0(nA2)、立方阶 0(nA3)、k 次方阶 O(nAk)、指数阶 0(25)。下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。1、设三个函数 f,g,h 分另 U 为 f(n)=100nA3+nA2+1000,g(n)=25nA3+5000nA2 h(n)=nA1.5+5000nl

10、gn 请判断下列关系是否成立:(1)f(n)=O(g(n)(2)g(n)=O(f(n)(3)h(n)=O(nA1.5)(4)h(n)=O(nlgn)(1)成立。题中由于两个函数的最高次项都是 nA3,因此当 noo 时，两个函数的比值是 一 个常数，所以这个关系式是成立的。(2)成立。与上同理。(3)成立。与上同理。(4)不成立。由于当 noo 时 nAl.5 比 nlgn 递增的快，所以 h(n)与 nlgn 的比值不是常数，故不成立。2、设 n 为正整数，利用大O记号，将下列程序段的执行时间表示为 n 的函数。(1)i=1;k=0 while(i1 while(x=(y+1)*(y+1)y

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