什麼是演算法——問題、計算模型與正確性

問題、演算法與程式之別(problem vs algorithm vs program)

在「寫點程式碼」這句鬆散的話底下,藏著三件不同的事,把它們分清楚能省去許多混淆。問題是你想完成什麼。演算法是你選來完成它的方法。程式是用電腦能跑的真實語言把那方法寫出來。想像做書架:問題是「撐住這些書」;演算法是計畫(「鋸四塊這麼長的板子,這樣接起來」);程式則是你在車庫裡用你的工具實際鋸切與鎖螺絲。

每一層回答不同的問題。問題是一份規格:給定這種輸入,什麼輸出才正確?它對方法隻字不提。演算法是一套程序:一份有限、無歧義、與語言無關、且滿足該規格的食譜——你可以用虛擬碼甚至白話描述它。程式是一份實作:把演算法用 Python、C 或任何語言編碼出來,把所有瑣碎的真實細節(變數名稱、記憶體、錯誤處理)都填上。一個問題能由許多演算法來解;一個演算法能在許多語言中化為許多程式,全都表達同一套底層方法。

為什麼非要堅持這種分層?因為正確性與速度主要住在演算法這一層,而非程式這一層。如果你的演算法是平方時間的,再精巧的 C 或再快的筆電也無法把它變成近乎瞬間的 n log n 方法——你必須換演算法。反過來,一個出色的演算法也可能被有臭蟲的程式毀掉。把層次分開,讓你能在斟酌實作細節之前先抽象地推理方法(「這套做法既正確又快嗎?」),也讓同一個好點子得以跨語言、跨機器重用數十年。

問題:「把這些名字排序。」演算法:合併排序(切半、各自排序、合併)。程式:你實際執行的那 30 行 Python。把 Python 換成 Java,程式變了,但演算法與問題不變。

同樣的問題與演算法,不同的程式——方法比程式碼活得久。

加速程式(更快的語言、更好的硬體)帶來常數倍的改進;選一個更好的演算法則改變成本隨 n 成長的方式。對大型輸入,後者幾乎總是佔上風。

又稱
three levels of computation計算的三個層次