演算法

應對燈泡不亮的簡單演算法流程圖

演算法（英語：algorithm），在數學（算學）和電腦科學之中，指一個被定義好的、計算機可施行其指示的有限步驟或次序，常用於計算、數據處理和自動推理。演算法是有效方法，包含一系列定義清晰的指令，並可於有限的時間及空間內清楚的表述出來。

演算法中的指令描述的是一個計算，它執行時從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。包括隨機化演算法在內的一些演算法，都包含了一些隨機輸入。

早在嘗試解決希爾伯特提出的判定問題時，演算法的不完整概念已經初步定型；在其後的正式化階段中人們嘗試去定義「有效可計算性」或者「有效方法」。這些嘗試包括庫爾特·哥德爾、雅克·埃爾布朗和史蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞迴函式，阿隆佐·邱奇於1936年提出的λ演算，1936年埃米爾·萊昂·珀斯特的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當下，依然常有符合直覺的想法難以定義爲形式化演算法的情況。

歷史

演算法在中國古代文獻中稱為「術」，最早出現在《周髀算經》、《九章算術》。特別是《九章算術》，給出四則運算、最大公約數、最小公倍數、開平方根、開立方根、求素數的埃氏篩，線性方程組求解的高斯消元法。三國時代的劉徽給出求圓周率的演算法：劉徽割圓術。

自唐代以來，歷代更有許多專門論述「算法」的專著：

• 唐代：《一位算法》 一卷，《算法》 一卷；
• 宋代：《算法緒論》 一卷、《算法秘訣》 一卷；最著名的是楊輝的《楊輝算法》；
• 元代：《丁巨算法》；
• 明代：程大位 《算法統宗》
• 清代：《開平算法》、《算法一得》、《算法全書》。

而英文名稱「algorithm」來自於9世紀波斯數學家花拉子米（比阿勒·霍瓦里松，波斯語：خوارزمی ‎，拉丁轉寫：al-Khwarizmi），因為比阿勒·霍瓦里松在數學上提出了演算法這個概念。「演算法」原為「algorism」，即「al-Khwarizmi」的音轉，意思是「花拉子米」的運演算法則，在18世紀演變為「algorithm」。

歐幾里得演算法被人們認為是史上第一個演算法。

第一次編寫程式是愛達·勒芙蕾絲（Ada Byron）於1842年為巴貝奇分析機編寫求解解伯努利微分方程的程式，因此愛達·勒芙蕾絲被大多數人認為是世界上第一位程式設計師。因為查爾斯·巴貝奇（Charles Babbage）未能完成他的巴貝奇分析機，這個演算法未能在巴貝奇分析機上執行。

因為「well-defined procedure」缺少數學上精確的定義，19世紀和20世紀早期的數學家、邏輯學家在定義演算法上出現了困難。20世紀的英國數學家圖靈提出了著名的圖靈論題，並提出一種假想的電腦的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了演算法定義的難題，圖靈的思想對演算法的發展起到了重要的作用。

特徵

以下是高德納在他的著作《電腦程式設計藝術》裡對演算法的特徵歸納：

1. 輸入：一個演算法必須有零個或以上輸入量。
2. 輸出：一個演算法應有一個或以上輸出量，輸出量是演算法計算的結果。
3. 明確性：演算法的描述必須無歧義，以保證演算法的實際執行結果是精確地符合要求或期望，通常要求實際執行結果是確定的。
4. 有限性：依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統類比的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函式（指令）。而一些定義更規定演算法必須在有限個步驟內完成任務。
5. 有效性：又稱可行性。能夠實現，演算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現。

基本要素

演算法的核心是建立問題抽象的模型和明確求解目標，之後可以根據具體的問題選擇不同的模式和方法完成演算法的設計。

常用設計模式

完全遍歷法和不完全遍歷法：在問題的解是有限離散解空間，且可以驗證正確性和最佳性時，最簡單的演算法就是把解空間的所有元素完全遍歷一遍，逐個檢測元素是否是我們要的解。這是最直接的演算法，實現往往最簡單。但是當解空間特別龐大時，這種演算法很可能導致工程上無法承受的計算量。這時候可以利用不完全遍歷方法——例如各種搜尋法和規劃法——來減少計算量。

分治法：把一個問題分割成互相獨立的多個部分分別求解的思路。這種求解思路帶來的好處之一是便於進行平行計算。

動態規劃法：當問題的整體最佳解就是由局部最佳解組成的時候，經常採用的一種方法。

貪婪演算法：常見的近似求解思路。當問題的整體最佳解不是（或無法證明是）由局部最佳解組成，且對解的最佳性沒有要求的時候，可以採用的一種方法。

線性規劃法：見條目。

簡併法：把一個問題通過邏輯或數學推理，簡化成與之等價或者近似的、相對簡單的模型，進而求解的方法。

常用實現方法

遞迴方法與迭代方法

順序計算、平行計算和分散式計算：順序計算就是把形式化演算法用程式語言進行單執行緒序列化後執行。

確定性演算法和非確定性演算法

精確求解和近似求解

形式化演算法

演算法是電腦處理資訊的本質，因為電腦程式本質上是一個演算法來告訴電腦確切的步驟來執行一個指定的任務，如計算職工的薪水或列印學生的成績單。一般地，當演算法在處理資訊時，會從輸入裝置或資料的儲存位址讀取資料，把結果寫入輸出裝置或某個儲存位址供以後再呼叫。

複雜度

時間複雜度

演算法的時間複雜度是指演算法需要消耗的時間資源。一般來說，電腦演算法是問題規模$n$的函式$f(n)$，演算法的時間複雜度也因此記做

$T(n)={\mathcal {O}}(f(n))$

演算法執行時間的增長率與$f(n)$的增長率正相關，稱作漸近時間複雜度，簡稱時間複雜度。

常見的時間複雜度有：常數階$O(1)$，對數階$O(\log n)$，線性階$O(n)$，線性對數階$O(n\log n)$，平方階$O(n^{2})$，立方階$O(n^{3})$，...，$k$次方階$O(n^{k})$,指數階$O(2^{n})$。隨著問題規模$n$的不斷增大，上述時間複雜度不斷增大，演算法的執行效率越低。

空間複雜度

演算法的空間複雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間複雜度類似，一般都用複雜度的漸近性來表示。同時間複雜度相比，空間複雜度的分析要簡單得多。

非確定性多項式時間（NP）

主條目：NP (複雜度)

實現

演算法不單單可以用電腦程式來實現，也可以在人工神經網路、電路或者機械裝置上實現。

範例

求最大值演算法

這是演算法的一個簡單的例子。

我們有一串隨機數列。我們的目的是找到這個數列中最大的數。如果將數列中的每一個數字看成是一顆豆子的大小，可以將下面的演算法形象地稱為「撿豆子」：

1. 首先將第一顆豆子放入口袋中。
2. 從第二顆豆子開始檢查，如果正在檢查的豆子比口袋中的還大，則將它撿起放入口袋中，同時丟掉原先口袋中的豆子。反之則繼續下一顆豆子。直到最後一顆豆子。
3. 最後口袋中的豆子就是所有的豆子中最大的一顆。

以上演算法在中國大陸的教科書中通常被叫做「打擂法」或者「迴圈打擂」：在一個for迴圈中，每輪迴圈都有新的挑戰者。若挑戰者勝的話，挑戰者做新擂主，否則擂主衛冕。for迴圈結束後輸出最後的擂主。

下面是一個形式演算法，用ANSI C代碼表示

int max(int *array, int size)
{
  int mval = *array;
  int i;
  for (i = 1; i < size; i++)
    if (array[i] > mval)
      mval = array[i];
  return mval;
}

求最大公約數演算法

求兩個自然數的最大公約數 設兩個變數$M$和$N$

1. 如果$M<N$，則交換$M$和$N$
2. $M$除以$N$，得到餘數$R$
3. 判斷$R=0$，正確則$N$即為「最大公約數」，否則下一步
4. 將$N$賦值給$M$，將$R$賦值給$N$，重做第一步。

用ANSI C代碼表示

//交換2數
void swapi(int *x, int *y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

int gcd(int m, int n)
{
  int r;
  do
  {
    if (m < n)
      swapi(&m, &n);
    r = m % n;
    m = n;
    n = r;
  } while (r);
  return m;
}

利用if函式以及遞迴則能做出更為精簡的程式碼，更可省去交換的麻煩。（但是也因為遞迴呼叫，其空間複雜度提高）

int gcd(int a,int b)
{
    if(a%b)
        return gcd(b,a%b);
    return b;
}

分類

• 基本演算法
  • 列舉
  • 搜尋
    • 深度優先搜尋
    • 廣度優先搜尋
    • 啟發式搜索
    • 遺傳演算法
• 資料結構的演算法
• 數論與代數演算法
• 計算幾何的演算法
  • 凸包演算法
• 圖論的演算法
  • 哈夫曼編碼
  • 樹的遍歷
  • 最短路徑演算法
  • 最小生成樹演算法
  • 最小樹形圖
  • 網路流演算法
  • 匹配演算法
  • 分團問題
• 動態規劃
• 其他
  • 數值分析
  • 加密演算法
  • 排序演算法
  • 檢索演算法
  • 隨機化演算法
  • 關於並列演算法，請參閱平行計算一文。

參考文獻

• Rogers, Jr, Hartley. Theory of Recursive Functions and Effective Computability. The MIT Press. 1987. ISBN 0-262-68052-1. 
• Davis, Martin. The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press. 1965. ISBN 0-486-43228-9.  Davis此書中有列出許多相關的論文，包括哥德爾、邱奇、圖靈、巴克利·羅瑟、史蒂芬·科爾·克萊尼及埃米爾·波斯特的論文。在參考文獻中也會列出原作者的姓名。

參閱

• 抽象機器
• 演算法作曲
• 進階綜合
• 垃圾進，垃圾出
• 《演算法導論》
• 計算理論
  • 可計算性理論
  • 計算複雜性理論

延伸閱讀

[在維基數據編輯]

《欽定古今圖書整合·曆象彙編·曆法典·演算法部》，出自陳夢雷《古今圖書整合》

外部連結

• 20世紀十大演算法 （頁面存檔備份，存於網際網路檔案館）
• 演算法筆記 （頁面存檔備份，存於網際網路檔案館）
• 計算幾何演算法概覽 （頁面存檔備份，存於網際網路檔案館）