时间复杂度复习资料

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) wc ?rn)但是我们总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。functionnamecconstantlognlogarithmiclog2nlog-squarednlinearnlognnognn?quadraticn，cubic2可exponentialinput 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&n?0(ii)， t?n户r?-1 ooologjnkmn2). tnhlnlofcn- looolqn-cxnlogzn). 【练 习12】 下述函数中渐近时间最小的是嘿些？(1)tl(nhnlognh-1 ooohgid (2)t如)=n?t000k)g：n (3)tj(nn2-10001og2n (4)t4(n)=2nlog2n 1 oo

4、ologan 【解】i (no(nlag)i t血)=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 的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的

5、常数。此类算法的时间复杂度是 0(1) 。o(na2) (capuooag)oe一-a 1000 2000 3000 4000 5000 6000 7000 b000 9000 1000c 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) 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-1 f(n)=2na2-n-1 +

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

7、log2n ) ( 一次) (n 次) 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)n/2=n(n+1)(n-1)/6 所以时间复杂度为o(n，3). 我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最坏情况运行时间是o(na2) ，但期望

8、时间是o(nlogn) 。通过每次都仔细地选择基准值，我们有可能把平方情况(即 o(na2) 情况) 的概率减小到几乎等于0。在实际中，精心实现的快速排序一般都能以(o(nlogn) 时间运行。下面是一些常用的记法： 访问数组中的元素是常数时间操作，或说o(1)操作。 一个算法如果能在每个步骤去掉一半数据元素，如二分检索，通常它就取o(logn) 时间。 用 strcmp 比较两个具有n 个字符的串需要o(n)时间。 常规的矩阵乘算法是o(na3) ，因为算出每个元素都需要将n 对元素相乘并加到一起，所有元素的个数是na2。 指数时间算法通常来源于需要求出所有可能结果。例如， n 个元素的集合

9、共有2n 个子集，所以要求出所有子集的算法将是o(2n) 的。：-d 指数算法一般说来是太复杂了，除非n 的值非常小，因为，在这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题( 如著名的巡回售货员问题”)到目前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果的算法替代之。常见的时间复杂度，按数量级递增排列依次为：常数阶 0(1) 、对数阶 o(log2n) 、线性阶 o(n) 、 线性对数阶o(nlog2n) 、平方阶 0(na2)、立方阶 0(na3)、k 次方阶 o(nak)、指数阶0(25) 。 下面我们通过例子加以说明，让大家碰到问题时知

10、道如何去解决。1、设三个函数f,g,h 分另 u 为 f(n)=100na3+na2+1000 , g(n)=25na3+5000na2 h(n)=na1.5+5000nlgn 请判断下列关系是否成立: (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) 与 n

11、lgn 的比值不是常数，故不成立。2、设 n 为正整数，利用大 o记号，将下列程序段的执行时间表示为n 的函数。(1) i=1; k=0 while(i1 while (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) (x=x-10;y-; else x+; 解答： t(n)=o(1), 这个程序看起来有点吓人，总共循环运行了1000 次，但是我们看到n没有？没。这段程序的运行是和n 无关的，就算它再循环一万年，我们也不管他，