演算法是什麼？靠步驟的巧思讓計算變快的原理

生活中的例子

在地圖App輸入目的地，幾秒內就會出現路線。在搜尋網站輸入字詞，龐大的網頁中看起來有用的會排在上面。影音App會推薦你可能想看的影片。

想像一下，要把一疊打亂的撲克牌依數字排好。是一次次找出最小的牌抽出來，還是先分成幾疊再合起來？人總會選某種做法，而做法不同，花的時間也差很多。

這種「得出答案的步驟」，就叫做演算法。新聞裡也常看到「社群媒體的演算法」這種說法。本文會用數字確認演算法是什麼，以及為什麼步驟的巧思能讓計算變快。

演算法是「有終點、清楚明確的步驟」

演算法是把解決某個問題的各個階段，依序寫下來的東西。它接收材料（輸入），經過固定的階段，得出答案（輸出）。例如，從一串數字中找出最大數的步驟如下。先把第一個數當作暫時的最大值，再和下一個數比較，比較大就替換暫時的最大值。一直做到最後一個數為止。

它和單純的「做法」不同，在於兩個條件。第一，每個階段的意思都很清楚，任何人照著做都會做同樣的事。第二，不論輸入是什麼，總有一天一定會結束。電腦科學家高德納（Donald Knuth）在著名的教科書中，列出演算法的5個性質。也就是這兩個，再加上輸入、輸出和實際做得到，共5個。

電腦的核心零件CPU，只會一個一個執行「加」「比較」這類簡單的指令。要把哪些指令依什麼順序排列才能得出答案，這種步驟的想法就是演算法。CPU的原理在「CPU是什麼？」中說明。

「演算法」（algorithm）這個詞，源自9世紀數學家花拉子米的名字。他寫了一本用印度數字（今天的阿拉伯數字）計算的書，譯成拉丁文後傳遍歐洲。譯本中他名字的寫法，就成了這個詞的由來。

找法的不同：從頭依序找，還是每次減半

假設要從100萬名會員的名冊中，找出某個編號的人。最直接的方法，是從第一筆開始一筆一筆比較。這種方法叫做「線性搜尋」。運氣不好的話，要一直比到最後一筆，共比較100萬次。

如果名冊依編號排好，就有更好的方法。先和正中間的那一筆比較。要找的編號比較大的話，就絕對不在前半，只留下後半。重複這樣做，每比較1次，範圍就減半。這種方法叫做二分搜尋。

把100萬筆不斷減半，會變成50萬、25萬…，第20次比較時一定會有結果。因為2乘20次是1,048,576，超過100萬。也就是說，用二分搜尋的話，不論找不找得到，最多20次就結束。100萬次和20次，差了5萬倍。

查紙本字典時，人不會從第一頁依序翻。而是先大概翻開，看要往前還是往後，再慢慢縮小範圍。二分搜尋就是把這種縮小範圍的動作，在「剛好正中間」機械式地重複進行。

不過，二分搜尋有個條件。資料必須事先依序排好。如果名冊是亂的，和正中間比較也不知道要找的在哪一邊。所以接下來要看的「排序」，也是很重要的工作。

排序也會出現好幾萬倍的差距

把資料依固定順序重新排列，叫做「排序」。這裡比較兩種做法。工夫的大小，以「比較兩張牌大小的次數」來計算。

第一種是直接的方法。從還沒排好的牌中找出最小的一張，加到隊伍的後面。要找出最小的，必須看過剩下所有的牌。有n張牌時，比較次數第1次是n−1次，第2次是n−2次…，每次少1。合計大約是「n×n÷2」次（這種方法叫做選擇排序）。

第二種是「合併排序」。把一疊牌分成兩半，再把各半分成兩半，一直分到每疊只剩1張。接著把小疊兩兩合起來。比較兩疊最上面的牌，重複拿走較小的那張，就會變成依序排好的一疊。

合併排序快，是因為對半分的次數很少。即使有100萬張，大約對半分20次就會變成每疊1張。合併的工作在每一層都只是把所有的牌各看1次。所以比較次數大約只要「張數×對半分的次數」。「n要對半分幾次才會變成1」寫成 log₂n，所以這是 n×log₂n 次。

合併排序一欄是用 n×log₂n 算出的估計值，實際比較的次數會比這少一些。如果是一副撲克牌，差距約4倍，用手排的話用哪種都行。但張數越多，差距就拉得越大。想親眼看看排序過程的人，可以用排序過程視覺化工具比較幾種方法。

時間複雜度：用工夫的「增加方式」來比較

到目前為止的例子中，重要的不是工夫的「多少」，而是「增加方式」。資料變成2倍時，線性搜尋的工夫變成2倍。二分搜尋只多1次。直接的排序方法則變成4倍。

相對於資料的數量，工夫會怎樣增加。這叫做時間複雜度。它是一把尺，用來比較解決同一個問題的不同步驟，和電腦的快慢無關。

時間複雜度會像 O(n) 或 O(n²) 這樣，加上「O」來寫。這種寫法叫做大O符號，括號中的 n 是資料的數量。O(n²) 的意思是「工夫大約和 n×n 成正比增加」。「÷2」這類係數會省略。因為係數不會改變資料變成2倍時，工夫會變成幾倍。

表中的 log，和前面一樣是以「對半分幾次才會變成1」來計算。O(n²) 一欄是1兆，和前一個表的5,000億不同，是因為省略了係數「÷2」。

最麻煩的是 O(2ⁿ)。要從50件物品中試遍「選哪些」的所有組合，就是2乘50次，約1,100兆種。即使1秒檢查10億種，也要大約13天。物品變成51件，又會再加倍。想改變數字試試看的人，可以用時間複雜度比較工具計算次數和時間。

再快的電腦，也救不了繞遠路的步驟

假設有一台1秒能比較10億次的電腦。為了簡化，假設每次比較花的時間都一樣。用直接的方法排序100萬筆，約5,000億次比較要花約500秒，超過8分鐘。用合併排序約2,000萬次，只要0.02秒。

那麼，換成快100倍的電腦會怎樣？直接的方法也能縮短到5秒。即使如此，用舊電腦跑合併排序還是快250倍。

再假設資料增加10倍，變成1,000萬筆。直接的方法工夫變成100倍，所以快100倍的電腦也要約500秒。舊電腦跑合併排序，只要約0.23秒。用 O(n²) 的步驟，100倍的效能只要資料變成10倍就會用完。

靠著半導體的進步，電腦數十年來持續變快（「摩爾定律是什麼？」）。即使如此，演算法的研究仍不可或缺，原因就在這裡。

留名歷史的演算法

戴克斯特拉演算法（1959年）：找出最近的路

這是在已知各地點、以及連接地點的道路長度時，求出從出發點到各地點最短路線的方法。從離出發點近的地點開始，依序確定「到這裡的最短距離」，並更新更遠地點的距離。荷蘭的艾茲赫爾·戴克斯特拉在1956年想出，1959年發表論文。這種方法叫做戴克斯特拉演算法。

戴克斯特拉後來說，他是在阿姆斯特丹的咖啡館，沒用紙筆，花了約20分鐘想出來的。決定網路通訊路徑的機制（OSPF），也是用這種方法計算路徑。

PageRank（1998年）：從連結衡量網頁的重要性

由當時是史丹佛大學研究生的謝爾蓋·布林和賴利·佩吉提出。他們在1998年的論文中，連同搜尋引擎Google的原型一起發表。被越多網頁連結，而且是被重要網頁連結的網頁，就被認為越重要。根據Google的官方說明，現在的搜尋是結合包含PageRank在內的許多機制來決定排名。

RSA加密（1977年）：把「很費工」拿來當防護

MIT的李維斯特、薩莫爾、阿德曼三人在1977年提出報告，1978年刊登於期刊。把兩個很大的質數相乘很簡單，但要從相乘的結果找回原本的兩個數，用已知的步驟非常花時間。RSA加密就是以這種工夫的差距作為安全的基礎。詳細內容在「加密是什麼？」中說明。

迷宮搜尋（1961年）：決定晶片的佈線

1961年，C. Y. Lee 發表了避開障礙物、找出連接兩點路徑的方法。從起點開始，像波浪擴散一樣，替相鄰的格子、再相鄰的格子編號，到達終點後再循著編號走回來。自動決定電路板和半導體晶片佈線的設計軟體，很早就在使用從這個想法發展出來的方法。

為平行運作的晶片設計的演算法

配合執行它的零件來選擇演算法，也很重要。GPU是把數千個以上的簡單運算電路排在一起，同時運作的晶片。要發揮它的力量，必須把步驟重新組成可以同時進行的形式。

以1,024個數的總和為例。一個一個加的話，加法共1,023次，要等前一個答案，一次一次依序進行。若要平行處理，先兩兩一組，同時做512組加法。剩下的512個數再兩兩相加，就變成256個。重複下去，第10次就得到一個總和。

加法的次數，兩種做法都是1,023次，沒有改變。改變的是等待前一個答案的次數。依序相加要等1,023次份，平行處理只要10次份。GPU公司NVIDIA的技術資料，也把這種樹狀的加法，說明為在GPU上加總大量數字的基本形式。

相反地，不看前一個結果就無法進行下一步的步驟，就不容易平行化。二分搜尋由前一次比較的結果決定下一個要看的位置，是這類步驟的代表。AI的計算為什麼適合同時進行的形式，在「AI為什麼要用GPU？」中說明。

常見的誤解

從數字來看

上面的次數，是假設每次比較時間固定的估計值。實際的時間，也會因為從記憶體搬運資料的速度等而改變。

進一步學習

• 動手試試看：排序過程視覺化工具、時間複雜度比較工具、戴克斯特拉演算法計算工具、二元搜尋樹與堆積視覺化工具
• 用表格看差異：廣度優先搜尋與深度優先搜尋的差異、陣列與鏈結串列的差異、CPU與GPU的差異
• 下一步的用語：穩定排序、遞迴、雜湊表、貪婪演算法、動態規劃
• 從基礎讀起：「CPU是什麼？」、「編譯器是什麼？」、「AI為什麼要用GPU？」