1、求解算法的時間復(fù)雜度的具體步驟是:找出算法中的基本語句；算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。計算基本語句的執(zhí)行次數(shù)的數(shù)量級；只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，這就意味著只要保證基本語句執(zhí)行次 數(shù)的函數(shù)中的最高次幕正確即可，可以忽略所有低次幕和最高次幕的系數(shù)。這樣 能夠簡化算法分析，并且使注意力集中在最重要的一點上：增長率。用大O記號表示算法的時間性能。將基本語句執(zhí)行次數(shù)的數(shù)量級放入大0記號中。如果算法中包含嵌套的循環(huán)，則基本語句通常是最內(nèi)層的循環(huán)體，如果算法 中包含并列的循環(huán)，則將并列循環(huán)的時間復(fù)雜度相加。例如：for (i=1; i=n; i+)x+;for

2、(i=1; i=n; i+)for (j=1; j=n; j+)x+;第一個for循環(huán)的時間復(fù)雜度為0 (n)，第二個for循環(huán)的時間復(fù)雜度為 0 (n2)，則整個算法的時間復(fù)雜度為0 (n+n2)=0 (n2)。常見的算法時間復(fù)雜度由小到大依次為：0 (1) V0 (log2n) V0 (n) 0 (nlog2n) 0 (n2) 0 (n3)V0 (2n) V 0 (n!)0 (1)表示基本語句的執(zhí)行次數(shù)是一個常數(shù)，一般來說，只要算法中不存在 循環(huán)語句，其時間復(fù)雜度就是0 (1)。0 (log2n)、0 (n)、0 (nlog2n)、0 (n2) 和0 (n3)稱為多項式時間，而0 (2n)

3、和0 (n!)稱為指數(shù)時間。計算機科學(xué)家普 遍認(rèn)為前者是有效算法，把這類問題稱為P類問題，而把后者稱為NP問題。0(1)Temp=i;i=j;j=temp;以上三條單個語句的頻度均為1，該程序段的執(zhí)行時間是一個與問題規(guī)模n無關(guān) 的常數(shù)。算法的時間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。如果算法的執(zhí)行時間 不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過0(rT2)2. 1.交換i和j的內(nèi)容sum=0；(一次)for(i=l;i=n;i+)(n 次)for(j=l;j=n;j+) (n2 次)sum+；(n”2 次)解：T(n)=2rT2+n+l =0(n”2)2. 2.f

4、or (i=l:in:i+)y=y+l;for (j=0;j二(2*n);j+)x+;解：語句1的頻度是n-1語句 2 的頻度是(n-l)*(2n+l)=2n2-n-1 f(n)=2n 2n1+ (n1)=2n 2-2該程序的時間復(fù)雜度T (n)=0 (rT2).0(n)2. 3.a=0; TOC o 1-5 h z 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-l=0(n).0(logn )2.4.i=1；while (i=n)i=i*2;解：語句1的頻度是1,設(shè)語句 2 的頻度是 f(n),貝U： 2f(n)=n;f(n)=logn 取最大值f(n)= logn, T(n)=O(logn )O(n”3)2.5.for(i=0;in;i+)(for(j=0;ji;j+)(for(k=0;kj;k+)x=x+2;解：當(dāng)i=m, j=k的時候，內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時，j可以取0,1,.,m-1 , 所以這里最內(nèi)循環(huán)共進行了 0+1+.+m-1=(m-1)m/2次