⑴ 找出算法中的基本語句；
算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。
⑵ 計(jì)算基本語句的執(zhí)行次數(shù)的數(shù)量級(jí)；
只需計(jì)算基本語句執(zhí)行次數(shù)的數(shù)量級(jí)，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長率。
⑶ 用大Ο記號(hào)表示算法的時(shí)間性能。
將基本語句執(zhí)行次數(shù)的數(shù)量級(jí)放入大Ο記號(hào)中。
如果算法中包含嵌套的循環(huán)，則基本語句通常是最內(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)。
常見的算法時(shí)間復(fù)雜度由小到大依次為：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
Ο(1)表示基本語句的執(zhí)行次數(shù)是一個(gè)常數(shù)，一般來說，只要算法中不存在循環(huán)語句，其時(shí)間復(fù)雜度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項(xiàng)式時(shí)間，而Ο(2n)和Ο(n!)稱為指數(shù)時(shí)間。計(jì)算機(jī)科學(xué)家普遍認(rèn)為前者是有效算法，把這類問題稱為P類問題，而把后者稱為NP問題。
O(1)
Temp=i;i=j;j=temp;
以上三條單個(gè)語句的頻度均為1，該程序段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。如果算法的執(zhí)行時(shí) 間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時(shí)間也不過是一個(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++; ②
}
解： 語句1的頻度是n-1
語句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; ⑤
}
解： 語句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(logn )
2.4.
i=1; ①
while (i<=n)
i=i*2; ②
解： 語句1的頻度是1,
設(shè)語句2的頻度是f(n), 則：2^f(n)<=n;f(n)<=logn
取最大值f(n)= logn,
T(n)=O(logn )
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).