算法復(fù)雜度的分析方法及其運(yùn)用

        算法復(fù)雜度是在《數(shù)據(jù)結(jié)構(gòu)》這門課程的第一章里出現(xiàn)的，因?yàn)樗晕⑸婕暗揭恍?shù)學(xué)問題，所以很多同學(xué)感覺很難，加上這個概念也不是那么具體，更讓許多人復(fù)習(xí)起來無從下手，下面我們就這個問題給各位考生進(jìn)行分析。

首先了解一下幾個概念。

一個是時間復(fù)雜度，

一個是漸近時間復(fù)雜度。

前者是某個算法的時間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)，而后者是指當(dāng)問題規(guī)模趨向無窮大時，該算法時間復(fù)雜度的數(shù)量級。

當(dāng)我們評價一個算法的時間性能時，主要標(biāo)準(zhǔn)就是算法的漸近時間復(fù)雜度，因此，在算法分析時，往往對兩者不予區(qū)分，經(jīng)常是將漸近時間復(fù)雜度T(n)=O(f(n))簡稱為時間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語句頻度。

此外，算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。但是我們總是考慮在最壞的情況下的時 間復(fù)雜度。以保證算法的運(yùn)行時 間不會比它更長。

常見的時 間復(fù)雜度，按數(shù)量級遞增排列依次為：

•     常數(shù)階O(1)

•     對數(shù)階O(log2n)

•     線性階O(n)

•     線性對數(shù)階O(nlog2n)

•     平方階O(n^2)

•     立方階O(n^3)

•     k次方階O(n^k)

•     指數(shù)階O(2^n)

下面我們通過例子加以說明，讓大家碰到問題時知道如何去解決。

1、設(shè)三個函數(shù)f,g,h分別為 f(n)=100n^3 n^2 1000 , g(n)=25n^3 5000n^2 , h(n)=n^1.5 5000nlgn

請判斷下列關(guān)系是否成立：
（1） f(n)=O(g(n))
（2） g(n)=O(f(n))
（3） h(n)=O(n^1.5)
（4） h(n)=O(nlgn)

這里我們復(fù)習(xí)一下漸近時 間復(fù)雜度的表示法T(n)=O(f(n))，這里的"O"是數(shù)學(xué)符號，它的嚴(yán)格定義是"若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=O(f(n))表示存在正的常數(shù)C和n0 ,使得當(dāng)n≥n0時都滿足0≤T(n)≤C?f(n)。"用容易理解的話說就是這兩個函數(shù)當(dāng)整型自變量n趨向于無窮大時，兩者的比值是一個不等于0的常數(shù)。這么一來，就好計(jì)算了吧。

◆ (1)成立。題中由于兩個函數(shù)的最高次項(xiàng)都是n^3,因此當(dāng)n→∞時，兩個函數(shù)的比值是一個常數(shù)，所以這個關(guān)系式是成立的。
◆ （2）成立。與上同理。
◆ （3）成立。與上同理。
◆ （4）不成立。由于當(dāng)n→∞時n^1.5比nlgn遞增的快，所以h(n)與nlgn的比值不是常數(shù)，故不成立。

2、設(shè)n為正整數(shù)，利用大"O"記號，將下列程序段的執(zhí)行時 間表示為n的函數(shù)。
(1) i=1; k=0
while(i<n)
{ k=k 10*i;i ;
}
解答：T(n)=n-1， T(n)=O(n)， 這個函數(shù)是按線性階遞增的。

(2) x=n; // n>1
while (x>=(y 1)*(y 1))
y ;
解答：T(n)=n1/2 ，T(n)=O(n1/2)， 最壞的情況是y=0，那么循環(huán)的次數(shù)是n1/2次，這是一個按平方根階遞增的函數(shù)。

(3) x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x ;
解答：T(n)=O(1)， 這個程序看起來有點(diǎn)嚇人，總共循環(huán)運(yùn)行了1000次，但是我們看到n沒有? 沒。這段程序的運(yùn)行是和n無關(guān)的，就算它再循環(huán)一萬年，我們也不管他，只是一個常數(shù)階的函數(shù)。