返回目錄

同(tong)一(yi)問(wen)題可用不同(tong)算(suan)(suan)法(fa)(fa)解決，而(er)一(yi)個算(suan)(suan)法(fa)(fa)的(de)質(zhi)量優劣將(jiang)影響到算(suan)(suan)法(fa)(fa)乃至程(cheng)序的(de)效率。算(suan)(suan)法(fa)(fa)分(fen)析的(de)目的(de)在于選(xuan)擇合適算(suan)(suan)法(fa)(fa)和改進算(suan)(suan)法(fa)(fa)。

算法復(fu)雜(za)度(du)分(fen)為時(shi)(shi)間復(fu)雜(za)度(du)和空(kong)間復(fu)雜(za)度(du)。其作用： 時(shi)(shi)間復(fu)雜(za)度(du)是(shi)度(du)量算法執行的(de)時(shi)(shi)間長(chang)短；而空(kong)間復(fu)雜(za)度(du)是(shi)度(du)量算法所需存儲(chu)空(kong)間的(de)大小。

時間復雜度

1.時間頻度

一個算(suan)(suan)法(fa)(fa)執行(xing)所耗費(fei)(fei)的(de)時(shi)間(jian)(jian)，從理論上(shang)是不(bu)能算(suan)(suan)出來的(de)，必(bi)須(xu)上(shang)機運行(xing)測試才能知道。但我們(men)不(bu)可(ke)能也沒有必(bi)要對每個算(suan)(suan)法(fa)(fa)都上(shang)機測試，只需知道哪(na)個算(suan)(suan)法(fa)(fa)花(hua)費(fei)(fei)的(de)時(shi)間(jian)(jian)多，哪(na)個算(suan)(suan)法(fa)(fa)花(hua)費(fei)(fei)的(de)時(shi)間(jian)(jian)少就可(ke)以了(le)。并(bing)且一個算(suan)(suan)法(fa)(fa)花(hua)費(fei)(fei)的(de)時(shi)間(jian)(jian)與算(suan)(suan)法(fa)(fa)中語(yu)(yu)句(ju)的(de)執行(xing)次數(shu)，哪(na)個算(suan)(suan)法(fa)(fa)中語(yu)(yu)句(ju)執行(xing)次數(shu)多，它花(hua)費(fei)(fei)時(shi)間(jian)(jian)就多。一個算(suan)(suan)法(fa)(fa)中的(de)語(yu)(yu)句(ju)執行(xing)次數(shu)稱為語(yu)(yu)句(ju)頻度或時(shi)間(jian)(jian)頻度。記為T(n)。

2.計算方法

1. 一般情況下，算法(fa)(fa)的(de)(de)(de)(de)(de)基(ji)本(ben)操作(zuo)重復執行(xing)的(de)(de)(de)(de)(de)次(ci)(ci)數(shu)(shu)是模塊n的(de)(de)(de)(de)(de)某(mou)一個(ge)函數(shu)(shu)f（n），因此，算法(fa)(fa)的(de)(de)(de)(de)(de)時(shi)間(jian)復雜(za)度記做：T（n）=O（f（n）） 分析：隨著模塊n的(de)(de)(de)(de)(de)增(zeng)大，算法(fa)(fa)執行(xing)的(de)(de)(de)(de)(de)時(shi)間(jian)的(de)(de)(de)(de)(de)增(zeng)長率(lv)(lv)和(he)f（n）的(de)(de)(de)(de)(de)增(zeng)長率(lv)(lv)成(cheng)正比，所以f（n）越小(xiao)，算法(fa)(fa)的(de)(de)(de)(de)(de)時(shi)間(jian)復雜(za)度越低，算法(fa)(fa)的(de)(de)(de)(de)(de)效率(lv)(lv)越高(gao)。 2. 在(zai)計(ji)算時(shi)間(jian)復雜(za)度的(de)(de)(de)(de)(de)時(shi)候，先(xian)找(zhao)出算法(fa)(fa)的(de)(de)(de)(de)(de)基(ji)本(ben)操作(zuo)，然后(hou)根據相應(ying)的(de)(de)(de)(de)(de)各語句(ju)確(que)定(ding)它的(de)(de)(de)(de)(de)執行(xing)次(ci)(ci)數(shu)(shu)，再找(zhao)出T（n）的(de)(de)(de)(de)(de)同數(shu)(shu)量(liang)級(ji)（它的(de)(de)(de)(de)(de)同數(shu)(shu)量(liang)級(ji)有(you)以下：1，Log2n ，n ，nLog2n ，n的(de)(de)(de)(de)(de)平方(fang)(fang)(fang)(fang)，n的(de)(de)(de)(de)(de)三(san)(san)(san)(san)次(ci)(ci)方(fang)(fang)(fang)(fang)，2的(de)(de)(de)(de)(de)n次(ci)(ci)方(fang)(fang)(fang)(fang)，n！），找(zhao)出后(hou)，f（n）=該(gai)數(shu)(shu)量(liang)級(ji)，若T(n)/f(n)求極限可得(de)到(dao)一常(chang)數(shu)(shu)c，則時(shi)間(jian)復雜(za)度 T（n）=O（f（n）） 例：算法(fa)(fa)： for（i=1;i<=n;++i） { for(j=1;j<=n;++j) { c[ i ][ j ]=0; //該(gai)步驟屬于(yu)基(ji)本(ben)操作(zuo) 執行(xing)次(ci)(ci)數(shu)(shu)：n的(de)(de)(de)(de)(de)平方(fang)(fang)(fang)(fang) 次(ci)(ci) for(k=1;k<=n;++k) c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該(gai)步驟屬于(yu)基(ji)本(ben)操作(zuo) 執行(xing)次(ci)(ci)數(shu)(shu)：n的(de)(de)(de)(de)(de)三(san)(san)(san)(san)次(ci)(ci)方(fang)(fang)(fang)(fang) 次(ci)(ci) } } 則有(you) T（n）= n的(de)(de)(de)(de)(de)平方(fang)(fang)(fang)(fang)+n的(de)(de)(de)(de)(de)三(san)(san)(san)(san)次(ci)(ci)方(fang)(fang)(fang)(fang)，根據上面括號里的(de)(de)(de)(de)(de)同數(shu)(shu)量(liang)級(ji)，我們可以確(que)定(ding) n的(de)(de)(de)(de)(de)三(san)(san)(san)(san)次(ci)(ci)方(fang)(fang)(fang)(fang) 為(wei)T（n）的(de)(de)(de)(de)(de)同數(shu)(shu)量(liang)級(ji) 則有(you)f（n）= n的(de)(de)(de)(de)(de)三(san)(san)(san)(san)次(ci)(ci)方(fang)(fang)(fang)(fang)，然后(hou)根據T（n）/f（n）求極限可得(de)到(dao)常(chang)數(shu)(shu)c 則該(gai)算法(fa)(fa)的(de)(de)(de)(de)(de) 時(shi)間(jian)復雜(za)度：T（n）=O（n的(de)(de)(de)(de)(de)三(san)(san)(san)(san)次(ci)(ci)方(fang)(fang)(fang)(fang)）

3.分類

按數量級遞增排列，常見的(de)時(shi)間復雜度(du)有： 常數階(jie)O(1),對(dui)數階(jie)O(log2n),線(xian)性階(jie)O(n), 線(xian)性對(dui)數階(jie)O(nlog2n),平方階(jie)O(n2)，立方階(jie)O(n3),...， k次方階(jie)O(nk), 指數階(jie)O(2n) 。隨(sui)著問(wen)題規模n的(de)不斷增大，上(shang)述時(shi)間復雜度(du)不斷增大，算(suan)法的(de)執行效率越低。

與時間復(fu)雜度類似，空間復(fu)雜度是指算(suan)法在計(ji)算(suan)機內執行時所需存(cun)儲空間的(de)度量。記作: S(n)=O(f(n)) 我(wo)們一般所討論的(de)是除(chu)正常占(zhan)用內存(cun)開銷(xiao)外的(de)輔助規(gui)模。

返回目錄