算法是指完成一個(gè)任務(wù)所需要的具體步驟和方法。也就是說(shuō)給定初始狀態(tài)或輸入數(shù)據(jù)，經(jīng)過(guò)計(jì)算機(jī)程序的有限次運(yùn)算，能夠得出所要求或期望的終止?fàn)顟B(tài)或輸出數(shù)據(jù)。

編程界的“Pascal之父”Nicklaus Wirth有一句人盡皆知的名言：“算法+數(shù)據(jù)結(jié)構(gòu)=程序”，Algorithm+Data Structures=Programs，可見(jiàn)算法對(duì)程序的重要性。

本文從算法的基本定義出發(fā)，詳細(xì)解讀了算法的發(fā)展歷程、主要特征、衡量指標(biāo)和算法設(shè)計(jì)的基本方法，供大家學(xué)習(xí)參考。

1. 算法的基本定義

百科百科對(duì)算法的定義是：算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問(wèn)題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。也就是說(shuō)，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。

一句話概括一下，算法就是解決問(wèn)題的操作步驟。

2. 算法的發(fā)展歷程

在我國(guó)古代，算法被稱為“演算法”，關(guān)于算法的起源最早可以追溯到我國(guó)古代公元前1世紀(jì)的《周髀算經(jīng)》，是算經(jīng)的十書之一，原名《周髀》，主要闡述古代中國(guó)的蓋天說(shuō)和四分歷法。在唐朝的時(shí)候，此書被定為國(guó)子監(jiān)算科的教材之一，并改名為《周髀算經(jīng)》。《周髀算經(jīng)》中記載了勾股定理、開(kāi)平方問(wèn)題、等差級(jí)數(shù)等問(wèn)題，其中用到了相當(dāng)復(fù)雜的分?jǐn)?shù)算法和開(kāi)平方算法等。在隨后的發(fā)展中，出現(xiàn)了割圓術(shù)、秦九昭算法和剩余定理等一些經(jīng)典算法。

在西方，算法（algorithm）一詞最早來(lái)源于9世紀(jì)波斯數(shù)學(xué)家花拉子米（花拉子米是代數(shù)與算術(shù)的創(chuàng)立人，被譽(yù)為“代數(shù)之父”，所著《代數(shù)學(xué)》一書，最早給出了一次和二次方程的一般解法），花拉子米的拉丁文譯名是“Algoritmi”，英文對(duì)“算法”原譯為“algorism”，意思是花拉子米的運(yùn)算法則，指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過(guò)程，在18世紀(jì)演變?yōu)椤癮lgorithm”。

阿拉伯?dāng)?shù)學(xué)家花拉子米

世界上第一個(gè)算法

公元前300年，“幾何之父”歐幾里得提出了人類史上第一個(gè)算法——?dú)W幾里得算法，又稱輾轉(zhuǎn)相除法，是求最大公約數(shù)的一種方法。它的具體做法是: 用較大數(shù)除以較小數(shù)，再用出現(xiàn)的余數(shù)(第余數(shù))去除除數(shù)，再用出現(xiàn)的余數(shù)(第二余數(shù))去除第一余數(shù)，如此反復(fù)，直到最后余數(shù)是0為止。如果是求兩個(gè)數(shù)的最大公約數(shù)，那么最后的除數(shù)就是這兩個(gè)數(shù)的最大公約數(shù)。

輾轉(zhuǎn)相除法舉例:

求10，25的最大公約數(shù):

25/10=2……5

10/5=2……0

所以10，25的最大公約數(shù)為5

輾轉(zhuǎn)相除法代碼實(shí)現(xiàn):

世界上第一個(gè)算法程序

'If I should see you，after long year.How should I greet, with tears, with silence. '這是英國(guó)著名詩(shī)人拜倫的詩(shī)句，而世界上第一位程序員阿達(dá)·洛芙萊斯（Ada Lovelace），就是這位著名詩(shī)人的女兒，她編寫了世界上第一個(gè)算法程序。1842年，Ada為巴貝奇分析機(jī)編寫求解伯努利方程的程序，寫作了第一份“程序設(shè)計(jì)流程圖”，被珍視為“第一位給計(jì)算機(jī)寫程序的人”。因?yàn)椴闋査埂ぐ拓惼?Charles Babbage)未能完成他的巴貝奇分析機(jī)，這個(gè)算法未能在巴貝奇分析機(jī)上執(zhí)行。

這張寫滿數(shù)學(xué)算法的巨幅圖表，被視為“第一個(gè)計(jì)算機(jī)程序”，由埃達(dá)·洛夫萊斯編寫， 發(fā)表于 1843 年的一篇關(guān)于“分析機(jī)” 的文章中。埃達(dá)對(duì)此給出精準(zhǔn)描述如下：“這張表顯示了運(yùn)算過(guò)程中，機(jī)器各部分的所有連續(xù)變化?！?/p>

雖然這個(gè)算法未能實(shí)現(xiàn)，但Ada對(duì)計(jì)算機(jī)科學(xué)的貢獻(xiàn)毋庸置疑，1953年，阿達(dá)之前對(duì)查爾斯·巴貝奇的《分析機(jī)概論》所留下的筆記被重新公布，并被公認(rèn)對(duì)現(xiàn)代計(jì)算機(jī)與軟件工程造成了重大影響。

“軟件之母”Ada Lovelace

圖靈機(jī)

20世紀(jì)的英國(guó)數(shù)學(xué)家圖靈提出了著名的圖靈論題，并提出一種假想的計(jì)算機(jī)的抽象模型，這個(gè)模型被稱為圖靈機(jī)。

圖靈機(jī)，又稱圖靈計(jì)算機(jī)，是指一個(gè)抽象的機(jī)器，即將人們使用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過(guò)程進(jìn)行抽象，由一個(gè)虛擬的機(jī)器替代人類進(jìn)行數(shù)學(xué)運(yùn)算。

它有一條無(wú)限長(zhǎng)的紙帶，紙帶分成了一個(gè)一個(gè)的小方格，每個(gè)方格有不同的顏色。有一個(gè)機(jī)器頭在紙帶上移來(lái)移去。機(jī)器頭有一組內(nèi)部狀態(tài)，還有一些固定的程序。在每個(gè)時(shí)刻，機(jī)器頭都要從當(dāng)前紙帶上讀入一個(gè)方格信息，然后結(jié)合自己的內(nèi)部狀態(tài)查找程序表，根據(jù)程序輸出信息到紙帶方格上，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)，然后進(jìn)行移動(dòng)。

圖靈機(jī)是可被視作任意解決有限數(shù)學(xué)邏輯過(guò)程的機(jī)器，可以用來(lái)模擬任何算法。圖靈機(jī)的出現(xiàn)解決了算法定義的難題，圖靈的思想對(duì)算法的發(fā)展起到了重要的作用。

3. 算法的重要特征

一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：

·有窮性（Finiteness）

算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止；

·確切性(Definiteness)

算法的每一步驟必須有確切的定義；

·輸入項(xiàng)(Input)

一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定出了初始條件；

·輸出項(xiàng)(Output)

一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的；

·可行性(Effectiveness)

算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行的操作步驟，即每個(gè)計(jì)算步驟都可以在有限時(shí)間內(nèi)完成（也稱之為有效性）。

4.算法的評(píng)定

算法的復(fù)雜性是算法效率的度量，在評(píng)價(jià)算法性能時(shí)，復(fù)雜性是一個(gè)重要的依據(jù)。算法的復(fù)雜性的程度與運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少有關(guān)，所需要的資源越多，表明該算法的復(fù)雜性越高:所需要的資源越少，表明該算法的復(fù)雜性越低。

計(jì)算機(jī)的資源，最重要的是運(yùn)算所需的時(shí)間和存儲(chǔ)程序和數(shù)據(jù)所需的空間資源，算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。

評(píng)定一個(gè)算法的優(yōu)劣可以從以下5個(gè)方面進(jìn)行衡量：

1）時(shí)間復(fù)雜度

是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小量度。

2）空間復(fù)雜度

程序運(yùn)行時(shí)基本操作所執(zhí)行的次數(shù)。

3）正確性

算法的正確性是評(píng)價(jià)一個(gè)算法優(yōu)劣的最重要的標(biāo)準(zhǔn)。

4）可讀性

算法的可讀性是指一個(gè)算法可供人們閱讀的容易程度。

5）魯棒性

魯棒性是指一個(gè)算法對(duì)不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也稱為容錯(cuò)性。

5.算法設(shè)計(jì)和分析的基本方法：

1）遞歸和遞推。遞歸和遞推是學(xué)習(xí)算法設(shè)計(jì)的第一步。遞歸算法是把大問(wèn)題分解成相對(duì)較小的問(wèn)題的過(guò)程，而遞推就是從小問(wèn)題逐步推導(dǎo)出大問(wèn)題的過(guò)程。無(wú)論遞歸還是遞推，都應(yīng)該有初始狀態(tài)。

2)搜索、枚舉及優(yōu)化剪枝。搜索在所有算法中既是最簡(jiǎn)單也是最復(fù)雜的算法。說(shuō)它簡(jiǎn)單，是因?yàn)樗惴ū旧聿⒉粡?fù)雜，實(shí)現(xiàn)容易:說(shuō)它最復(fù)雜，是因?yàn)橐獙?duì)搜索的范圍進(jìn)行一定的控制，不然就會(huì)出現(xiàn)超時(shí)等問(wèn)題。搜索技術(shù)主要包括廣度優(yōu)先搜索和深度優(yōu)先搜索。當(dāng)其余算法都無(wú)法對(duì)問(wèn)題進(jìn)行求解時(shí)，搜索或許是唯一可用的方法。搜索是對(duì)問(wèn)題的解空間進(jìn)行遍歷的過(guò)程。有時(shí)問(wèn)題解空間相當(dāng)龐大，完全遍歷解空間是不現(xiàn)實(shí)的，此時(shí)就必須充分發(fā)掘問(wèn)題所包含的約束條件，在搜索過(guò)程中應(yīng)用這些條件進(jìn)行剪枝，從而減少搜索量。

3）分治法。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題.....直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)......

4）動(dòng)態(tài)規(guī)劃法。動(dòng)態(tài)規(guī)劃在查找有很多重疊子問(wèn)題的情況的最優(yōu)解時(shí)有效。它將問(wèn)題重新組合成子問(wèn)題。為了避免多次解決這些子問(wèn)題，它們的結(jié)果都逐漸被計(jì)算并被保存，從簡(jiǎn)單的問(wèn)題直到整個(gè)問(wèn)題都被解決。因此，動(dòng)態(tài)規(guī)劃保存遞歸時(shí)的結(jié)果，因而不會(huì)在解決同樣的問(wèn)題時(shí)花費(fèi)時(shí)間。

5）貪心算法(亦作饕餮法)。就是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好/優(yōu)的選擇，從而希望導(dǎo)致結(jié)果是最好!優(yōu)的算法。貪心法可以解決一些最優(yōu)性問(wèn)題，如:求圖中的最小生成樹(shù)、求哈夫曼編碼.....對(duì)于其他問(wèn)題，貪心法般不能得到我們所要求的答案。一旦一個(gè)問(wèn)題可以通過(guò)貪心法來(lái)解決，那么貪心法一般是解決這個(gè)問(wèn)題的最好辦法。由于貪心法的高效性以及其所求得的答案比較接近最優(yōu)結(jié)果，貪心法也可以用作輔助算法或者直接解決一些要求結(jié)果不特別精確的問(wèn)題。