树下的分开又重逢
图：本文生成式概念插画。天平负责缩小怀疑范围，重新汇合的线条提醒我们：真正昂贵的故事常发生在 Combine。
天平落下以前，二十七枚硬币都保持沉默
旧式天平没有刻度。 它不会告诉你左边重了多少，只肯做三种回答：左边轻、右边轻、两边相等。
桌上有 27 枚硬币，一枚假币略轻。 若从第一枚开始逐个怀疑，三次称量几乎什么也做不了。 可如果先把硬币分成三组，每组 9 枚，把前两组放上天平，天平的一次点头便会让 18 枚硬币同时退出故事：
- 左边轻，假币在左组； - 右边轻，假币在右组； - 两边相等，假币在没有上场的第三组。
接着把 9 枚分成三组，再把 3 枚分成三组。27 → 9 → 3 → 1。 我们没有获得更精确的称量工具，只是改变了提问的尺度。
这幅画面很容易让人把 Divide and Conquer 理解成“不断切半”或“递归就完事”。 可硬币谜题其实只展示了最轻松的一类：每次只需继续追踪一个 child instance，回来时也几乎不用 combine。
真正的故事从孩子们再次相遇时开始。
Merge Sort 的两半回来时，各自声称已经排好，却还要花线性时间交错合并； Inversion Counting 还要求它们汇报跨越边界的关系； 大整数乘法原本带回四个 half-size products，Karatsuba 却发现其中一个可以用代数关系省掉； FFT 更进一步，挑选一组有对称性的 points，让两份 half-size evaluations 同时回答两倍的问题。
于是复杂度并不只由“切得多小”决定。还要看：
1. 每次分出多少个 children； 2. 哪些 children 真的必须递归； 3. Divide 与 Combine 在每一层收取多少费用； 4. child solutions 是否携带了 parent 最需要的那类信息。
递归会制造很多房间。算法设计的工作，是决定哪些门必须打开，以及孩子们回来时，手里应该带着什么。
D&C 的四个部件
一份 divide-and-conquer algorithm 通常包含：
- Base cases：小到无需继续递归的 instances； - Divide：把 instance 切成更小的 instances； - Conquer：独立递归求解 child instances； - Combine：把 child solutions 合成 parent solution。
关键词是 independently。如果 child subproblems 大量重叠，并且相同 state 会反复出现，更像 DP；如果每层只保留一个局部最优选择，更像 Greedy。
Correctness
D&C correctness 通常用 strong induction on input size：
1. Base cases 直接正确； 2. 假设所有更小 instances 都被递归调用正确解决； 3. 证明 Divide 产生的 child instances 覆盖了原问题需要的信息； 4. 证明 Combine 在 child answers 正确时，会得到 parent 的正确答案。
不要只证明两个递归调用“会返回答案”。真正的 hinge 往往在 combine：cross-boundary information 是否被完整计算？
图：递归调用解决孩子，Combine 才把孩子的答案变回父问题的答案。复杂度由两边共同决定。作者自制。
Binary Search：只进入一个房间
给定 sorted array 与 target x：
1. 检查中点； 2. 若中点等于 x，完成； 3. 若中点小于 x，只递归右半； 4. 否则只递归左半。
每层只产生一个 size 约为 n/2 的 child，额外工作 Θ(1)：
递归深度 Θ(log n)，所以总时间 Θ(log n)。
常见 extensions
- lower bound：最小的满足 A[i] ≥ x 的 index； - upper bound：最大的满足 A[i] ≤ x 的 index； - equal range：所有等于 x 的 indices 区间； - first true / last true：在 monotone Boolean predicate 上找边界。
处理 duplicates 时，发现一个 x 不代表 lower bound 已经找到。必须继续向可能存在更早答案的一侧收缩，同时保存当前 candidate。
Discrete Binary Search：在答案上二分
Binary search 不只搜索 array。只要一个 decision predicate 随 target 单调，就能搜索答案。
设 optimisation 问题想求最大 feasible target t，并能在 g(n) 时间判断：
若：
则答案空间形如：
用 binary search 找最后一个 true。若候选范围宽度为 K，总时间：
Worked example：Maximum Median
有一个已经递增排序、长度 2n - 1 的整数 array A。每天可把任意元素增加 1，共 k 次。问最大可能 median。
对某个 target t，判断能否让 median 至少为 t：
- array 前半不影响 median 是否达到 t； - 对 positions n..2n-1，所有小于 t 的值都必须补到 t； - 所需 increments 为：
若 cost(t) ≤ k，target feasible。
feasible(t) 单调：能达到更高 median，当然也能达到更低 target。每次 decision 扫描后半 array，花 O(n)；target 搜索范围可取 A[n]..A[n] + k，所以总时间：
三个必须写清的点
1. Predicate 是什么：YES/NO 的语义必须完整； 2. Monotonicity 为什么成立：不能只说“显然单调”； 3. Search bounds：答案一定落在哪个区间，区间宽度决定 log 中是什么。
若 predicate 呈 true, false, true，binary search 不是稍微不准，而是根本没有边界可找。
Merge Sort：两边各自有序，重逢时线性和解
Merge sort：
- Divide：array 分成两半，Θ(1)； - Conquer：递归排序两半； - Combine：线性 merge 两个 sorted arrays，Θ(n)。
递推式：
递归树共有 Θ(log n) 层，每层合计处理 Θ(n) 个元素，因此：
Merge sort 重要，不只因为会排序。更重要的是：sorted child solutions 让跨分区信息可以批量计算。
Inversion Counting：不要一对一对数
对 array A[1..n]，inversion 是一对 indices (i, j)，满足：
brute force 检查所有 pairs，需要 Θ(n²)。D&C 把 inversions 分成三类：
- 左半内部：递归； - 右半内部：递归； - 跨两半：在 merge 时计算。
Combine 的 hinge
假设递归已经把 left 与 right 排序。Merge 时：
- 若 left[i] ≤ right[j]，把 left[i] 放入结果，不新增 cross inversion； - 若 left[i] right[j]，那么从 left[i] 到左半末尾的所有剩余元素都大于 right[j]。
于是一次就增加：
个 inversions，并把 right[j] 放入结果。
原本可能是线性数量的一组 pairs，被 sorted order 一口气数完。Modified merge 仍为 Θ(n)，递推式仍是：
所以总时间 Θ(n log n)。
Correctness
每个 inversion 恰属于三类之一：
1. 两个 endpoints 都在 left； 2. 都在 right； 3. 前者在 left、后者在 right。
前两类由 induction hypothesis 正确计数。第三类在 merge 中按较小的 right-side element 计数一次；当 right[j] 被取出时，所有尚未取出的 left elements 恰好形成与它的 cross inversions。没有遗漏，也没有重复。
Combine 这一步不仅“把数组排好”，还携带 parent 需要的统计量。D&C 很多创新就发生在这里：递归框架不变，merge 时多带一件东西回来。
Quicksort：平衡不是承诺
Quicksort：
- Divide：选 pivot，并按大小 partition，Θ(n)； - Conquer：递归排序 pivot 两边； - Combine：几乎无需额外工作。
若 pivot 每次把 array 大致均分：
若 pivot 每次都是极值：
因此：
- average / expected：通常 Θ(n log n)，需说明 pivot model； - worst case：Θ(n²)。
Master Theorem 只处理固定比例的 T(n/b) 形状，不能直接塞进 T(n - 1)。一个定理用不了，并不表示复杂度也拒绝回答；把递推式展开求和即可。
Recurrence：把算法的家谱写出来
若一个 size n 的 instance：
- 产生 a 个 size 至多 n/b 的 child instances； - Divide 与 Combine 合计 f(n)；
则常见递推式是：
三个量各自有明确语义：
- a：branching factor； - b：每个 child 缩小多少； - f(n)：本层不在递归调用中的工作。
漏算 f(n) 是最常见的事故。把 array 切成两半可能 Θ(1)，但把两个答案 merge 回来可能 Θ(n)；不能因为 combine 写在最后，就当它没有花时间。
Master Theorem：比较叶子与每层的劳动
课程采用以下版本。设：
n^(c) 也可理解为 recursion tree 的 leaves 数量级。
Case 1：树叶占主导
若存在 ε 0，使：
则：
每个 internal node 的额外工作增长得不够快，数量庞大的 leaves 赢了。
Case 2：每层势均力敌
若：
则：
每层工作同阶，共有 Θ(log n) 层。
Case 3：root work 占主导
若存在 ε 0，使：
并满足 regularity condition：存在常数 q < 1 与充分大的 n，使：
则：
本层工作向上增长得足够快，root 附近支配总成本。
应用模板
只写“f(n) 比 n^c 大，所以 Case 3”不够。“大一个 log”与“大一个 polynomial factor”是不同的事。
期末复习递推式逐个拆
额外复习资料列出了一组很适合检查盲点的 recurrences。
T(n) = 4T(n/2) + n
n ∈ O(n^(2 - 1))，Case 1：
T(n) = 4T(n/2) + n²
f(n) = Θ(n²)，Case 2：
T(n) = 4T(n/2) + n³
f(n) 比 critical polynomial 大一个 polynomial factor。检查 regularity：
可取 q = 1/2 < 1，Case 3：
T(n) = T(n - 1) + n²
不符合 T(n/b)，Master Theorem 不适用。展开：
平方和为 Θ(n³)，因此：
T(n) = 2T(n/2) + n log n
这里 c = 1，critical polynomial 是 n，但：
它不属于课程版 Case 2 的 Θ(n)，也不比 n 大一个 n^ε 的 polynomial factor，所以课程版 Master Theorem 不能直接应用。
用 recursion tree：
第 i 层有 2ⁱ 个 size n/2ⁱ 的 instances，每个额外工作：
该层总工作：
把 i = 0..log n - 1 求和：
所以：
这是很好的考试陷阱：会背三种 case 还不够，还要知道什么时候不该硬套。
Large Integer Multiplication：四次递归，一无所得
在 bit complexity model 中，n-bit integers 的加法是 Θ(n)，乘法不能再假设是 constant time。
把两个 n-bit integers 分成高低各 n/2 bits：
直接展开：
需要四个 half-size multiplications：
加法与 shifting 为 Θ(n)：
Master Theorem 给出：
分治框架很忙，复杂度却与 grade-school multiplication 同阶。问题不是没有 Divide，而是 branching factor 太大。
Karatsuba：用一次便宜加法，买掉一次昂贵乘法
关键代数式：
先递归计算三个乘积：
中间 cross term 为：
于是：
递归乘法从四次降为三次，额外仍只有线性加减：
因此：
Karatsuba 最迷人的地方，是它没有让每次 multiplication 本身变快。它只是少做了一次。递归树会把这一次节省复制到每一层，于是一个局部代数 trick 变成全局 exponent 的改变。
Convolution：多项式乘法的另一张脸
设 coefficient sequences：
对应 polynomials：
乘积 polynomial PC(x) = PA(x)PB(x) 的第 t 个 coefficient：
这正是 sequences 的 convolution：
直接计算所有 pair products 需要 Θ(n²)。FFT 的策略不是更快地做同一堆 pairwise products，而是换 representation：
在 value representation 中，两个 polynomials 相乘只需对相同 sample points 的 values 逐点相乘，线性时间即可。真正的工作变成：怎样快速地在很多点上 evaluate polynomial，并再 reconstruct coefficients。
Fishing Net：先反转模板，再做 convolution
Slides 用一张有洞的 fishing net 展示怎样从题目认出 convolution。Shore sequence A[i] 表示每米的 fish 数，binary net sequence N[j] 表示第 j 段是否有网。把 net 放在 offset t 时，捕获量是对应位置的 dot product。
Convolution 要求一个 index 增加时另一个减少，而原来的 net index 与 shore index同向移动。解决办法是先把 net sequence reverse 得到 N'，再计算：
C 的适当区间中，每一项对应一个 placement 的捕获量；取最大项即可。Shore 长度是 100L，仍为 Θ(L)，所以 FFT 总时间 Θ(L log L)。
这是一类常见的识别动作：sliding dot product / cross-correlation 与 convolution 只差一次 reversal。FFT 并不只乘多项式，它也能一次性评估所有 alignments。
Roots of Unity：让一半计算自动重现
取 m 次 roots of unity：
DFT 把 coefficient sequence A 转成 polynomial 在这些 points 的 values：
为避免 product polynomial 发生 coefficient aliasing，输入 sequences 要 zero-pad 到足够长度，通常取不小于结果 coefficient 数量的 power of two。
Even/Odd split
把 polynomial 按 even 与 odd coefficients 拆开：
其中 Peven 与 Podd 各只有一半 coefficients。
当 x = ωₘ^k 时：
于是一个 size m 的 evaluation problem，变成两个 size m/2 的 DFT，再用：
在线性时间中合并。
递推式：
所以：
Inverse FFT
从 values 回到 coefficients 使用几乎相同的算法：
1. 把 root ωₘ 换成它的 inverse； 2. 最终每个输出除以 m。
因此 polynomial multiplication / convolution：
总时间：
FFT 的 conceptual hinge
FFT 不是“神秘公式让乘法变快”。它利用 roots of unity 的对称性，让对 x 的计算与对 -x 的计算共享同一对 half-size subproblems。
Binary search 丢掉一半搜索空间；Karatsuba 买掉一个递归乘法；FFT 则让后一半 evaluation 从前一半的结构里长出来。三种算法的表面距离很远，骨头却相似：不再为重复结构支付第二次全价。
把三棵递归树并排看
若分别背：
它们只是三行公式。若逐列比较，设计选择才出现：
| 算法 | children | child size | combine | 真正省下的东西 | |---|---:|---:|---:|---| | Binary Search | 1 | n/2 | Θ(1) | 一半候选空间 | | Merge Sort | 2 | n/2 | Θ(n) | 借有序性线性重组 | | Karatsuba | 3 | n/2 | Θ(n) | 第四次递归乘法 |
Gentner 等人的 analogical-encoding studies 提醒我们，比较 cases 能帮助 novice 抽取关系结构，而不只记住每个 case 的表面叙事；那些 studies 研究的是 negotiation learning，不是递归算法，因此这里只把它当作一个有边界的教学设计依据。对 D&C 来说，最值得比较的不是故事，而是 children / shrink / combine 三列。 Gentner, Loewenstein & Thompson, 2003
现在再看 FFT：
它与 Merge Sort 拥有相同 recurrence，却做着完全不同的数学工作。这也反过来提醒我们：recurrence 描述成本的形状，不等于描述算法的语义。
Master Theorem 不能做什么
它通常不能直接处理：
- T(n) = T(n - 1) + f(n)； - unequal subproblem sizes，如 T(n/3) + T(2n/3) + n； - a 或 b 随 n 变化； - 某些只差 logarithmic factors、却不落入课程版 Case 2 的 f(n)； - average-case recurrence，若期望与随机变量尚未正确建立。
这时可用：
- expansion / telescoping； - recursion tree； - substitution / induction； - 更一般的定理，但使用课程外工具时要解释条件。
定理的价值不在能套所有题，而在能迅速解决它适用的形状。把不合适的 recurrence 削成模板形状，只会把复杂度连同边角一起削错。
D&C 与 DP 的分界
| 问题 | Child subproblems | 典型方法 | |---|---|---| | Merge sort 左右半 | disjoint / independent | D&C | | Inversion counting 左右半 | independent，combine 处理跨界 | D&C | | Tower of Hanoi 的相同计数子问题 | equivalent / repeated | DP reuse | | Fibonacci naive recursion | 高度 overlapping | DP | | FFT even/odd coefficient sets | disjoint coefficients，共享结构化 evaluation | D&C | | Matrix Chain 的各种 split | 大量 overlapping intervals | DP |
“有没有 recursion”不是分类标准。关键是 child instances 是否独立，以及相同 state 是否会反复出现。
考场写法
Algorithm
Correctness
Complexity
然后说明用 Master Theorem、recursion tree 或求和得到 bound。不要直接从算法名字猜复杂度。
最容易失分的七处
1. Combine 没写：只说“递归两边”，没有说明答案怎样合并。 2. Cross-boundary cases 遗漏：例如 inversions 跨越左右 halves。 3. Binary search 没证明 monotonicity：答案空间未必是单一边界。 4. Search range 不清楚：log K 中的 K 没有定义。 5. Master Theorem 强行套：T(n - 1)、unequal splits 或 logarithmic gap 不满足版本条件。 6. Case 3 忘记 regularity：只比较 growth rates。 7. 模型混淆：large integer arithmetic 仍按 unit-cost，导致 Karatsuba 的问题规模失去意义。
--- 最后
Divide and Conquer 常被画成一棵向下分叉的树，但算法的创造力不只在 Divide。
Binary search 的决定是只让一根枝条活下去； inversion counting 的决定是在 merge 时顺便数完跨界关系；Karatsuba 的决定是用代数消掉一个昂贵 child； FFT 的决定则是挑选一组极其对称的 evaluation points，让两半递归结果可以同时回答正负两个方向。
树形只是舞台。 真正改变复杂度的，是让哪些信息在枝条之间重逢。
不过人生不会如递归树这般理想 分开然后是更好的重逢。
有些告别，只是寻常午后， 风吹过树叶， 便没有再见过那道背影。