淺談算法及算法評價

【摘 要】在計算機領域，一個算法實質上是針對所處理問題的需要，在數據的邏輯結構和存儲結構的基礎上施加的一種運算。對算法要進行評價、改進，從而設計出更好的算法。

【關鍵詞】 算法 算法評價

一、算法

算法是指為解決給定問題而需施行的有窮操作過程的描述。在計算機科學中，算法則是描述計算機解決給定問題的操作過程。描述一個算法可以采用文字敘述，也可以采用傳統(tǒng)流程圖、N-S圖或PAD圖，但要在計算機上實現(xiàn)，則最終必須采用一種程序設計語言編寫為程序。算法的意義非常類似于處方、過程、方法和規(guī)程。

通常，一個算法必須具備以下五個重要特性：

1. 有窮性

有始有終是算法最基本的特征。一個算法必須在它所涉及的每一種情形下，都能在執(zhí)行有窮步操作之后結束。有的運算過程，操作步驟看似有限，但不能保證它在動態(tài)環(huán)境下實際執(zhí)行次數的有窮性。因此，判斷一個算法的有窮性應對算法所涉及的各種情形作動態(tài)分析，從而作出判斷?？聪旅鎯蓚€例子：

例1 一個非算法的計數過程

（1）開始

（2）n←0

（3）n←n+1

（4）重復（3）

（5）結束

粗一看，這個過程僅有五個步驟，是有窮的，但事實上，該過程一開始，就永不休止。因而在動態(tài)執(zhí)行中它并不具備有窮性，它不是一個算法。當然，只要對上述過程稍加修改，限定其計數之上限，即可使之成為一個算法，這就是下面的例2。

2. 確定性

算法的每一步操作，其順序和內容都必須確切定義，而不得有任何歧義性。

3. 數據輸入

一個算法有n（n≥0）個初始數據的輸入。

4. 數據輸出

算法是用來解決給定問題的，所以，一個算法必須將人們所關心的信息輸出。也就是說，一個算法必須有一個或多個有效信息的輸出，它是同輸入數據有某種特定關系的信息。

5. 可行性

一個算法的任何一步操作都必須是可行的，即必須是可以付諸實施并能具體實現(xiàn)的基本操作。也就是說，每步操作均能由計算機（或人們用紙和筆）操作有限次即可完成。

二、算法評價

對于解決同一個問題，往往能夠編寫出許多不同的算法。進行算法評價的目的，既在于從解決同一問題的不同算法中選擇出較為合適的一種，也在于知道如何對現(xiàn)有算法進行改進，從而有可能設計出更好的算法。一般從以下六個方面對算法進行評價。

1. 正確性

正確性是設計和評價一個算法的首要條件，如果一個算法不正確，則不能完成或不能較好地完成所要求的任務，其他方面也就無從談起。一個正確的算法是指在合理的數據輸入下，能夠在有限的運行時間內得出正確的結果。通過采用各種典型的輸入數據上機反復調試算法，使得算法中的每段代碼都被測試過，若發(fā)現(xiàn)錯誤及時修正，最終可以驗證出算法的正確性。

2. 健壯性

健壯性是指一個算法對不合理（又稱不正確、非法、錯誤等）數據輸入的反應和處理能力。一個好的算法應該能夠識別出錯誤數據并進行相應的處理。對錯誤數據的處理一般包括打印出錯誤信息、調用錯誤處理程序、返回標識錯誤的特定信息、中止程序運行等。

3. 可讀性

可讀性是指一個算法供人們閱讀的方便程度。一個可讀性好的算法，應該符合結構化和模塊化程序設計的思想，應該對其中的每個功能模塊、重要數據類型或語句加以注釋，應該建立有相應的文檔，對整個算法的功能、結構、使用及有關事項進行說明。

4. 簡單性

簡單性是指一個算法所采用的數據結構和方法的簡單程度。如對數組進行查找時，采用順序查找的方法比采用二分查找的方法要簡單；對數據進行排序時，采用簡單選擇排序的方法比采用堆排序或快速排序的方法要簡單，對文件進行輸入輸出時，使用提取和插入操作符比使用成員函數要簡單，把一批數據組織成線性結構比組織成樹或圖結構要簡單。但最簡單的算法往往不是最有效的，即可能需要占用較長的運行時間和較多的內存空間。而算法的簡單性便于用戶編寫、分析和調試，對于處理少量數據的情況還是適用的，若要處理大量的數據，則算法的有效性（即占用較少的運行時間和內存空間）比簡單性更重要。

5. 時間復雜度

時間復雜度又稱計算復雜度，它是一個算法運行時間的相對量度。一個算法的運行時間是指在計算機上從開始到結束運行所花費的時間，它大致等于計算機執(zhí)行一種簡單操作（如賦值、比較、計算、轉向、返回、輸入、輸出等）所需的時間與算法中進行簡單操作次數的乘積。因為執(zhí)行一種簡單操作所需的時間隨機器而異，它是由機器本身硬軟件環(huán)境決定的，與算法無關，所以我們只討論影響運行時間的另一個因素——算法中進行簡單操作的次數。

不管一個算法是簡單還是復雜，最終都是被分解成簡單操作來具體執(zhí)行的，因此，每個算法都對應著一定的簡單操作的次數。顯然，在一個算法中，進行簡單操作的次數越少，其運行時間也就相對地越少；次數越多，其運行時間也就相對地越多。所以，通常把算法中包含簡單操作次數的多少叫做算法的時間復雜度，用它來衡量一個算法的運行時間性能或稱計算性能。

在一個算法中，最好情況的時間復雜度最容易求出，但它通常沒有多大的實際意義，因為數據一般都是隨意分布的，出現(xiàn)最好情況分布的概率極小。最差情況的時間復雜度也容易求出，它比最好情況有實際意義，通過它可以估計到算法運行時所需要的相對最長時間，并且能夠使用戶知道如何設法改變數據的排列次序，盡量避免或減少最差情況的發(fā)生。平均情況下的時間復雜度的計算要困難一些，因為它往往需要概率統(tǒng)計等方面的數學知識，有時還需要經過嚴格的理論推導才能求出，但平均情況的時間復雜度最有實際意義，它確切地反映了運行一個算法的平均快慢程度，通常就用它來表示一個算法的時間復雜度。

6. 空間復雜度

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間、算法的輸入輸出數據所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。算法的輸入輸出數據所占用的存儲空間是由要解決的問題所決定的，是通過參數表由調用函數傳遞而來，它不隨本算法的不同而改變。存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的算法。算法在運行過程中臨時占用的存儲空間隨算法的不同而異，有的算法只需要占用少量的臨時工作單元，而且不隨問題規(guī)模的大小而改變，我們稱這種算法是“就地”進行的，是節(jié)省存儲的算法，有的算法需要占用的臨時工作單元數與解決問題的規(guī)模有關。

分析一個算法所占用的存儲空間要從各方面綜合考慮。如對于遞歸算法來說，一般都比較簡短，算法本身所占用的存儲空間較少，但運行時需要一個附加堆棧，從而占用較多的臨時工作單元；若寫成非遞歸算法，一般可能比較長，算法本身占用的存儲空間較多，但運行時將可能需要較少的存儲單元。

對于一個算法，其時間復雜度和空間復雜度往往是相互影響的，當追求一個較好的時間復雜度時，可能會使空間復雜度的性能變差，即可能導致占用較多的存儲空間；反之，當追求一個較好的空間復雜度時，可能會使時間復雜度的性能變差，即可能導致占用較長的運行時間。另外，算法的所有性能之間都存在著或多或少的相互影響。因此，當設計一個算法（特別是大型算法）時，要綜合考慮算法的各項性能、算法的使用頻率、算法處理的數據量的大小、算法描述語言的特性及算法運行的機器系統(tǒng)環(huán)境等各方面因素，才能夠設計出比較好的算法。

【參考文獻】

［1］數據結構. 電子科技大學出版社， 1994.

［2］數據結構實用教程（c/c++描述）. 清華大學出版社，2001.