偽·從零開始學演算法 - 1.1 演算法的簡述

演算法的定義

按照一定規則解決某一類問題的明確和有限的步驟。（人教版高中數學必修3）

任何良定義的具體計算步驟的一個序列。（《演算法導論》原書第3版. 北京: 機械工業出版社. 2013年1月）

高德納在他的著作《計算機程序設計藝術》里對演算法的特徵有如下歸納：

輸入
一個演算法必須有零個或以上輸入量。
輸出
一個演算法應有一個或以上輸出量，輸出量是演算法計算的結果。
明確性
演算法的描述必須無歧義，以保證演算法的實際執行結果是精確地匹配要求或期望，通常要求實際運行結果是確定的。
有限性
依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統模擬的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定演算法必須在有限個步驟內完成任務。

Advertisements
有效性
又稱可行性。能夠實現，演算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現。

簡要來說，一個演算法的描述是準確的；輸入可有可無，但必須要有輸出；要在有限步驟內完成；能夠準確解決特定問題。

演算法的表現形式有自然語言、流程圖、偽代碼等。

自然語言就是將演算法的各個步驟直接寫出來。

流程圖通過特定的圖形符號、連接線和文字說明，敘述演算法步驟。

偽代碼通過介於編程語言和自然語言的形式（更類似於編程語言），描述演算法步驟。

自然語言和偽代碼均無特定形式，能夠解釋清楚意思即可。

比如說計算三個數a、b、c中的最大值的演算法，用三種形式表現如下：

自然語言：

第一步：若a ≥ b，則max = a；否則，max = b。
第二步：若c ≥ max，則max = c。max即為它們中的最大值。

流程圖：

流程圖

偽代碼：

input a, b, c
if a >= b {max = a} else {max = b}
if c >= max {max = c}
print max
end

在後面的示例中，我主要使用流程圖。