演算法

維基百科,自由的百科全書
前往: 導覽搜尋
應對燈泡不亮的簡單演算法流程圖

數學計算機科學/算學之中,演算法/算則法Algorithm)爲一個計算的具體步驟,常用於計算資料處理英語Data processing自動推理。精確而言,演算法是一個表示爲有限長[1]列表的有效方法英語Effective method。演算法應包含清晰定義的指令[2]用於計算函式[3]

演算法中的指令描述的是一個計算,當其執行英語Execution (computing)時能從一個初始狀態和初始輸入(可能爲)開始, [4] 經過一系列有限 [5] 而清晰定義的狀態最終產生輸出 [6]停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的隨機化演算法在內的一些演算法,包含了一些隨機輸入。 [7] [8]

形式化演算法的概念部分源自嘗試解決希爾伯特提出的判定問題,並在其後嘗試定義有效計算性[9]或者有效方法[10]中成形。這些嘗試包括庫爾特·哥德爾雅克·埃爾布朗史蒂芬·科爾·克萊尼分別於 1930年、1934年和1935年提出的遞歸函式阿隆佐·邱奇於1936年提出的λ演算,1936年Emil Leon PostFormulation 1艾倫·圖靈1937年提出的圖靈機。即使在當前,依然常有直覺想法難以定義爲形式化演算法的情況。[11]

歷史[編輯]

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

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

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

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

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

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

特徵[編輯]

以下是Donald Knuth在他的著作The Art of Computer Programming裡對演算法的特徵歸納:

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

基本要素[編輯]

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

常用設計模式[編輯]

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

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

動態規劃法: 當問題的整體最優解就是由局部最優解組成的時候,經常採用的一種方法。詳見詞條。

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

線性規劃法:見詞條。

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

常用實現方法[編輯]

遞迴方法迭代方法:見詞條

順序計算、平行計算分布式計算:順序計算就是把形式化演算法用程式語言進行單執行緒序列化後執行。其餘見詞條。

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

精確求解和近似求解:

形式化演算法[編輯]

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

複雜度[編輯]

時間複雜度[編輯]

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

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

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

常見的時間複雜度有:常數階O(1),對數階O(log2n),線性階O(n), 線性對數階O(nlog2n),平方階O(n2),立方階O(n3),..., k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大,上述時間複雜度不斷增大,演算法的執行效率越低。

空間複雜度[編輯]

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

非確定性多項式時間(NP)[編輯]

實現[編輯]

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

範例[編輯]

求最大值演算法[編輯]

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

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

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

下面是一個形式演算法,用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代碼表示

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;
}

分類[編輯]

參考文獻[編輯]

  1. ^ "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
  2. ^ Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).
  3. ^ "an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) . . . this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).
  4. ^ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).
  5. ^ "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5).
  6. ^ "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).
  7. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
  8. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
  9. ^ Kleene(史蒂芬·科爾·克萊尼) 1943 in Davis 1965:274
  10. ^ Rosser(巴克利·羅瑟) 1939 in Davis 1965:225
  11. ^ Moschovakis, Yiannis N. What is an algorithm?// (編) Engquist, B.; Schmid, W. Mathematics Unlimited — 2001 and beyond. Springer. 2001: 919–936 (Part II). 

外部連結[編輯]

參見[編輯]