2.1　算法的基本概念

算法是解決問題的完整的步驟描述，是解決問題的策略、規(guī)則和方法。算法與程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)密切相關(guān)，正如著名計算機(jī)科學(xué)家Niklaus Wirth提出的公式：算法+數(shù)據(jù)結(jié)構(gòu)=程序。

算法是程序不可缺少的部分。算法的描述形式有很多種，如傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、計算機(jī)程序語言等。下面介紹算法的幾個特性，并且分析一個好的算法應(yīng)該具備哪些特點(diǎn)。

2.1.1　算法的特性

算法是為解決某個特定類型的問題而設(shè)計的一個實(shí)現(xiàn)過程，它具有以下特性。

1.有窮性

一個算法必須在執(zhí)行有窮步之后結(jié)束，并且每一步都在有窮時間內(nèi)完成，不能無限地執(zhí)行下去。就像一條線段，有起點(diǎn)有終點(diǎn)，不能無限延長，如圖2.1所示。

例如，要編寫一個整數(shù)由小到大累加的程序，一定要設(shè)置整數(shù)的上限，否則程序會無終止地運(yùn)行下去，也就是常說的死循環(huán)。

2.確定性

算法的每一步都應(yīng)該是確切定義的，不能有二義性，要執(zhí)行的每個步驟都必須有嚴(yán)格而清楚的規(guī)定。

3.可行性

算法中的每一步都應(yīng)該能有效地運(yùn)行，也就是說算法是可執(zhí)行的，并且要求最終能得到正確的結(jié)果。例如，如圖2.2所示的程序，代碼中的“z=x/y；”就是一個無效的語句，因?yàn)?不可以作分母。

4.輸入

一個算法可以有一個或多個輸入，也可以沒有輸入，輸入就是在執(zhí)行算法時從外界獲取的數(shù)據(jù)，如算法所需的初始量。有多個輸入的算法代碼如下：

沒有輸入的算法代碼如下：

5.輸出

輸出是算法最終得到的結(jié)果，一個算法有一個或多個輸出。編寫程序的目的就是要得到輸出。例如，在控制臺中輸出“MingRi”，如圖2.3所示。

如果一個程序在運(yùn)行后沒有得到輸出，那么這個程序就失去了意義。

2.1.2　算法的優(yōu)劣

衡量一個算法的優(yōu)劣，通常要從以下幾個方面分析。

1.正確性

正確性是指所寫的算法能滿足具體問題的要求，即對任何合法的輸入，算法都會得出正確的輸出。

2.可讀性

可讀性是指算法被理解的難易程度。一個算法的可讀性十分重要，如果一個算法比較抽象，難以理解，那么這個算法就不易交流和推廣，在修改、擴(kuò)展及維護(hù)時都十分不方便。因此在編寫算法時，要盡量將該算法寫得簡明易懂。

3.健壯性

在一個程序編寫完成后，運(yùn)行該程序的用戶對程序的理解各不相同，并不能保證每個人都能按照要求進(jìn)行輸入。健壯性是指當(dāng)輸入的數(shù)據(jù)非法時，算法能夠做出相應(yīng)判斷和反應(yīng)，而不會因?yàn)檩斎脲e誤造成程序癱瘓。例如，用積木搭建“高塔”，即使取下幾塊積木，“高塔”仍然不會倒，這就是“高塔”的健壯性。

4.時間復(fù)雜度與空間復(fù)雜度

時間復(fù)雜度是指算法運(yùn)行所需的時間。不同的算法具有不同的時間復(fù)雜度。如果一個程序比較小，就感覺不到時間復(fù)雜度的重要性；如果一個程序特別大，就會察覺到時間復(fù)雜度是十分重要的。因此，寫出更高速的算法一直是算法不斷改進(jìn)的目標(biāo)?？臻g復(fù)雜度是指算法運(yùn)行所需的存儲空間。