什麼是演算法？

一份你早已在用的食譜

想像泡一杯茶。你燒開水，把茶包放進杯子，倒水，等待，取出茶包。沒人覺得這有什麼可怕，可它卻具備了計算機科學家所說的[[dsa-algorithm|演算法]]的全部要素：一串有限的、清晰的步驟，接收一些初始材料（水、茶包），產出一個結果（茶）。這就是全部的觀念。演算法不過是一套*精確的流程*——一份寫得足夠仔細的食譜，仔細到哪怕你閉著眼照做，也能得到正確的答案。

這個詞聽上去嚇人，但你這輩子一直在執行演算法：在詞典裡查一個單字、發一副撲克牌、照路線去朋友家。在這門課裡，唯一的不同是我們會把步驟寫得極其精確，精確到一台毫無常識的機器都能照做。電腦從不去猜你*想表達*什麼。所以演算法必須把要做什麼、按什麼順序，說得一絲不漏、毫無縫隙。

從步驟到程式碼：找出最大的數

我們來把一份食譜變成電腦能跑的東西。任務是：給定一串數字，找出最大的那個。換作人，你瞄一眼就行了，可機器需要把步驟一條條寫明。先用大白話給出這份食譜。

1. 先假定第一個數是目前最大的，把它記住。
2. 逐個查看其餘的每一個數。
3. 如果當前看到的這個比你記住的那個大，就改記住這一個。
4. 當沒有數剩下時，你記住的那個就是最大的，把它報出來。

注意每一步都是機械的——不需要任何判斷。正因如此，它能直接翻譯成 C++：

#include <vector>

// Return the largest value in v. (Assume v is not empty.)
int largest(const std::vector<int>& v) {
    int best = v[0];                 // step 1: first is best so far
    for (int i = 1; i < v.size(); i++) {   // step 2: look at the rest
        if (v[i] > best) {           // step 3: found a bigger one?
            best = v[i];             //         remember it instead
        }
    }
    return best;                     // step 4: report the answer
}

先求正確，再論一題多解

我們對演算法的第一項要求是正確性：對*每一個*合法輸入，它都回傳正確的答案。我們這份食譜之所以正確，靠的是一個一路成立的小承諾——看完前 *k* 個數之後，`best` 裡裝的總是這 *k* 個中最大的那個。開頭時檢驗一下（k = 1，顯然成立），每走一步都讓這個承諾繼續為真，於是到最後 `best` 就是所有數裡最大的。這種推理方式——一個在每一趟裡都保持為真的事實——我們在查找那一篇裡還會再用到。

下面這個觀念，正是讓整個領域變得有趣的地方：*同一件*任務通常有許多份正確的演算法，而它們並非一樣好。要找最大的數，你也可以反過來把整串數排好序，再取最後一個——一樣正確，可它做的功遠超所需。又比如要查一個名字在不在電話簿裡，你可以從頭到尾讀每一條，也可以翻到中間、每次把查找範圍減半。兩種都能找到名字，但一種快得多。正確，只是入場券。在那之後，我們就按運行起來有多*省*來比較各份食譜——而這正是後面幾篇要講的。