按定好的顺序解决

算法是“解决问题的定好的顺序”。走完步骤就出答案，顺序错了结果也错。顺序一样，谁来做都一样的答案。所以给电脑写上顺序，它就总做一样的事。

大问题一口解决不了。所以把它切成同样形状的小问题，定好按什么顺序解，再把小块答案合回去。这样用“切开 - 排顺序 - 合起来”来对付大问题，正是计算思维的起点。再难的问题，切小了，就抓得住。

排序是把打乱的东西按顺序排成一列。挨着比，把大的往后送，重复下去，队就一点点齐了。每一步落一个位，所以再乱，最后队也会齐。收拾整齐了，找起来也容易。

挨着一格一格比的排序，队越长比较就越爆炸，越慢。更聪明的路，是把队对半分开，各自排好，再把排好的两半像拉链一样合并。一直对半分到底，就只剩单个，而单个本身就已排好。合并很快，因为只比两边的最前面。因为是对半分，层增长得慢，每层的花费约等于队长，所以整体比一格一格快得多。这个分开再合并的想法，就是快速排序的窍门。

查找是把想要的拈出来。一个个看慢，可排好了队就一半一半地切，快得多地找到。一半一半地切，只有排好队才行得通。所以排序和查找是搭档。排一次队，往后一直快。

快慢不拿秒来量，而看它长起来的样子。就是看输入的格子 n 一变大，活儿多多少。log n 几乎不长，n 随格子长，n² 会爆。而且式子再乱，只留长得最快的那一项就行。3n²+5n+9 就是个 n²。这样只看最大那项的记号，叫大O(O)。所以在大数据里，一半一半地切，比一个个快得没法比。

算法不只花时间，也占位置（内存）。空间复杂度，衡量的是算法在答案之外多用的位置，随输入大小增长了多少。我们衡量时间用的那把大O尺子，这回原样量到位置上。多用的位置永远是一格，就是 O(1)；随输入一起变多，就是 O(n)。而时间和位置，常常互相交换。事先做好表、多占位置，就变快；原地求解、省下位置，就变慢。所以挑一个好算法时，我们不只看快慢，也一并看位置的代价。

大问题，靠劈成两半、各自解开、再合回来去攻克。关键在于：劈出来的两块互不重叠。一边干过的活，另一边不必再干一遍。小到再也劈不动了，就立刻解，把解好的块往上合，整个答案就出来了。二分查找也好、归并排序也好，都是这个框架。块互不重叠，正是这法子的力量所在。

递归就是解决问题时，用更小的输入再调用自己。第 8 课你把大问题劈成两半去攻克。那个劈开，正是再调用自己。所以分治和递归是一回事。它真正需要的，是个停下的地板。没有地板，就会没完没了往下掉。调用一个个堆起来，一碰到地板，就倒着回上来，合成一个答案。调用自己、停下的地板、堆起再解开。这三样就是递归。

递归常常把同一个小问题反复地重解。光看斐波那契的树就知道，fib(2) 到处又冒出来。把解过的答案记在便条上再用，就不会把同一个东西解两遍了。这就是记忆化。反过来，从最底下的小值开始把表往上填，也是同一个想法。这么一来，原本指数级地慢，就变成线性，快得多了。分治劈出来的块互不重叠，所以没什么可记的，可一旦重叠，记下来这一手就改变一切。

贪心算法就是每一步都挑“眼下看着最好的那个”。它不看整体，一步步地选，所以又快又简单。像找零先给大面额、抢会议先抢最早结束的，在有些问题上这真的是对的。可一旦硬币种类古怪、或路绕来绕去，眼前的最好就不是整体的最好，反成了陷阱。所以贪心又快又常对，但并不总对。

有些解法掷骰子，随机地挑要做什么。在快速排序里，总拿最后一个值当基准，碰上坏输入就慢; 可要是随机挑基准，就能躲开那个陷阱，平均下来更快。还有，往正方形里乱撒点，看落进圆里的比例，就能估出面积。撒得越多，估得越准。随机解法不能保证每回都给一样的答案，但换来的是又快又简单。你让出一点确定性，换到速度。

图是“用点（对象）和线（关系）画出的图画”。点可以是任何东西，线是两者之间的关系。地铁、朋友网、网页都是图。树是其中没有环（循环）的特殊情形。所以树也是图的一种。把世界看成点和线，看着乱的东西一眼就看明白了。

从一个点出发把整个图走遍，有两种走法。广度优先像水波一样一层一层从近处散开。深度优先沿一条路走到头，走不通就退回来。两种都会不漏地踩到每个点，只是顺序不同。而且当线没有远近之分时，广度优先踩到的顺序就是最短距离。

每条线距离不同时，岔口少的路不一定最快。所以光按远近数是不行的。从起点出发，按最近优先，一个点一个点地把距离定下来，把定好区域的边界一个点一个点往外推。每一刻都挑还没定好的点里最近的那个，就是眼前的最优。等边界铺满，就知道到每个点的最快距离了。

有些问题，输入只大一点点，要查的情况数就爆了，所以到今天还没人知道怎么解得快。就像推销员要找一条把每座城都走一遍的最短路。可这类问题往往是：找答案难，验答案易。那么，验得快的问题，是不是解也快呢？这就叫 P 对 NP 问题，至今谁也不知道答案。是个没解开的大谜。

就算是拿不到完美答案的难题，“够好的答案”往往很快就能拿到。有的方法更进一步，还能保证那答案“在最优的百分之几以内”。这是一桩交易：让出一点准度，换来时间。多花点时间就更准，少花点就没那么准。在哪儿停下，由我们来挑。这就是整个领域的收尾。我们没法把每个问题都解得完美，可只要用快的方法、聪明的策略、清楚自己的极限去明智地权衡，哪怕站在难题面前，也能把一个好用的答案握在手里。