← 算法课堂：换一种算法到底换了什么

同一种拆法，三种不同的收益

上一单元的结论很窄：Strassen 把 n/2 阶乘法从 8 次降到 7 次，指数从 3 降到 2.807，但实测要到约 700 阶才反超朴素实现——因为每次递归都复制子块，那笔 Θ(n² log n) 的搬运把优势推迟了很远。

这一单元把"分治"从矩阵乘法上取下来，换成三个更小的例子。它们的拆法几乎一样，收益来源却不同：

问题拆法递推式指数收益来自哪里
大整数乘法按位对半拆T(n) = 3T(n/2) + Θ(n)log₂3 ≈ 1.585指数从 2 降到 1.585
找第 k 大按值划分，丢掉不用的那半T(n) = T(n/2) + Θ(n)（平均）平均 1（线性）不是指数低，是不必处理的数据被丢掉了
最近点对按 x 中位线拆T(n) = 2T(n/2) + Θ(n log n)—合并在被筛过的条带里做

三个问题的递推式外观相似，但第三列的"收益来源"完全不同。这是本单元真正的题目：递推式只描述成本，不描述为什么值得拆。 同一份 T(n) = M·T(n/2) + f(n)，M 的下降可以来自"少算几块"，也可以来自"根本不用算"。

预计用时：60 分钟。前置是第一单元的递推式写法、交叉规模，以及《揭开黑盒》24–29 节。

账本要加一列

上一单元的四项（计算、搬运、准备、存储）在这里不够用。找第 k 大的快选实现里，内存写入次数随丢弃比例变化——它没有复制子块，只在原数组上交换。所以这一单元把"搬运"拆成两列：读与写。

方案计算读写准备存储
大整数·朴素n² 次单位乘2n²n²无n²
大整数·Karatsuban^1.585待测待测无（原地拆）n^1.585
第 k 大·全排序n log n 次比较待测待测无n
第 k 大·快选平均 ~3.4n 次比较待测待测无（原地划分）n

四行都必须由本单元的实验填满。填法沿用上一单元的规矩：先对拍，后计时；对拍不过，计时作废。

例一：大整数乘法的拆法

上一单元拆的是矩阵的行列维度，这里拆的是位。把 n 位大整数 a 从中间劈成两半：

a = a1 · 10^m + a0        m = ⌊n/2⌋
b = b1 · 10^m + b0

a · b = a1·b1 · 10^2m  +  (a1·b0 + a0·b1) · 10^m  +  a0·b0
                      \_______ z2 _______/   \___ z1 ___/   \_ z0 _/

朴素的拆法要算 4 次 n/2 位乘法（z2、a1·b0、a0·b1、z0）：

T(n) = 4·T(n/2) + Θ(n)     →  log₂4 = 2    与 n² 同阶

拆了等于没拆，指数还是 2。这正是上一单元在中段得出的那个观察——分治本身不减少工作量，减少工作量的是 M 的下降。

Karatsuba 只改一件事：z1 不算两次乘法，而是算 (a1+a0)·(b1+b0) 再减掉 z2 和 z0：

z1 = (a1+a0)·(b1+b0) − z2 − z0

一次乘法换两次加法，M 从 4 降到 3：

T(n) = 3·T(n/2) + Θ(n)     →  log₂3 ≈ 1.585

指数确实降下来了。但按上一单元的教训，降下来不等于立刻更快——(a1+a0) 这类加法是 Θ(n) 项，M 变小会让这一项在递推里被乘更多次。所以先写下会被反驳的预测：

会反驳 E1 的观察：比值不随位数上升。会反驳 E2 的观察：小位数上 Karatsuba 已经更快。

先对拍，再谈快慢

契约里的第一条规矩在这里最容易被违反。"乘法次数少了"会让人跳过正确性检查——一共就 3 次子乘法，看着就该对。事实上 Karatsuba 最容易错的地方恰好是减号：z1 − z2 − z0 里如果借位处理写成"高位补零"，结果会在某些输入上悄悄错一位。

本单元的独立参考用 BigInt：

function mulReference(a, b) {            // a、b 是数字数组，每项一位
  const A = BigInt(a.map(String).join(''));
  const B = BigInt(b.map(String).join(''));
  return (A * B).toString().split('').map(Number);
}

BigInt 走的不是被测实现的任何中间量，是真正独立的参考。对拍覆盖 8 到 512 位，朴素与 Karatsuba 各比对一次。

例二：找第 k 大——收益不是指数，是筛掉

这个问题和前一个看着不同，但拆法仍是分治。区别在于拆的对象：不是拆输入的下标，而是拆值的范围。

朴素做法是全排序后取第 k 个：

T(n) = Θ(n log n)

分治做法（Quickselect）随便取一个 pivot，把数组划成「比它大」「等于它」「比它小」三段：

若第 k 大落在「比它大」那段 → 只有那段的长度需要继续处理
若落在「等于它」那段       → 答案就是 pivot，直接返回
若落在「比它小」那段       → 只有那段需要继续处理

每次只保留含目标的那一段，其余全部丢弃。 平均情况下 pivot 落在中间，每轮丢掉一半：

T(n) = T(n/2) + Θ(n)     →  T(n) = Θ(n)

从 n log n 降到 n，但这里要看清一件事：指数并没有像 Karatsuba 那样"变小又变小"，而是第一轮就达到了线性，然后不再下降。 递推式 T(n) = T(n/2) + Θ(n) 的解是等比级数 2n + n + n/2 + ⋯ = Θ(n)，收敛的。它和 T(n) = 2T(n/2) + Θ(n) 只差一个系数 2，结论却整档不同——因为后者每轮两边都要处理，前者只处理一边。

这就是本节标题说的那件事：分治的收益有时不来自"指数更低"，而来自根本不进入不需要的那一半。 整趟下来处理的元素总数大约是 2n，而不是 n log n。

划分写得对不对，决定它会不会悄悄出错

这里的对拍比大整数更值得说，因为参考不能是"排序"。

如果我拿"排序后取第 k 个"当参考，而候选实现之一恰好就是"排序后取第 k 个"，那这个参考就和候选同源——它测不出划分的错误，只能测出排序的错误。所以本单元的参考换成计数法：不排序，在值域上二分，数出比中值大的元素有多少个：

function kthByCounting(values, k) {      // 独立于两种候选
  let lo = Math.min(...values), hi = Math.max(...values);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    let cnt = 0;
    for (const v of values) if (v > mid) cnt++;
    if (cnt >= k) lo = mid + 1; else hi = mid;
  }
  return lo;
}

这条参考路子和"排序"、和"就地划分"都不共享中间量。结果它抓出了一个真 bug。

一个被对拍抓出来的错误

直觉写法是两指针交换、返回左指针位置：

// 错的：只能保证两段分对，不能保证返回下标处的值等于 pivot
function partition(a, lo, hi, pivot) {
  let i = lo, j = hi;
  while (i <= j) {
    while (a[i] > pivot) i++;
    while (a[j] < pivot) j--;
    if (i <= j) { [a[i], a[j]] = [a[j], a[i]]; i++; j--; }
  }
  return i;                    // ← 问题在这
}

这个划分没有排错——它确实把大于 pivot 的放到了左边。错误的假设在返回值上：a[i] 处放的是某个大于 pivot 的元素，不是 pivot 本身，所以不能拿它当"第 i+1 大的值"。

举个最小例子，n=20：

原始:      349624, 570496, ..., 992512, 913408
划分返回 i = 12
降序全排序: [0..11] = 992512 ... 427712   [12] = 349624   [13..] = 332864 ...
但 a[12] 实测 = 195776        ← 只要结果落在下标 12，就会返回 195776

a[12] 已经被交换写坏，本来该在那个位置的是 349624。只要目标下标恰好落在 pivot 位置，就会返回错值；落在两边就碰巧对。 所以它不是每次错，是 21 组里错 5 组——这种"有时对"的错误最难查。

修法是换成三路划分，让 pivot 值本身归位，并返回它占据的区间：

// 对的：返回 [lt, gt]，[lt, gt] 内任意下标 q 都满足「a[q] 是第 q+1 大的值」
function partition(a, lo, hi, pivot) {
  let lt = lo, i = lo, gt = hi;
  while (i <= gt) {
    if (a[i] > pivot)      { [a[lt], a[i]] = [a[i], a[lt]]; lt++; i++; }
    else if (a[i] < pivot) { [a[i], a[gt]] = [a[gt], a[i]]; gt--; }
    else i++;
  }
  return [lt, gt];
}

修完 21 组全过，含"值域只有 1000 的同值密集"用例——三路划分本来就是为了同值密集设计的，中段会把所有等于 pivot 的元素一次性归位。

这个 bug 值得留在讲义里，不是因为它难，而是因为它演示了对拍的真正作用： 如果参考选成"排序"，或者只测了一两组 k，这个错误会带着"乘法更少所以更快"的结论一路进报告。契约把"先有独立参考"放在第一条，挡的就是这种情况。

实测数据

以下是在本机（Node.js 22，Windows，单线程）测得，对拍全部通过后计时才生效。脚本在 assets/algo-lab/divide-lab.mjs。

大整数：对拍结果。 8 / 16 / 32 / 64 / 128 / 256 / 512 位，朴素与 Karatsuba 全部与 BigInt 参考逐位相同。

找第 k 大：对拍结果。 21 组用例（n = 1000 / 10000 / 100000，各取 k = 1, 2, n/2, n-1, n；另加值域仅 1000 的同值密集用例）全部与计数法参考相同。

交叉规模：Karatsuba vs 朴素。 每档重复到单次 ≥ 5 ms、取 9 轮最小值以压低计时噪声：

位数朴素(ms)Karatsuba(ms)比值
640.04160.04880.85
1280.15200.14851.02
2560.58740.50431.17
5122.40481.55231.55
10249.57824.81291.99
204842.576415.76412.70
4096168.138248.91223.44

大位数上一路拉开，4096 位时 Karatsuba 快 3.44 倍，与 log₂3 的预测方向一致。

但交叉规模测不准，而且要如实写出来。 六次独立运行给出的"首次反超位数"分别是 85、102、104、105、119、127——落在 85～130 之间，不是同一个数。 加密网格（32 到 1024 取 13 档）看得更清楚，比值在 n = 96 到 200 之间反复贴着 1.0 上下穿：

位数运行一运行二运行三
960.8330.7940.914
1281.0111.0021.045
1600.8561.0300.964
1921.0031.1461.112
2561.2431.3041.167

n=160 这一档最说明问题：三次分别是 0.856、1.030、0.964，同一档在赢与输之间来回。到 n = 256 之后三次都稳定站上 1.17 以上，不再翻面。

所以本单元的结论不是"交叉规模 = 某个数"，而是：

交叉规模在 85～130 位之间，而 100～400 位这一段两种实现的差距经常小于测量噪声。 低于约 100 位，两者统计上打平；512 位及以上稳定由 Karatsuba 胜出（1.55 / 1.99 / 2.70 / 3.44）。

这不是测不出来，是这一段本来就没有可分辨的差别。给出一个精确到个位的交叉位数，等于把噪声当结论。第一单元给的 712～726 是同一个道理，只是那一段的噪声更小。

一个不能当成发现的异常点

加密网格时，n = 384 那一档出现过比值 0.940（回落到朴素更快），看起来像"交叉规模不是单调的"。复跑四次得到 0.987 / 1.415 / 0.830 / 1.430——同一档在 0.83 与 1.43 之间翻面，与 96～192 段是同一个现象。

记录它的理由有两条：

  1. 这个点差一点被写进结论，当成"交叉规模非单调"的发现。凡是"只出现一次、且与趋势不符"的数据点，都必须复跑。
  2. 复跑之后它并没有变成一个更小的疑点，而是扩大了噪声区间的上界：原本以为只有 96～200 位不可分辨，实际到 384 位仍然如此。

这带来一个必须写进报告的限制：本节的"高于约 250 位即稳定胜出"，是从 256 / 512 / 1024 三档都大于 1.2 推出的，但 384 档打断过这个单调性。 更稳妥的说法是"从约 400 位起稳定"，而 400 位以上本单元只测了 512 与更大——中间是否有别的翻面点，未测。

把边界写得比数据更宽，是因为数据自己不同意更窄的写法。

找第 k 大：快选 vs 全排序。 取 k = n/2，随机值与同值密集各测一次：

n场景全排序(ms)快选(ms)比值
10000随机1.200.157.96
10000同值密集0.810.145.67
50000随机6.630.5412.37
100000随机15.821.2512.65
500000随机82.666.9311.93
1000000随机168.6311.8114.28
1000000同值密集158.2016.369.67

大 n 上的比值在多次运行里落在 8.6～23 之间，这里给不出更窄的区间，原因本身就是一条结论：全排序耗时稳定（n=1000000 五次测得 155～212 ms），而快选只要 8～13 ms。分母这么小，单次调用的噪声就能把比值推动 ±40%。两种实现相差越悬殊，比值反而越难测准。

但趋势是干净的：比值大致随 n 上升，在 10 倍量级稳定下来。这个倍数明显大于大整数的 3.44 倍，原因不在实现质量，在问题的性质：

所以快选的收益能直接体现在耗时上，而 Karatsuba 的指数优势一部分被"输出规模不变"吃掉了。这是本单元最值得记住的一条：分治的收益上限，受问题要求你交出多少东西的约束。

同值密集场景并没有让快选变差（9～16，与随机场景同档）。三路划分在这里起了作用——中段一次归位，pivot 重复越多划分反而越快。

证据

按契约，最小交付：

// 大整数：参考是 BigInt，与两种实现都无关
const ref = mulReference(a, b);
if (!eq(mulNaive(a, b), ref) || !eq(mulKaratsuba(a, b), ref))
  throw new Error('大整数结果不对，后面所有计时作废');

// 找第 k 大：参考是计数法，不能是排序（否则与候选之一同源）
const expect = kthByCounting(values, k);
if (kthBySort(values, k) !== expect || kthQuickselect(values, k) !== expect)
  throw new Error('第 k 大结果不对，后面所有计时作废');

计时范围：包含调用、输入校验、输出分配与临时空间申请，不包含输入生成与参考计算。每档先热身一次；小规模（单次 < 5 ms）在计时循环内重复到 ≥ 5 ms 再取单次耗时，否则 performance.now() 的噪声会把比值推来推去——这一点是第一单元与第二单元的共同教训。

本节交付

填完开头那张账本表，另交一份报告：

项内容
输入与输出大整数位数范围、元素范围；第 k 大问题中 k 的取值约定（第 k 大，k 从 1 开始）
正确性BigInt 参考（大整数）与计数法参考（第 k 大）的逐项比对结果；21 组用例清单
基线实现朴素竖式 mulNaive、全排序 kthBySort，注明源文件版本
候选变化大整数只改一件事：子乘法由 4 次降为 3 次；第 k 大只改一件事：每轮只保留含目标的一段
成本账本计算、读、写、准备、存储分开记
实验设计大整数 7 个位数档；第 k 大 5 个 n 档 × 2 个场景；两次往返
证据原始样本、环境、计时边界、重复次数
未解决的问题见下

未解决的问题 一栏本单元至少留四项：

  1. 快选的平均 Θ(n) 依赖 pivot 落在中间。最坏情况（每次都取到极值元素）会退化成 Θ(n²)，本单元没有构造这样的输入，也没有测它的概率。中位数取三是降低概率，不是消除。
  2. 快选的递推式 T(n) = T(n/2) + Θ(n) 是平均值。报告里写"平均线性"时，是否写清了它是在均匀随机输入下的期望？
  3. Karatsuba 的交叉规模在 85～130 位之间给出，但 100～400 位整段都有翻面。这一段究竟是计时噪声，还是两种实现真的打平？ 若换成统计多次运行的分布而非最小值，能否把边界收窄？本单元未做。
  4. 三个例子共用同一个递推式结构，但收益来源不同。能不能把这个"来源"写成可检查的判据——也就是，看一个问题就能判断它的收益是来自"指数低"还是来自"筛掉数据"，不必先写出实现？
  5. 快选比全排序快十倍量级，导致它的耗时（8～13 ms）小到单次噪声能推动比值 ±40%。量一个"快得多的东西"需要比量一个"快一点的东西"更多的重复次数——本节的 5 ms 重复阈值对大整数够用，对快选不够。阈值该按什么定？

第三项是本单元真正的边界：我给了"不可分辨"这个结论，但没有证明它不可分辨。 第五项则暴露了一个反直觉的规律：优势越大，越难把优势量准。

一个刻意留空的例子

三个例子里，最近点对只列了递推式，没有实现。它是刻意留的——因为它的合并步骤引入了本单元还没出现的量：在条带里按 y 排序。这一步让 T(n) = 2T(n/2) + Θ(n log n) 里的 Θ(n log n) 成了主项，指数退回到 log₂2 = 1 的同一档，分治的收益完全不在指数上，而在合并只发生在被筛过的窄条带里。

换句话说，最近点对是把本节那句"收益来自筛掉不必处理的数据"推到极限的例子：它的拆法不带来任何指数优势，全部收益来自合并时不必两两比较所有点对。

它和快选的"筛"机制不同——快选筛掉的是输入的一半，最近点对筛掉的是候选点对的大部分。这个区别值得单独一节，本节不写：没有实测数据的一节，不值得占用一课时的位置。 它留在下一节的待办里。

与后续路线的接口

本单元为止，账本里的量都还在单机上。三个例子的搬运（读/写）都发生在同一块内存里。

从第三单元起，账本会多出一项无法在单机上演的量：通信——子任务拆到不同设备上之后，中间结果必须搬运，而搬运次数与拆法直接相关。矩阵乘法的分治拆开放在多设备上时，这个代价会盖过指数优势。

这条线通向第四单元（归约、扫描、通信代价）。

参考实现与自测

候选方案、独立参考与测量脚本在 assets/algo-lab/，零依赖，只需要 Node.js 18+：

node assets/algo-lab/divide-lab.mjs       # 对拍 + 交叉规模 + 快选计时
node --test assets/algo-lab/test.mjs      # 只跑正确性断言，不做计时

divide-lab.mjs 的第 1、2 步是全部规模的对拍；任何一项失败就打印"计时作废"并终止判定，不把数据当结论。计时结果不写进断言——本机耗时波动会导致换机器就红，那是环境差异，不是被测代码坏了。

上一单元的 strassen-lab.mjs 与 assets/math-lab/ 的实验台可以并行使用；本单元的三个实现都只依赖标准库，不需要 BigInt 之外的任何东西。

← 减法从哪一步开始目录