概論- 算法的描述和分析(二)

　　算法分析

　　評價算法好壞的標准

　　求解同一計算問題可能有許多不同的算法究竟如何來評價這些算法的好壞以便從中選出較好的算法呢?

　　選用的算法首先應該是正確的此外主要考慮如下三點

　　① 執行算法所耗費的時間;

　　② 執行算法所耗費的存儲空間其中主要考慮輔助存儲空間;

　　③ 算法應易於理解易於編碼易於調試等等

　　算法性能選擇

　　一個占存儲空間小運行時間短其它性能也好的算法是很難做到的原因是上述要求有時相互抵觸要節約算法的執行時間往往要以犧牲

　　更多的空間為代價;而為了節省空間可能要耗費更多的計算時間因此我們只能根據具體情況有所側重

　　① 若該程序使用次數較少則力求算法簡明易懂;

　　② 對於反復多次使用的程序應盡可能選用快速的算法;

　　③ 若待解決的問題數據量極大機器的存儲空間較小則相應算法主要考慮如何節省空間

　　算法的時間性能分析

　　()算法耗費的時間和語句頻度

　　一個算法所耗費的時間=算法中每條語句的執行時間之和

　　每條語句的執行時間=語句的執行次數(即頻度(Frequency Count))×語句執行一次所需時間

　　算法轉換為程序後每條語句執行一次所需的時間取決於機器的指令性能速度以及編譯所產生的代碼質量等難以確定的因素

　　若要獨立於機器的軟硬件系統來分析算法的時間耗費則設每條語句執行一次所需的時間均是單位時間一個算法的時間耗費就是該算法中所

　　有語句的頻度之和

　　【例】求兩個n階方陣的乘積 C=A×B其算法如下:

　　# define n // n 可根據需要定義這裡假定為

　　void MatrixMultiply(int A[a]int B [n][n]int C[n][n])

　　{ //右邊列為各語句的頻度

　　int i j k;

　　() for(i=; i

　　(2) for (j=0;j

　　(3) C[i][j]=0; n 2

　　(4) for (k=0; k

　　(5) C[i][j]=C[i][j]+A[i][k]*B[k][j]; n 3

　　}

　　}

　　該算法中所有語句的頻度之和(即算法的時間耗費)為：

　　T(n)=2n 3 +3n 2 +2n+1 (1.1)

　　分析：

　　語句(1)的循環控制變量i要增加到n，測試到i=n成立才會終止。tw.winGwit.Com故它的頻度是n+1。但是它的循環體卻只能執行n次。語句(2)作為語句(1)循

　　環體內的語句應該執行n次，但語句(2)本身要執行n+1次，所以語句(2)的頻度是n(n+1)。同理可得語句(3)，(4)和(5)的頻度分別是n 2 ，n 2

　　(n+1)和n 3 。

　　算法MatrixMultiply的時間耗費T(n)是矩陣階數n的函數。

　　(2)問題規模和算法的時間復雜度

　　算法求解問題的輸入量稱為問題的規模(Size),一般用一個整數表示。

　　【例3.4】矩陣乘積問題的規模是矩陣的階數。

　　【例3.5】一個圖論問題的規模則是圖中的頂點數或邊數。

　　一個算法的時間復雜度(Time Complexity, 也稱時間復雜性)T(n)是該算法的時間耗費，是該算法所求解問題規模n的函數。當問題的規模

　　n趨向無窮大時，時間復雜度T(n)的數量級(階)稱為算法的漸進時間復雜度。

　　【例3.6】算法MatrixMultidy的時間復雜度T(n)如(1.1)式所示，當n趨向無窮大時，顯然有

　　

　　這表明，當n充分大時，T(n)和n 3 之比是一個不等於零的常數。即T(n)和n 3 是同階的，或者說T(n)和n 3 的數量級相同。記作T(n)=O(n 3

　　)是算法MatrixMultiply的漸近時間復雜度。

　　數學符號"O"的嚴格的數學定義：

　　若T(n)和f(n)是定義在正整數集合上的兩個函數，則T(n)=O(f(n))表示存在正的常數C和n0，使得當n≥n0時都滿足0≤T(n)≤C·f(n)。

From:http://tw.wingwit.com/Article/program/sjjg/201311/23403.html