算法復(fù)雜度分析29369

1、算法復(fù)雜度分析1、算法的時(shí)間性能分析(1) 算法耗費(fèi)的時(shí)間和語(yǔ)句頻度一個(gè)算法所耗費(fèi)的時(shí)間二算法屮每條語(yǔ)句的執(zhí)行時(shí)間之和毎條語(yǔ)句的執(zhí)行時(shí)間二語(yǔ)句的執(zhí)彳亍次數(shù)(即頻度(frequency count) x語(yǔ)句執(zhí)行-次所需時(shí)間 算法轉(zhuǎn)換為程序后，每條語(yǔ)句執(zhí)行一次所需的時(shí)間取決于機(jī)器的指令性能、速度以及編譯 所產(chǎn)生的代碼質(zhì)量等難以確定的因素o若耍獨(dú)立丁機(jī)器的軟、硬件系統(tǒng)來(lái)分析算法的時(shí)間耗費(fèi)，則設(shè)每條語(yǔ)句執(zhí)行一次所需的時(shí) 間均是單位時(shí)間，一個(gè)算法的時(shí)間耗費(fèi)就是該算法中所有語(yǔ)句的頻度之和。求兩個(gè)n階方陣的乘積oaxb,其算法如下：# define n 100 / n可根據(jù)需要定義，這里假定為100void

2、 matrixmultiply(int aa, int b nn, int cnn) /右邊列為各語(yǔ)句的頻度int i , j , k;(1) for(i=0; i<n; j+) n+1(2) for (j二0;j<n;j+) n(n+l)cij二0; n2(4) for (k二0; k<n; k+) n(n+l)(5) cij=cij+aik*bkj; n3該算法中所有語(yǔ)句的頻度2和(即算法的時(shí)間耗費(fèi))為：t(n)二2n'+3r?+2n+l (1. 1)分析：語(yǔ)句(1)的循環(huán)控制變量i 要增加到n,測(cè)試到i二n成立才會(huì)終止。故它的頻度是n+1。 但是它的循環(huán)體卻只能

3、執(zhí)行n次。語(yǔ)句(2)作為語(yǔ)句循環(huán)體內(nèi)的語(yǔ)句應(yīng)該執(zhí)行n次，但語(yǔ)句(2) 本身要執(zhí)行n+1次,所以語(yǔ)句的頻度是n(n+l)0同理可得語(yǔ)句(3), (4)和(5)的頻度分 別是i?, n2(n+l)和譏算法matrixmultiply的時(shí)間耗費(fèi)t(n)是矩陣階數(shù)n的函數(shù)。(2) 問(wèn)題規(guī)模和算法的時(shí)間復(fù)雜度算法求解問(wèn)題的輸入量稱(chēng)為問(wèn)題的規(guī)模(size), 一般用一個(gè)整數(shù)表示。矩陣乘積問(wèn)題的規(guī)模是矩陣的階數(shù)。 一個(gè)圖論問(wèn)題的規(guī)模則是圖中的頂點(diǎn)數(shù)或邊數(shù)。一個(gè)算法的時(shí)間復(fù)雜度(time complexity,也稱(chēng)時(shí)間復(fù)雜性)t(n)是該算法的時(shí)間耗費(fèi)， 是該算法所求解問(wèn)題規(guī)模n的函數(shù)。當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮

4、大時(shí)，吋間復(fù)雜度t(n)的數(shù)量 級(jí)(階)稱(chēng)為算法的漸進(jìn)時(shí)間復(fù)雜度。算法matrixmultidy的時(shí)間復(fù)雜度t(n) ill(l. 1)式所示,當(dāng)n趨向無(wú)窮大時(shí)，顯然有+ 3m2 + 2m +1) /= 2qco.m->00.這表明，當(dāng)n充分大時(shí)，t(n)和r?之比是一個(gè)不等于零的常數(shù)。即t(n)和r?是同階的， 或者說(shuō)t(n)和r?的數(shù)量級(jí)相同。記作t(n)=0(n3)是算法matrixmultiply的漸近時(shí)間復(fù)雜度。(3) 漸進(jìn)時(shí)間復(fù)雜度評(píng)價(jià)算法時(shí)間性能主要用算法時(shí)間復(fù)雜度的數(shù)量級(jí)(即算法的漸近時(shí)間復(fù)雜度)評(píng)價(jià)一個(gè)算法的時(shí)間性能。算法matrixmultiply的時(shí)間復(fù)雜度一般為t

5、(n)二0(r?), f(n)=n3是該算法屮語(yǔ)句(5)的頻度。 f面再舉例說(shuō)明如何求算法的時(shí)間復(fù)雜度。交換i和j的內(nèi)容。temp二i; 1二 j;j二temp;以上三條單個(gè)語(yǔ)句的頻度均為1,該程序段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)。 算法的時(shí)間復(fù)雜度為常數(shù)階，記作t(n)=0(l)o 注意：如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其執(zhí) 行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類(lèi)算法的時(shí)間復(fù)雜度是0(1)。變量計(jì)數(shù)之一：(1) x=0;y=0;(2) for(kl;k<=n:k+)(3) x+;(4) for(i=l;i<=n;i+)(5) for(j

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

7、與問(wèn)題規(guī)模n沒(méi)有直接關(guān)系， 但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)展循環(huán) 向外層分析語(yǔ)句的執(zhí)行次數(shù)：n 2 j n 2ns s z1 = z+ 1)/2 珂心+ 1)®+1)/6+啥 + 1)/2/22=1j=1 上=12=1 j=12=1則該程序段的時(shí)間復(fù)雜度為t(n)二0(r?/6+低次項(xiàng))=0(n3)。(4) 算法的時(shí)間復(fù)雜度不僅僅依賴(lài)于問(wèn)題的規(guī)模，還與輸入實(shí)例的初始狀態(tài)冇關(guān)。 在數(shù)值a0. . n-1中查找給定值k的算法大致如下：(1) i=n-l;(2) while(i>=0&&( ai !=k)(3) i;(4)

8、 return i;此算法中的語(yǔ)句(3)的頻度不僅與問(wèn)題規(guī)模n有關(guān)，還與輸入實(shí)例中a的齊元秦取值及k 的取值有關(guān)：若a屮沒(méi)冇與k相等的元素，則語(yǔ)句(3)的頻度f(wàn)(n)=n；若a的最后一個(gè)元素等于k,則語(yǔ)句(3)的頻度f(wàn)(n)是常數(shù)oo(5) 最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度最壞情況下的時(shí)間復(fù)雜度稱(chēng)最壞時(shí)間復(fù)雜度。一般不特別說(shuō)明，討論的時(shí)間復(fù)雜度均是最 壞情況下的時(shí)間復(fù)雜度。這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界，這 就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)。平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況卜s算法的期望運(yùn)行時(shí) 間。常見(jiàn)的時(shí)間復(fù)雜度按數(shù)量級(jí)遞

9、増排列依次為：常數(shù)0(1)、對(duì)數(shù)階0 (log2n).線形階0(n)、線 形對(duì)數(shù)階0 (nlog2n)、平方階0 (n2)立方階0 (n3)、k次方階0 (nk)、指數(shù)階0 (2n)?？臻g復(fù)雜度：一個(gè)算法的空間復(fù)雜度(space complexity)s(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是 問(wèn)題規(guī)模n的函數(shù)。漸近空間復(fù)雜度也常常簡(jiǎn)稱(chēng)為空間復(fù)雜度。算法的時(shí)間復(fù)雜度利空間復(fù)雜 度合稱(chēng)為算法的復(fù)雜度。補(bǔ)充：1、表示法：設(shè)f和g是定義域?yàn)樽匀粩?shù)集n上的函數(shù)f(刀)=0(gs)若存在正數(shù)c和加 使得對(duì)一切心n0有0wfa)wcg(ji)q(gs)若存在正數(shù)c和/x)使得對(duì)一切心n0有owcgs)

10、w f(n)fri) =o (g(z?)對(duì)所有正數(shù)c<l存在旳 使得對(duì)一切nno有0wfsxcgs)f(n) = ® (g()f(n)=0(g(/i)且 f(n) =q (gri)0(1)表示常數(shù)函數(shù)解釋?zhuān)侯?lèi)似于二，表示兩個(gè)函數(shù)具冇相同的數(shù)量級(jí)；()類(lèi)似于v二，表示我們的函數(shù)不會(huì)超過(guò)給 出的特定函數(shù)的數(shù)量級(jí)；q類(lèi)似丁>=,表示我們的函數(shù)至少有給出的特定兩數(shù)的數(shù)量級(jí)；。類(lèi) 似于小于，表示我們的函數(shù)-定比給出的函數(shù)數(shù)量級(jí)小；3類(lèi)似于，表示我們的函數(shù)一定比 給出的特定函數(shù)數(shù)量級(jí)大(我們寫(xiě)f(n) = q(g (n) ), f(n)就是我們所想要分析的函數(shù)，g(n)就 是一個(gè)給出

11、的特定函數(shù))。大0表示法的常用計(jì)算規(guī)則：加法規(guī)則t(ri)二 71 (/?) + 72(/?)二 <9(/1 (/?) + 0(/2 (門(mén))二0(max (/i (刀)，/2 (/?)乘法規(guī)則t(n) = 715)x72(/?) = 0( fl (n) x 0( f2 (n) =6>(/l (n) x /2 (/?)2、基線條件(base case):清單1.階乘函數(shù)的第一次嘗試int factorial(ini n)return n * factorial(n - 1); 不過(guò)，這個(gè)函數(shù)的問(wèn)題是，它會(huì)永遠(yuǎn)運(yùn)行下去，因?yàn)樗鼪](méi)育終止的地方。函數(shù)會(huì)連續(xù)不斷 地調(diào)用factorial。當(dāng)計(jì)算到零時(shí)，沒(méi)有條件來(lái)停止它，所以它會(huì)繼續(xù)調(diào)用零和負(fù)數(shù)的階乘。 因此，我們的函數(shù)需要一個(gè)條件，告訴它何時(shí)停止。由于小于1的數(shù)的階乘沒(méi)有任何意義，所以我們?cè)谟?jì)算到數(shù)字1的時(shí)候停止，并返回1的 階乘(即1)。因此，真正的遞歸函數(shù)類(lèi)似于：清單2.實(shí)際的遞歸函數(shù)int factorial(int n)if (n = 1)return 1;elseretu