|
算法分析 1．評(píng)價(jià)算法好壞的標(biāo)準(zhǔn) 求解同一計(jì)算問(wèn)題可能有許多不同的算法，究竟如何來(lái)評(píng)價(jià)這些算法的好壞以便從中選出較好的算法呢？ 選用的算法首先應(yīng)該是"正確"的。此外，主要考慮如下三點(diǎn)： ① 執(zhí)行算法所耗費(fèi)的時(shí)間； ② 執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間； ③ 算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。 2．算法性能選擇 一個(gè)占存儲(chǔ)空間小、運(yùn)行時(shí)間短、其它性能也好的算法是很難做到的。原因是上述要求有時(shí)相互抵觸：要節(jié)約算法的執(zhí)行時(shí)間往往要以犧牲更多的空間為代價(jià)；而為了節(jié)省空間可能要耗費(fèi)更多的計(jì)算時(shí)間。因此我們只能根據(jù)具體情況有所側(cè)重： ① 若該程序使用次數(shù)較少，則力求算法簡(jiǎn)明易懂； ② 對(duì)于反復(fù)多次使用的程序，應(yīng)盡可能選用快速的算法； ③ 若待解決的問(wèn)題數(shù)據(jù)量極大，機(jī)器的存儲(chǔ)空間較小，則相應(yīng)算法主要考慮如何節(jié)省空間。 3．算法的時(shí)間性能分析 （1）算法耗費(fèi)的時(shí)間和語(yǔ)句頻度 一個(gè)算法所耗費(fèi)的時(shí)間=算法中每條語(yǔ)句的執(zhí)行時(shí)間之和 每條語(yǔ)句的執(zhí)行時(shí)間=語(yǔ)句的執(zhí)行次數(shù)(即頻度(Frequency Count))×語(yǔ)句執(zhí)行一次所需時(shí)間 算法轉(zhuǎn)換為程序后，每條語(yǔ)句執(zhí)行一次所需的時(shí)間取決于機(jī)器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量等難以確定的因素。 若要獨(dú)立于機(jī)器的軟、硬件系統(tǒng)來(lái)分析算法的時(shí)間耗費(fèi)，則設(shè)每條語(yǔ)句執(zhí)行一次所需的時(shí)間均是單位時(shí)間，一個(gè)算法的時(shí)間耗費(fèi)就是該算法中所有語(yǔ)句的頻度之和。 【例3.3】求兩個(gè)n階方陣的乘積 C=A×B,其算法如下: # define n 100 // n 可根據(jù)需要定義,這里假定為100 void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n]) { //右邊列為各語(yǔ)句的頻度 int i ,j ,k; (1) for(i=0; i＜n;j++) n+1 (2) for (j=0;j＜n;j++) { n(n+1) (3) C[i][j]=0; n2 (4) for (k=0; k＜n; k++) n2(n+1) (5) C[i][j]=C[i][j]+A[i][k]*B[k][j]; n3 } } 該算法中所有語(yǔ)句的頻度之和(即算法的時(shí)間耗費(fèi))為： T(n)=2n3+3n2+2n+1 (1.1) 分析： 語(yǔ)句(1)的循環(huán)控制變量i要增加到n，測(cè)試到i=n成立才會(huì)終止。故它的頻度是n+1。但是它的循環(huán)體卻只能執(zhí)行n次。語(yǔ)句(2)作為語(yǔ)句(1)循 環(huán)體內(nèi)的語(yǔ)句應(yīng)該執(zhí)行n次，但語(yǔ)句(2)本身要執(zhí)行n+1次，所以語(yǔ)句(2)的頻度是n(n+1)。同理可得語(yǔ)句(3)，(4)和(5)的頻度分別是n2，n2(n+1)和n3。 算法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ù)表示。 【例3．4】矩陣乘積問(wèn)題的規(guī)模是矩陣的階數(shù)。 【例3．5】一個(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ú)窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱(chēng)為算法的漸進(jìn)時(shí)間復(fù)雜度。 【例3．6】算法MatrixMultidy的時(shí)間復(fù)雜度T(n)如(1.1)式所示，當(dāng)n趨向無(wú)窮大時(shí)，顯然有  這表明，當(dāng)n充分大時(shí)，T(n)和n3之比是一個(gè)不等于零的常數(shù)。即T(n)和n3是同階的，或者說(shuō)T(n)和n3的數(shù)量級(jí)相同。記作T(n)=O(n3)是算法MatrixMultiply的漸近時(shí)間復(fù)雜度。 數(shù)學(xué)符號(hào)"O"的嚴(yán)格的數(shù)學(xué)定義： 若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則T(n)=O(f(n))表示存在正的常數(shù)C和n0，使得當(dāng)n≥n0時(shí)都滿(mǎn)足0≤T(n)≤C·f(n)。 （3）漸進(jìn)時(shí)間復(fù)雜度評(píng)價(jià)算法時(shí)間性能 主要用算法時(shí)間復(fù)雜度的數(shù)量級(jí)(即算法的漸近時(shí)間復(fù)雜度)評(píng)價(jià)一個(gè)算法的時(shí)間性能。 【例3．7】有兩個(gè)算法A1和A2求解同一問(wèn)題，時(shí)間復(fù)雜度分別是T1(n)=100n2，T2(n)=5n3。 （1）當(dāng)輸入量n＜20時(shí)，有T1(n)＞T2(n)，后者花費(fèi)的時(shí)間較少。 （2）隨著問(wèn)題規(guī)模n的增大，兩個(gè)算法的時(shí)間開(kāi)銷(xiāo)之比5n3/100n2=n/20亦隨著增大。即當(dāng)問(wèn)題規(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)稱(chēng)為時(shí)間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語(yǔ)句頻度。 【例3．8】算法MatrixMultiply的時(shí)間復(fù)雜度一般為T(mén)(n)=O(n3)，f(n)=n3是該算法中語(yǔ)句(5)的頻度。下面再舉例說(shuō)明如何求算法的時(shí)間復(fù)雜度。 【例3．9】交換i和j的內(nèi)容。 Temp=i; i=j; j=temp; 以上三條單個(gè)語(yǔ)句的頻度均為1，該程序段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。 如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類(lèi)算法的時(shí)間復(fù)雜度是O(1)。 【例3．10】變量計(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++; 一般情況下，對(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(mén)(n)=O(n2)。 當(dāng)有若干個(gè)循環(huán)語(yǔ)句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的頻度f(wàn)(n)決定的。 【例3．11】變量計(jì)數(shù)之二。 (1) x=1; (2) for(i=1;i<=n;i++) (3) for(j=1;j<=i;j++) (4) for(k=1;k<=j;k++) (5) x++; 該程序段中頻度最大的語(yǔ)句是(5)，內(nèi)循環(huán)的執(zhí)行次數(shù)雖然與問(wèn)題規(guī)模n沒(méi)有直接關(guān)系，但是卻與外層循環(huán)的變量取值有關(guān)，而最外層循環(huán)的次數(shù)直接與n有關(guān)，因此可以從內(nèi)層循環(huán)向外層分析語(yǔ)句(5)的執(zhí)行次數(shù)： 
則該程序段的時(shí)間復(fù)雜度為T(mén)(n)=O(n3/6+低次項(xiàng))=O(n3)。 （4）算法的時(shí)間復(fù)雜度不僅僅依賴(lài)于問(wèn)題的規(guī)模，還與輸入實(shí)例的初始狀態(tài)有關(guān)。 【例3．12】在數(shù)值A(chǔ)[0..n-1]中查找給定值K的算法大致如下： (1)i=n-1; (2)while(i>=0&&(A[i]!=k)) (3) i--; (4)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ù)0。 （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)。 【例3．19】查找算法【例1·8】在最壞情況下的時(shí)間復(fù)雜度為T(mén)(n)=0(n)，它表示對(duì)于任何輸入實(shí)例,該算法的運(yùn)行時(shí)間不可能大于0(n)。 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。 常見(jiàn)的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)0(1)、對(duì)數(shù)階0(log2n)、線(xiàn)形階0(n)、線(xiàn)形對(duì)數(shù)階0(nlog2n)、平方階0(n2)立方階0(n3)、…、k次方階0(nk)、指數(shù)階0(2n)。顯然，時(shí)間復(fù)雜度為指數(shù)階0(2n)的算法效率極低，當(dāng)n值稍大時(shí)就無(wú)法應(yīng)用。 類(lèi)似于時(shí)間復(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ù)雜度。 |
|
|
來(lái)自： moonboat > 《datastructure》
