淺談算法及算法評價

【摘 要】在計算機領(lǐng)域，一個算法實質(zhì)上是針對所處理問題的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上施加的一種運算。對算法要進行評價、改進，從而設(shè)計出更好的算法。

【關(guān)鍵詞】 算法 算法評價

一、算法

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

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

1. 有窮性

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

例1 一個非算法的計數(shù)過程

（1）開始

（2）n←0

（3）n←n+1

（4）重復(fù)（3）

（5）結(jié)束

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

2. 確定性

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

3. 數(shù)據(jù)輸入

一個算法有n（n≥0）個初始數(shù)據(jù)的輸入。

4. 數(shù)據(jù)輸出

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

5. 可行性

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

二、算法評價

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

1. 正確性

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

2. 健壯性

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

3. 可讀性

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

4. 簡單性

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

5. 時間復(fù)雜度

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

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

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

6. 空間復(fù)雜度

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

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

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

【參考文獻】

［1］數(shù)據(jù)結(jié)構(gòu). 電子科技大學(xué)出版社， 1994.

［2］數(shù)據(jù)結(jié)構(gòu)實用教程（c/c++描述）. 清華大學(xué)出版社，2001.