求解算法的時(shí)間復(fù)雜度的具體步驟是：
⑴ 找出算法中的基本語(yǔ)句；
算法中執(zhí)行次數(shù)最多的那條語(yǔ)句就是基本語(yǔ)句，通常是最內(nèi)層循環(huán)的循環(huán)體。
⑵ 計(jì)算基本語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)；
只需計(jì)算基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)，這就意味著只要保證基本語(yǔ)句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡(jiǎn)化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率。
⑶ 用大Ο記號(hào)表示算法的時(shí)間性能。
將基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)放入大Ο記號(hào)中。
如果算法中包含嵌套的循環(huán)，則基本語(yǔ)句通常是最內(nèi)層的循環(huán)體，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時(shí)間復(fù)雜度相加。例如：
for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
第一個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n)，第二個(gè)for循環(huán)的時(shí)間復(fù)雜度為Ο(n2)，則整個(gè)算法的時(shí)間復(fù)雜度為Ο(n+n2)=Ο(n2)。
常見(jiàn)的算法時(shí)間復(fù)雜度由小到大依次為：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
Ο(1)表示基本語(yǔ)句的執(zhí)行次數(shù)是一個(gè)常數(shù)，一般來(lái)說(shuō)，只要算法中不存在循環(huán)語(yǔ)句，其時(shí)間復(fù)雜度就是Ο(1)。Ο(log2n)、Ο(n)、
Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項(xiàng)式時(shí)間，而Ο(2n)和Ο(n!)稱為指數(shù)時(shí)間。計(jì)算機(jī)科學(xué)家普遍認(rèn)為前者是有效算法，把這類問(wèn)題稱
為P類問(wèn)題，而把后者稱為NP問(wèn)題。
O(1)
Temp=i;i=j;j=temp;
以
上三條單個(gè)語(yǔ)句的頻度均為1，該程序段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。如果算法的執(zhí)行時(shí)
間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O(1)。
O(n^2)
2.1. 交換i和j的內(nèi)容
sum=0； （一次）
for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n^2次 ）
sum++； （n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)
2.2.
for (i=1;i<n;i++)
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解： 語(yǔ)句1的頻度是n-1
語(yǔ)句2的頻度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
該程序的時(shí)間復(fù)雜度T(n)=O(n^2).
O(n)
2.3.
a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b; ③
b=a; ④
a=s; ⑤
}
解： 語(yǔ)句1的頻度：2,
語(yǔ)句2的頻度： n,
語(yǔ)句3的頻度： n-1,
語(yǔ)句4的頻度：n-1,
語(yǔ)句5的頻度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).
O(log2n)
2.4.
i=1;
①
while
(i<=n)
i=i*2;
②
解： 語(yǔ)句1的頻度是1,
設(shè)語(yǔ)句2的頻度是f(n),
則：2^f(n)<=n;f(n)<=log2n
取最大值f(n)=
log2n,
T(n)=O(log2n )
O(n^3)
2.5.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解：
當(dāng)i=m, j=k的時(shí)候,內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時(shí), j 可以取 0,1,...,m-1 ,
所以這里最內(nèi)循環(huán)共進(jìn)行了0+1+...+m-1=(m-1)m/2次所以,i從0取到n, 則循環(huán)共進(jìn)行了:
0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以時(shí)間復(fù)雜度為O(n^3).
一個(gè)經(jīng)驗(yàn)規(guī)則
有如下復(fù)雜度關(guān)系
c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!
其中c是一個(gè)常量，如果一個(gè)算法的復(fù)雜度為c 、 log2N 、n 、 n*log2N ,那么這個(gè)算法時(shí)間效率比較高 ，如果是 2^n , 3^n ,n!，那么稍微大一些的n就會(huì)令這個(gè)算法不能動(dòng)了，居于中間的幾個(gè)則差強(qiáng)人意。