分治 · 从递归式到随机化

「切开、递归、拼回」这三步几乎是所有分治算法的全部形状。真正把它们区分开的是代价, 而代价可以完全由一条递归式 $T(n) = aT(n/b) + f(n)$ 刻画: $a$ 是切出多少个子问题, $b$ 是规模缩小多少倍, $f$ 是切与拼两端的开销。把这条式子按 recursion tree 展开, 每层代价形成一个公比 $a/b^c$ 的等比数列, master theorem 的三种情形就是这个公比与 1 的三种大小关系。

建议顺序: 先读分治的骨架与复杂度把框架立住, 再看计数 · 取幂 · 大整数乘法里 Karatsuba 如何把 $a$ 从 4 压到 3, 最后是随机化与分治的交汇——quickselect 的期望线性、BFPRT 为买断最坏付出的常数, 以及 Las Vegas 与 Monte Carlo 的分野。

共同的骨架: 各 lab 把算法的执行过程预先展开成一串帧 (frame), 每帧是一份完整快照, 页面只持有一个游标, 前进 / 后退 / 自动播放都只是移动游标再重绘。本系列涉及随机的部分一律走自带种子的伪随机 (divide-conquer/core/rng.ts) —— 帧要能来回拖, 而 Math.random 会让回退后的重放落到另一条执行路径上。 master theorem

分治的骨架与复杂度

分治的全部代价信息压在递归式 $T(n) = aT(n/b) + f(n)$ 的三个参数里。按 recursion tree 逐层展开后，master theorem 的三种情形就是在问代价压在树根、各层还是叶子。

Karatsuba · 快速幂

计数 · 取幂 · 大整数乘法

三个与排序无关的分治。归并在合并时顺手数出跨半区的 inversion；快速幂折半的是指数而非规模；Karatsuba 用一次额外的加减法换掉第四次乘法，把 $a$ 从 4 压到 3。

quickselect

随机化与分治的交汇

quickselect 只递归含目标的那一半，随机 pivot 让每轮期望砍掉常数比例，期望代价线性。BFPRT 把最坏也压到线性，代价是常数变大。Las Vegas 与 Monte Carlo 分的是随机性落在时间上还是答案上。

相关链接

• 自适应归并排序 · Timsort 与 Powersort 本站 同一条 $T(n) = 2T(n/2) + \Theta(n)$ 的另一面: 那边问合并的顺序怎么定才省, 本系列问的是这条式子为什么等于 $n \log n$。
• 快速排序 · quicksort 本站 quickselect 的孪生兄弟: 同一套 pivot 与 partition, 一个只递归含目标的那半 (期望线性), 一个两半都要递归 (期望 $n \log n$)。
• 平面最近点对 · closest pair 本站 $a = b = 2$、$f = \Theta(n)$ 的现成实例, 难点全在证明「中缝带里只需检查常数个邻居」, 也就是把 $f$ 压到线性。
• Rabin-Karp · rolling hash 本站 本系列拿它作 Monte Carlo 的例子: 去掉逐字符确认那一步, 时间就成了定数, 而答案带上了碰撞概率。
• 动态规划 · 背包九讲 本站 分治与它的分界只有一条: 子问题重不重叠。不重叠则递归树各枝互不相干, 重叠则必须记账, 否则同一个子问题会被算指数次。
• Master theorem (analysis of algorithms) en.wikipedia.org 三种情形的严格陈述、正则性条件, 以及推广形式与 Akra-Bazzi 的关系。