课程笔记

5算法

5 分钟阅读

阅读入口

递归的结构

写递归前先回答三个问题

基线是什么？ 最小规模取什么值，答案是什么？
规模如何减小？ 每一步把问题缩小多少，是否一定到达基线？
结果如何组合？ 子问题的返回值怎样合成当前问题的答案？

执行顺序

递归调用不会立刻返回结果：当前调用先暂停，等子调用结束后再继续执行它后面的语句。因此，打印语句写在递归调用之前还是之后，会得到完全不同的输出顺序。汉诺塔的移动顺序就是由三次调用的先后关系决定的。

每次调用都会占用一个栈帧；调用链的展开与回退见函数调用与栈帧。

线性递归与树形递归

线性递归：每次只调用一次自身，调用链是一条线。递归加法属于这一类，规模每步减少1。
树形递归：每次分解成多个子调用，调用过程形成一棵树。汉诺塔每次产生两个规模 $n-1$ 的调用，移动次数满足 $M(n)=2M(n-1)+1$ ， $M(1)=1$ ，解得 $M(n)=2^n-1$ 。

树形递归的调用次数可能随规模指数增长，写之前应先估计调用总量。

来源：递归

5.2用递归加法、汉诺塔和归并建立这套结构，5.7的factors也是同一种写法。读后面几节时，凡是新的递归函数，都先回到“基线、规模、组合”这三个问题上。

分治的适用条件

分治能成立，通常需要同时满足以下条件：

子问题与原问题同型：可以用同一个函数处理，否则只是普通的任务拆分。
子问题相互独立：同一个子问题不会被重复求解。若子问题大量重叠，分治会反复计算同一批状态，应改用动态规划。
规模确实缩小：分解后的每个子问题都严格小于原问题，递归才能终止。
合并的代价可控：如果合并比重新计算还昂贵，分解就没有收益。

与递归、动态规划的关系

分治描述“怎么分解、怎么合并”，递归是常见的实现方式；两者不是同义词。动态规划也常写成递推式，但它会保存子问题的答案。判断时先看子问题是否重叠：重叠就用动态规划，不重叠再考察分治的合并是否划算。

代价的估计

分治不保证更快。寻找最小值无论用循环还是分治，都至少检查每个元素一次；归并排序的收益来自“合并两个有序列表”这一步，代价是 $O(n\log n)$ 的时间和 $O(n)$ 的额外空间。分析时分别估计分解、递归调用和合并的工作量，不要只数递归调用的层数。

来源：分治法

5.3的四种写法都建立在这些条件上。贪心与动态规划的分界也在这里：子问题重叠时换策略，子问题分离时讨论合并的代价。

学习安排

5.1用找假币说明计算思维；5.2用递归加法、汉诺塔和归并熟悉基线条件与递归步骤；5.3把递归用于分治，比较寻找最小值的三种写法，再处理同时求最值、归并排序和二进制加法。5.4–5.6转到另外三类策略：贪心每步取局部最优，动态规划保存重叠子问题的答案，迷宫问题用回溯搜索。5.7用递归分解因数讨论问题复杂度，与5.1的“计算思维之美”首尾呼应。

阅读顺序上，递归在分治之前：分治的“求解”步骤就是递归调用。贪心与动态规划放在分治之后，便于比较“每一步都取局部最优”和“保存子问题答案”两种思路。

课程约定

本章用Python列表表示序列。切片a[i:j] 返回新列表，不会原地修改；递归函数常以len(a) == 1作为基线条件。
5.3的归并排序直接调用5.2定义的merge，教材没有在归并排序里重复实现它。
汉诺塔的Hanoi(n, A, C, B) 表示把 $n$ 个盘子从A移到C、以B为辅助柱。
二进制加法用True/False列表表示二进制位，列表首元素是高位。

方法选择

遇到算法设计题时，按下面的顺序判断：

子问题是否重叠？重叠就考虑动态规划。
每一步的局部最优能否推出全局最优？能证明就用贪心。
能否分成独立的同型子问题并有效合并？可以就用分治。
需要在多条路径中尝试、失败后回退？用回溯。

分治、贪心和动态规划都可能写成递归或递推。区别不在代码形式，而在子问题是否重叠、答案是否保存。

递归与动态规划的对比

易错点

递归只写递归步骤、没有基线条件，或调用的规模没有变小，就无法终止。
分治要求子问题独立；子问题重叠时继续分治，会重复计算。
递归版求最小值与归并排序都用切片保存子列表，复制开销不能忽略。
贪心不是“每步取最大或最小”这么简单，需要证明局部最优能导向全局最优；币值任意的找零问题就可能失效。
Smin_max合并时，最小值与最大值要分别处理，不能把两个返回值当成同一个量。

复习要点

5.7的factors先找出一个因数，再递归分解剩余部分，循环上界取 $\lfloor\sqrt{x}\rfloor$ 。它把5.1的“把问题拆成可计算步骤”和5.7的“复杂度”接在一起；复习时可以和找假币的线性扫描对照，比较两种做法把代价花在了哪里。