数据结构时间复杂度

1、一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。n称为问题的规模，当n 不断变化时，时间频度T(ii)也会不断变化。但是有时候，我们想知道它变化时呈现什么规律。 为此，我们引入时间复杂度概念。一般情况卜，算法中基本操作重复执行的次数，是问题规模n的某个函数，用T(n) 表示。若右某个辅助函数f(n),使得当11趙近于无穷人时，T(n)/f(n)的极限值为不等丁冬的常 数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n),O(f(n)为算法的渐进时间复杂 度。时间频度不相同时，渐进时间复杂度O(f(n)有町能相同，如T(iO=M2+3ii+4与 T(ii)=4M2+

2、2ii+1它们的频度不同，但时间复杂度相同，都为O(M2)。现在我们根据一些书本上和网络上对时间复杂度概念的描述进行一卜总结：T(n),语句频度，时间频度，亦称为时间复杂度，O(f(n),渐进时间复杂度。前者T(n)是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者O(f(n) 是指当问题规模趋向无穷人时，该算法时间复杂度的数量级。当我们评价-个算法的时间性 能时，主要标准就是算法的渐近时间复杂度O(f(n),因此，在算法分析时，往往对两者不 予区分，经常是将渐近时间复杂度T(n)=O(f(n)称为时间复杂度，其中的血)一般是算法 中频度绘大的语句频度。注意：算法中语句的频度不仅与

3、问题规模有关，还与输入实例中各元素的取值相关。但是我 们总是考虑在最坏的情况卜的时间复杂度。以保证算法的运行时何不会比它更长。常见的时间复杂度，按数量级递增排列依次为：常数阶0(1)、对数阶O(log2n)或O(lbn)、线 性阶O(n)、线性对数阶O(n*log2n).平方阶O(2)、立方阶O(nT)、k次方阶O(k)、指数阶0(2九)。下面有一道题目是可以帮助同学们理解概念的：1、设三个函数 f,gji 分别为 f(n)=100*nA3+nA2+1000 , g(n)=25*iiA3+5000*nA2 , h(n)=nAl 5+5OOO*n*lgn诸判断卜列关系是否成立：(1) f(n)=

4、O(g(n) g(n)=O(f(n)(3)lXn)=O(nA1.5) h(n)=O(nlgii)这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n),这里的”O“是数学符兮，它的严格 定义是”若T(n)和f(n)是定义在正整数集合匕的两个丙数，则T(n)=O(f(ii)表示存在正常数C 和讪,使得当nnO时都满足0WT(n)WC*f(n) *(即书本中的定义)。通俗一点就是这两个 函数当整型自变量11趋向于无穷人时，两者的比值是一个不等于0的常数。 (1)成工。题中由于两个函数的最高次项都是3,因此半11一8时，两个函数的比值足一 个常数，所以这个关系式是成立的。 (2)成立。与上同理

5、。 (3)成立。与上同理。 (4)不成立。由于当D-8时1.5比屮lgn递增的快，所以h(ii)与nlgn的比值不是常数, 故不成立。理解完概念之后，就开始求算法的时间复杂度。从概念中我们知道，要求时间复朵度O(f(n),就必须要知道算法中频度最大的语句频度f(n), 那么要求最大的语句频度f(n)就必须要知道算法的语句频度T(n)o一般总的思路就是：T(n)-f(n)-X)(f(n)o有时候町以直接找到算法中频度绘人的语句，直接算出f(n),然后写出O(f(n)。也有例外情况就是很难求出语句频度T(n)的卜面会用一些例子做详细的说明：0(1)例 1： Temp=i;i=j ;j=temp:以

6、上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算 法的时间复杂度为常数阶，记作T(n)=O(l)0如果算法的执行时间不随着问题规模n的増加 而增长，即使算法中有上千条语句，其执行时间也不过是一个较人的常数。此类算法的时间 复杂度是0(1)。例 2： x=91;y=100;xxiule(yX)if(x100)x=x-10;y-;else x-h-;解答：T(n)=O(l).这个程序看起来有点吓人，总共循环运行了 1000次，但是我们看到n 没有？没。这段程序的运行是和11无关的，就算它再循环一万年，我们也不骨他，只是个 常数阶的函数。O(n)例1：i=l; k=0w

7、hile(in) k=k+10*i;i+;解答：T(n)=n-1,T(n)=O(n),这个函数是按线性阶递增的。例2： a=0； b=l;for (i=l;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 =O(n).O(nA2)例1:交换l和J的内容sum=0：(一次)fbr(i=l ;i=n;i+)(n 次)foi-(j=l;j=n;j卄)(2 次)sum；(2次)(此语句是算法中频度最大的，可直接算出f(n)=M2,得时间复杂度T(n)=O

8、(nA2)解：T(n)=2nA2+n+l =O(nA2)y=y+i;for(j=0;j=(2*n);j+)x卄；解：语句1的频度是语句 2 的频度是(n-l)*(2n+l)=2nA2-n-l f(n)=2nA2-n-l +(n-l )=2nA2-2 该程序的时间复杂度T(ii)=O(n2).O(nA3)fbr()=O;ji;j+) fbr(k=O;kj;k-H-)x=x+2;(此语句为频度最大的语句，可算出f(n)=nA3,写出时间复杂度 T(n)=O(nA3)解：当i=m, j=k的时候，内层循环的次数为k当时,j可以取,所以这里最内 循环共进行了 0+l+.+m-l=(m-l)m/2次所以

9、,1从0取到n,则循环共进行了： 0+(l-l)*l/2+.+(n-l)n/2=n(n+l)(n-l)/6 所以时间复杂度为 O(3).O(log2n )(此为例外情况，难以算出T(ii),但可以利用技巧直接算出0(f(n)o)例1：1=1； (Dwhile (i=n)1=1*2;解：语句1的频度是1,设语句 2 的频度是 f(n), 则：2Af(n)=n;f(n)0)if(x100)x=x-10;y-;else x+;解答：T(n)=O(l),这个程序看起來有点吓人，总共循环运行了 1000次，但圧我们看到11没有？没。这 段程序的运行足和n无关的.就篦它再循环一万年.我们也不竹他.只圧一个

10、常数阶的函数。O(n)例1：i=l; k=0 vhile(in) k=k-10*i;i+;解答：T(n)=n-1,T(n)=O(n),这个函数定按线性阶递增的。例2：a=0;b=l；for (i=l;i=n;i+)S=2十b;b=a;a=s;解：语句1的频度:2,语句2的频度：n.语句3的频度：n-1.语句4的频度：n-1.语句5的频度：n-1,T(n)=2*n+3(n-l )=4n-l=O(n).O(nA2)例1:交换1和J的内容$um=O： (一次)fbr(i= 1 ;i=n;i+) (n 次)fbr(j=l；j=n；j+)(2 次)sum卄：(M2次)(此语句是算法中频度最大的.可11接

11、算出f(n)=n2.得时何 T(n)=O(nT) 解：T(n)=2nA2+n+l =O(nA2)例2：for (i=l:in;i+)y=y+i;for (j=0;jn);j 卄)E：解：语句1的频度足n-1语句2的频度兄(“1广(2n十l)=22nlf(n)=2nA2-n-l ”n 1 )=2nA2-2该程序的时何复杂度T(n)=O(nA2).0(nA3)例1:fbr(i=O;in;i-+-+) fbr(j=O;ji;j-H-)fbr(k=O;kj;k-H-)x=x+2;(此语句为频度诫人的语句，町算出f(n)=n3,行出时间复杂度T(n)=O(M3)解：当i=m, j=k的时候，内层循环的次数为k -*i i=m时,j可以取0,1,ml ,所以这里最内 循环共进行了 0-Fl+.+m-l=(m-l)in/2次所以,1从0取到n,则循环共进行了： O+(l-l)*l/2+.+(n-l)ii/