時(shí)間復(fù)雜度的計(jì)算

1、時(shí)間復(fù)雜度計(jì)算學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)，覺得時(shí)間復(fù)雜度計(jì)算很復(fù)雜，怎么也看不懂，差不多三年之后，還是不懂，馬上就要找工作了，趕緊惡補(bǔ)一下吧：首先了解一下幾個(gè)概念。一個(gè)是時(shí)間復(fù)雜度，一個(gè)是漸近時(shí)間復(fù)雜度。前者是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)，而后者是指當(dāng)問題規(guī)模趨向無窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。當(dāng)我們?cè)u(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度，因此，在算法分析時(shí)，往往對(duì)兩者不予區(qū)分，經(jīng)常是將漸近時(shí)間復(fù)雜度T(n)=O(f(n)簡(jiǎn)稱為時(shí)間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語句頻度。此外，算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。

2、但是我們總是考慮在最壞的情況下的時(shí)間復(fù)雜度。以保證算法的運(yùn)行時(shí)間不會(huì)比它更長(zhǎng)。常見的時(shí)間復(fù)雜度，按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、k次方階O(nk)、指數(shù)階O(2n)。1. 大O表示法定義設(shè)一個(gè)程序的時(shí)間復(fù)雜度用一個(gè)函數(shù) T(n) 來表示，對(duì)于一個(gè)查找算法，如下： int seqsearch( int a, const int n, const int x) int i = 0; for (; ai != x && i < n ; i+ ); if ( i =

3、n) return -1; else return i; 這個(gè)程序是將輸入的數(shù)值順序地與數(shù)組中地元素逐個(gè)比較，找出與之相等地元素。 在第一個(gè)元素就找到需要比較一次，在第二個(gè)元素找到需要比較2次，在第n個(gè)元素找到需要比較n次。對(duì)于有n個(gè)元素的數(shù)組，如果每個(gè)元素被找到的概率相等，那么查找成功的平均比較次數(shù)為: f(n) = 1/n (n + (n-1) + (n-2) + . + 1) = (n+1)/2 = O(n) 這就是傳說中的大O函數(shù)的原始定義。用大O來表述 要全面分析一個(gè)算法，需要考慮算法在最壞和最好的情況下的時(shí)間代價(jià)，和在平均情況下的時(shí)間代價(jià)。對(duì)于最壞情況，采用大O表示法的一般提法（注

4、意，這里用的是“一般提法”）是：當(dāng)且僅當(dāng)存在正整數(shù)c和n0,使得 T(n) <= c*f(n)對(duì)于所有的n >= n0 都成立。則稱該算法的漸進(jìn)時(shí)間復(fù)雜度為T(n) = O(f(n)。這個(gè)應(yīng)該是高等數(shù)學(xué)里面的第一章極限里面的知識(shí)。這里f(n) = (n+1)/2, 那么c * f(n)也就是一個(gè)一次函數(shù)。就是在圖象上看就是如果這個(gè)函數(shù)在c*f(n)的下面，就是復(fù)雜度為T(n) = O(f(n)。對(duì)于對(duì)數(shù)級(jí)，我們用大O記法記為O(log2N)就可以了。規(guī)則1） 加法規(guī)則 T(n,m) = T1(n) + T2(n) = O ( max (f(n), g(m) ) 2) 乘法規(guī)則 T(

5、n,m) = T1(n) * T2(m) = O (f(n) * g(m) 3)一個(gè)特例 在大O表示法里面有一個(gè)特例，如果T1(n) O©， c是一個(gè)與n無關(guān)的任意常數(shù)，T2(n) = O ( f(n) ) 則有 T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) ). 也就是說，在大O表示法中，任何非0正常數(shù)都屬于同一數(shù)量級(jí)，記為O(1)。 4)一個(gè)經(jīng)驗(yàn)規(guī)則 有如下復(fù)雜度關(guān)系 c < log2N < n < n * Log2N < n2 < n3 < 2n < 3n < n! 其中c是一個(gè)常量，

6、如果一個(gè)算法的復(fù)雜度為c 、 log2N 、n 、 n*log2N ,那么這個(gè)算法時(shí)間效率比較高 ，如果是 2n , 3n ,n!,那么稍微大一些的n就會(huì)令這個(gè)算法不能動(dòng)了，居于中間的幾個(gè)則差強(qiáng)人意.1）基本知識(shí)點(diǎn)：沒有循環(huán)的一段程序的復(fù)雜度是常數(shù)，一層循環(huán)的復(fù)雜度是O(n),兩層循環(huán)的復(fù)雜度是O(n2)? （我用2表示平方，同理 3表示立方）；2）二維矩陣的標(biāo)準(zhǔn)差，殘差，信息熵，fft2,dwt2,dct2的時(shí)間復(fù)雜度: 標(biāo)準(zhǔn)差和殘差可能O(n)，F(xiàn)FT2是O(nlog(n)，DWT2可能也是O(nlog(n)；信息熵要求概率，而dct的過程和jpeg一樣。因?yàn)楹蚸peg一樣,對(duì)二難矩陣處理

7、了.Y=T*X*T'，Z=Y.*Mask，這樣子,還有分成8*8子圖像了;3)example：1、設(shè)三個(gè)函數(shù)f,g,h分別為 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn請(qǐng)判斷下列關(guān)系是否成立：（1） f(n)=O(g(n)（2） g(n)=O(f(n)（3） h(n)=O(n1.5)（4） h(n)=O(nlgn)這里我們復(fù)習(xí)一下漸近時(shí)間復(fù)雜度的表示法T(n)=O(f(n)，這里的"O"是數(shù)學(xué)符號(hào)，它的嚴(yán)格定義是"若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則T(n)=O(f

8、(n)表示存在正的常數(shù)C和n0 ,使得當(dāng)nn0時(shí)都滿足0T(n)C?f(n)。"用容易理解的話說就是這兩個(gè)函數(shù)當(dāng)整型自變量n趨向于無窮大時(shí)，兩者的比值是一個(gè)不等于0的常數(shù)。這么一來，就好計(jì)算了吧。 (1)成立。題中由于兩個(gè)函數(shù)的最高次項(xiàng)都是n3,因此當(dāng)n時(shí)，兩個(gè)函數(shù)的比值是一個(gè)常數(shù)，所以這個(gè)關(guān)系式是成立的。 （2）成立。與上同理。 （3）成立。與上同理。 （4）不成立。由于當(dāng)n時(shí)n1.5比nlgn遞增的快，所以h(n)與nlgn的比值不是常數(shù)，故不成立。2、設(shè)n為正整數(shù)，利用大"O"記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。(1) i=1; k=0while(i

9、<n) k=k+10*i;i+;解答：T(n)=n-1， T(n)=O(n)， 這個(gè)函數(shù)是按線性階遞增的。(2) x=n; / n>1while (x>=(y+1)*(y+1)y+;解答：T(n)=n1/2 ，T(n)=O(n1/2)，最壞的情況是y=0，那么循環(huán)的次數(shù)是n1/2次，這是一個(gè)按平方根階遞增的函數(shù)。(3) x=91; y=100;while(y>0)if(x>100)x=x-10;y-;else x+;解答： T(n)=O(1)，這個(gè)程序看起來有點(diǎn)嚇人，總共循環(huán)運(yùn)行了1000次，但是我們看到n沒有? 沒。這段程序的運(yùn)行是和n無關(guān)的，就算它再循環(huán)一萬年

10、，我們也不管他，只是一個(gè)常數(shù)階的函數(shù)。同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量?jī)?yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。 1、時(shí)間復(fù)雜度（1）時(shí)間頻度一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度。記為T(n)。（2）時(shí)間復(fù)雜度在剛才提到的

11、時(shí)間頻度中，n稱為問題的規(guī)模，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此，我們引入時(shí)間復(fù)雜度概念。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時(shí)，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=(f(n),稱(f(n) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。在各種不同算法中，若算法中語句執(zhí)行次數(shù)為一個(gè)常數(shù)，則時(shí)間復(fù)雜度為O(1),另外，在時(shí)間頻度不相同時(shí)，時(shí)間復(fù)雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n

12、2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同，都為O(n2)。按數(shù)量級(jí)遞增排列，常見的時(shí)間復(fù)雜度有：常數(shù)階O(1),對(duì)數(shù)階O(log2n),線性階O(n),線性對(duì)數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),.，k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。2、空間復(fù)雜度 與時(shí)間復(fù)雜度類似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量。記作:S(n)=O(f(n)我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲(chǔ)單元規(guī)模。討論方法與時(shí)間復(fù)雜度類似，不再贅述。（3）漸進(jìn)時(shí)間復(fù)雜度評(píng)價(jià)算法時(shí)間性能主要用算法時(shí)間復(fù)雜度

13、的數(shù)量級(jí)(即算法的漸近時(shí)間復(fù)雜度)評(píng)價(jià)一個(gè)算法的時(shí)間性能?！纠?7】有兩個(gè)算法A1和A2求解同一問題，時(shí)間復(fù)雜度分別是T1(n)=100n2，T2(n)=5n3。（1）當(dāng)輸入量n20時(shí)，有T1(n)T2(n)，后者花費(fèi)的時(shí)間較少。（2）隨著問題規(guī)模n的增大，兩個(gè)算法的時(shí)間開銷之比5n3/100n2=n/20亦隨著增大。即當(dāng)問題規(guī)模較大時(shí)，算法A1比算法A2要有效地多。它們的漸近時(shí)間復(fù)雜度O(n2)和O(n3)從宏觀上評(píng)價(jià)了這兩個(gè)算法在時(shí)間方面的質(zhì)量。在算法分析時(shí)，往往對(duì)算法的時(shí)間復(fù)雜度和漸近時(shí)間復(fù)雜度不予區(qū)分，而經(jīng)常是將漸近時(shí)間復(fù)雜度T(n)=O(f(n)簡(jiǎn)稱為時(shí)間復(fù)雜度，其中的f(n)一般是

14、算法中頻度最大的語句頻度?！纠?8】算法MatrixMultiply的時(shí)間復(fù)雜度一般為T(n)=O(n3)，f(n)=n3是該算法中語句(5)的頻度。下面再舉例說明如何求算法的時(shí)間復(fù)雜度?！纠?9】交換i和j的內(nèi)容。      Temp=i;      i=j;      j=temp;以上三條單個(gè)語句的頻度均為1，該程序段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。   

15、;   如果算法的執(zhí)行時(shí)間不隨著問題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語句，其執(zhí)行時(shí)間也不過是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O(1)。【例310】變量計(jì)數(shù)之一。(1) x=0;y=0;(2) for(k-1;k<=n;k+)(3)     x+;(4) for(i=1;i<=n;i+)(5)       for(j=1;j<=n;j+)(6)         y+;一

16、般情況下，對(duì)步進(jìn)循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，忽略該語句中步長(zhǎng)加1、終值判別、控制轉(zhuǎn)移等成分。因此，以上程序段中頻度最大的語句是(6)，其頻度為f(n)=n2，所以該程序段的時(shí)間復(fù)雜度為T(n)=O(n2)。當(dāng)有若干個(gè)循環(huán)語句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的?！纠?11】變量計(jì)數(shù)之二。(1) x=1;(2) for(i=1;i<=n;i+)(3)       for(j=1;j<=i;j+)(4)      

17、     for(k=1;k<=j;k+)(5)               x+;該程序段中頻度最大的語句是(5)，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問題規(guī)模n沒有直接關(guān)系，但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)層循環(huán)向外層分析語句(5)的執(zhí)行次數(shù)：則該程序段的時(shí)間復(fù)雜度為T(n)=O(n3/6+低次項(xiàng))=O(n3)。（4）算法的時(shí)間復(fù)雜度不僅僅依賴于問題的規(guī)模，還與輸入實(shí)例的初始狀

18、態(tài)有關(guān)?！纠?12】在數(shù)值A(chǔ)0.n-1中查找給定值K的算法大致如下：   (1)i=n-1;          (2)while(i>=0&&(Ai!=k)      (3)     i-;      (4)return i;       此算法中的語句(3)的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實(shí)例中A的各元素取值及K的取值有關(guān):若A中沒有與K相等的元素，則語句(3)的頻度f(n)=n；若A的最后一個(gè)元素等于K,則語句(3)的頻度f(n)是常數(shù)0。（5）