最近在研究算法，發(fā)現(xiàn)其實算法也并不是特別難，只要抓住算法的核心思想，再靜下心來，都可以自己實現(xiàn)的。在計算機領(lǐng)域，有一些常見的而且又經(jīng)常使用的算法，這些算法我們應(yīng)該掌握，比如常見的排序算法；還有一些算法就是特定領(lǐng)域中經(jīng)常使用的算法了，這些算法我們只有必須使用時再去學(xué)習(xí)使用就行了，比如圖像處理中的快速傅里葉變換算法。

算法定義

讓我們來看看算法的定義吧。（以下定義摘自中文維基百科）

在數(shù)學(xué)和計算機科學(xué)/算學(xué)之中，算法/演算法/算則法（Algorithm）為一個計算的具體步驟，常用于計算、數(shù)據(jù)處理和自動推理。精確而言，算法是一個表示為有限長列表的有效方法。算法應(yīng)包含清晰定義的指令用于計算函數(shù)。

算法中的指令描述的是一個計算，當(dāng)其運行時能從一個初始狀態(tài)和初始輸入（可能為空）開始，經(jīng)過一系列有限而清晰定義的狀態(tài)最終產(chǎn)生輸出并停止于一個終態(tài)。一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)移不一定是確定的。隨機化算法在內(nèi)的一些算法，包含了一些隨機輸入。

形式化算法的概念部分源自嘗試解決希爾伯特提出的判定問題，并在其后嘗試定義有效計算性或者有效方法中成形。這些嘗試包括庫爾特·哥德爾、雅克·埃爾布朗和斯蒂芬·科爾·克萊尼分別于1930年、1934年和1935年提出的遞歸函數(shù)，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當(dāng)前，依然常有直覺想法難以定義為形式化算法的情況。

算法的特征

以下是高德納在他的著作《計算機程序設(shè)計藝術(shù)》里對算法的特征歸納：

• 輸入：一個算法必須有零個或以上輸入量。

• 輸出：一個算法應(yīng)有一個或以上輸出量，輸出量是算法計算的結(jié)果。

• 明確性：算法的描述必須無歧義，以保證算法的實際執(zhí)行結(jié)果是精確地匹配要求或期望，通常要求實際運行結(jié)果是確定的。

• 有限性：依據(jù)圖靈的定義，一個算法是能夠被任何圖靈完備系統(tǒng)模擬的一串運算，而圖靈機只有有限個狀態(tài)、有限個輸入符號和有限個轉(zhuǎn)移函數(shù)（指令）。而一些定義更規(guī)定算法必須在有限個步驟內(nèi)完成任務(wù)。

• 有效性：又稱可行性。能夠?qū)崿F(xiàn)，算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。

算法的基本要素

算法的核心是創(chuàng)建問題抽象的模型和明確求解目標(biāo)，之后可以根據(jù)具體的問題選擇不同的模式和方法完成算法的設(shè)計。

說起到算法，那么怎樣衡量一個算法的好壞呢？答案是通過兩方面來考慮，一是從時間上來考慮，也就是所謂的時間復(fù)雜度； 還有就是從空間上來考慮，也就是空間復(fù)雜度。

時間復(fù)雜度

• 算法的時間復(fù)雜度是指算法需要消耗的時間資源。

一般來說，計算機算法是問題規(guī)模n 的函數(shù)f(n)，算法的時間復(fù)雜度也因此記做T(n)=O(f(n))。

算法執(zhí)行時間的增長率與f(n) 的增長率正相關(guān)，稱作漸近時間復(fù)雜度（Asymptotic Time Complexity），簡稱時間復(fù)雜度。

常見的時間復(fù)雜度有：常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),…， k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。

空間復(fù)雜度

• 算法的空間復(fù)雜度是指算法需要消耗的空間資源。

其計算和表示方法與時間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來表示。同時間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多。

注意，如果你特別在意算法的時間，在條件允許的情況下可以考慮犧牲空間，也就是所謂的拿空間換取時間。

算法設(shè)計的方法

另外，對于算法的設(shè)計，通常有以下幾種方法。

• 窮舉法

• 分治法

• 動態(tài)規(guī)劃法

• 貪婪算法

• 線性規(guī)劃法

這些方法在此就不深入講解了，因為每一個都可以單獨拿出長長的一大篇文章來講解，不過，我后面會繼續(xù)深入普及這方面的知識的。

算法實現(xiàn)的方法

除了了解到算法的常見設(shè)計方法，那么還有哪些常見的實現(xiàn)方法呢。

• 一般方法

• 遞歸方法

• 迭代方法

好了講了這么多理論，還是用一個例子來解釋下算法到底是什么。

求最大公約算法

問題：

求兩個自然數(shù)的最大公約數(shù) 設(shè)兩個變量M和N

解題步驟：

1.如果M <>

2.M被N除，得到余數(shù)R

3.判斷R＝0，正確則N即為“最大公約數(shù)”，否則下一步

4.將N賦值給M，將R賦值給N，重做第一步。

代碼實現(xiàn)

void swapi(int *x, int *y)

{ int tmp = *x; *x = *y; *y = tmp;

}int gcd(int m, int n)

{ int r; do { if (m <>

swapi(&m, &n);

r = m % n; m = n;

n = r;

} while (r); return m;

}

好了就講這么多了，如果有什么問題可以在下面評論或者發(fā)私信給我。

參考文章

• 中文維基百科一一算法【頭條不讓加外鏈，所以請在維基百科自行搜索吧】