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

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

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

1. 算法的基本定義

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

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

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

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

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

阿拉伯數(shù)學家花拉子米

世界上第一個算法

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

輾轉相除法舉例:

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

25/10=2……5

10/5=2……0

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

輾轉相除法代碼實現(xiàn):

int gcd(a, b)
[ return b == 0 ? a : gcd(b, a % b); }
//當余數(shù)為0時，最大公約數(shù)就是a，否則繼續(xù)往下遞歸

世界上第一個算法程序

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

這張寫滿數(shù)學算法的巨幅圖表，被視為“第一個計算機程序”，由埃達·洛夫萊斯編寫， 發(fā)表于 1843 年的一篇關于“分析機” 的文章中。埃達對此給出精準描述如下：“這張表顯示了運算過程中，機器各部分的所有連續(xù)變化。”

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

“軟件之母”Ada Lovelace

圖靈機

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

圖靈機，又稱圖靈計算機，是指一個抽象的機器，即將人們使用紙筆進行數(shù)學運算的過程進行抽象，由一個虛擬的機器替代人類進行數(shù)學運算。

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

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

3. 算法的重要特征

一個算法應該具有以下五個重要的特征：

·有窮性（Finiteness）

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

·確切性(Definiteness)

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

·輸入項(Input)

一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件；

·輸出項(Output)

一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結果。沒有輸出的算法是毫無意義的；

·可行性(Effectiveness)

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

4.算法的評定

算法的復雜性是算法效率的度量，在評價算法性能時，復雜性是一個重要的依據(jù)。算法的復雜性的程度與運行該算法所需要的計算機資源的多少有關，所需要的資源越多，表明該算法的復雜性越高:所需要的資源越少，表明該算法的復雜性越低。

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

評定一個算法的優(yōu)劣可以從以下5個方面進行衡量：

1）時間復雜度

是對一個算法在運行過程中臨時占用存儲空間大小量度。

2）空間復雜度

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

3）正確性

算法的正確性是評價一個算法優(yōu)劣的最重要的標準。

4）可讀性

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

5）魯棒性

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

5.算法設計和分析的基本方法：

1）遞歸和遞推。遞歸和遞推是學習算法設計的第一步。遞歸算法是把大問題分解成相對較小的問題的過程，而遞推就是從小問題逐步推導出大問題的過程。無論遞歸還是遞推，都應該有初始狀態(tài)。

2)搜索、枚舉及優(yōu)化剪枝。搜索在所有算法中既是最簡單也是最復雜的算法。說它簡單，是因為算法本身并不復雜，實現(xiàn)容易:說它最復雜，是因為要對搜索的范圍進行一定的控制，不然就會出現(xiàn)超時等問題。搜索技術主要包括廣度優(yōu)先搜索和深度優(yōu)先搜索。當其余算法都無法對問題進行求解時，搜索或許是唯一可用的方法。搜索是對問題的解空間進行遍歷的過程。有時問題解空間相當龐大，完全遍歷解空間是不現(xiàn)實的，此時就必須充分發(fā)掘問題所包含的約束條件，在搜索過程中應用這些條件進行剪枝，從而減少搜索量。

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

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

5）貪心算法(亦作饕餮法)。就是一種在每一步選擇中都采取在當前狀態(tài)下最好/優(yōu)的選擇，從而希望導致結果是最好!優(yōu)的算法。貪心法可以解決一些最優(yōu)性問題，如:求圖中的最小生成樹、求哈夫曼編碼…對于其他問題，貪心法般不能得到我們所要求的答案。一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法。由于貪心法的高效性以及其所求得的答案比較接近最優(yōu)結果，貪心法也可以用作輔助算法或者直接解決一些要求結果不特別精確的問題。文章來源地址http://www.zghlxwxcb.cn/news/detail-764721.html

到了這里，關于什么是算法？讀完這篇文章你就知道了的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！