1.3 算法的描述和算法分析

1.3.1 算法的描述

算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每條指令表示一個或多個操作。一個算法具有以下5個重要的特性。

1. 有窮性

一個算法必須總是在執行有窮步（對任何合法的輸入值）之后，且每一步都可在有窮時間內完成。即一個算法對于任意一組合法輸入值，在執行有窮步之后一定能夠結束。

2. 確定性

算法中每一條指令都必須有確切的含義，使讀者在理解時不會產生二義性。同時，在任何條件下，算法都只有一條執行路徑，即對于相同的輸入只能得出相同的結果。

3. 可行性

算法中所描述的操作必須足夠基本，且都可以通過已經實現的基本操作執行有限次來實現。

4. 輸入

作為算法加工對象的量值，一個算法有0個或多個輸入。有的量值需要在算法執行過程中輸入，而有的算法表面上沒有輸入，實際上已經被嵌入算法中。

5. 輸出

輸出是一組同“輸入”有確定對應關系的量值，是算法進行信息加工后所得到的產物，一個算法可以有一個或多個輸出。

設計一個算法時，它應該滿足以下4個要求。

（1）正確性

要求算法能夠正確地實現預先規定的功能和滿足性能要求，這是最重要也是最基本的標準。目前大多數算法是用自然語言描述需求的，它至少應包括輸入、輸出和加工處理等的明確無歧義的描述。設計或選擇算法應當能正確地反映這種需求。

（2）可讀性

算法應當易于理解，可讀性強。為了達到這個要求，算法必須做到邏輯清晰、簡單并且結構化。晦澀難懂的程序容易隱藏較多錯誤，難以調試和修改。

（3）健壯性

算法要求具有良好的容錯性，能夠提供異常處理，能夠對輸入進行檢查。不經常產生異常中斷或死機現象。例如，一個求矩形面積的算法，當輸入的坐標集合不能構成一個矩形時，不應繼續計算，而應當報告輸入錯誤。同時，處理錯誤的方法是返回一個表示錯誤的值，而不是輸出錯誤信息或直接異常中斷。

（4）效率與低存儲量要求

通常算法的效率主要指算法的執行時間。對于同一個問題，如果能用多種算法進行求解，執行時間短的算法效率高。算法存儲量指的是算法執行過程中所需的存儲空間。效率與低存儲量要求這兩者都與問題的規模有關。例如，求100個學生的平均成績和求10000個學生的平均成績在時間和空間的成本上必然是存在差異的。