什么是算法？

一份你早已在用的食谱

想象泡一杯茶。你烧开水，把茶包放进杯子，倒水，等待，取出茶包。没人觉得这有什么可怕，可它却具备了计算机科学家所说的[[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` 就是所有数里最大的。这种推理方式——一个在每一趟里都保持为真的事实——我们在查找那一篇里还会再用到。

下面这个观念，正是让整个领域变得有趣的地方：*同一件*任务通常有许多份正确的算法，而它们并非一样好。要找最大的数，你也可以反过来把整串数排好序，再取最后一个——一样正确，可它做的功远超所需。又比如要查一个名字在不在电话簿里，你可以从头到尾读每一条，也可以翻到中间、每次把查找范围减半。两种都能找到名字，但一种快得多。正确，只是入场券。在那之后，我们就按运行起来有多*省*来比较各份食谱——而这正是后面几篇要讲的。