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

演算法(algorithm)

/ AL-go-rith-um /

演算法就是給電腦的食譜。想想做歐姆蛋的食譜:一串有限、毫不含糊的步驟,任何人都能照著順序,把材料(輸入)變成菜餚(輸出)。好食譜絕不會說「加一點鹽碰碰運氣」——每一步都清楚到兩個廚師照做會得到相同結果。演算法正是這種食譜,只不過它要解的是計算問題,而不是做早餐。

更精確地說,演算法是一個有限、定義良好、必定終止的程序,它接受某個輸入並產生正確的輸出。把這句話拆開看。有限:它由固定且有界的指令數寫成。定義良好:每一步都明確無歧義,下一步該做什麼從不需要猜。終止:對每一個合法輸入,它最終都會停下來,而不會永遠繞圈。舉個小例子,要從一串數字中找最大值,你可以維持一個「目前冠軍」:先把第一個數當作冠軍,接著走過其餘的數,每遇到比目前冠軍大的數,就讓它當新冠軍;數字走完時,冠軍就是答案。這就是一個演算法——有限、無歧義,而且必定停止。

演算法之所以重要,是因為它把「解決問題」這件事,從任何特定機器、語言或程式設計師身上抽離出來。同一個「維持目前冠軍」的方法,在你腦中、紙上、Python 裡或硬體上都管用。這正是我們抽象地研究演算法的理由:一個在抽象層面又快又正確的方法,到哪裡執行都依然又快又正確。這個詞本身是為了紀念 9 世紀的學者花拉子米(al-Khwarizmi),他的名字拉丁化後成為 algorism,再演變為 algorithm。

找出 [3, 9, 2, 7] 的最大值:冠軍從 3 開始;看到 9(較大)→ 冠軍 9;看到 2(不較大)→ 維持 9;看到 7(不較大)→ 維持 9;數列結束 → 答案 9。

四個步驟,每步皆無歧義,而且會停下來——一個完整的演算法。

演算法不等於程式。程式是用某種語言寫出來的一份實作;演算法是底層的方法,你可以用許多語言實作它,甚至用手執行。

又称
computational procedure計算程序