子问题视角：分治与动态规划

分治算法

它是子问题视角的最简形态

两种思维里说过，子问题视角的做法是 让递归函数返回一个值，用子问题的答案拼出原问题的答案。

分治就是这句话的直接实现，只不过把「拼」这一步单独拎出来命名了：

分解 —— 把问题切成若干个规模更小、结构相同的子问题
解决 —— 递归地解决它们（base case 直接返回）
合并 —— 把子问题的答案拼成原问题的答案

⭐ 三步里只有第三步需要动脑。分解通常就是对半砍，解决是递归调用，真正决定这道题难不难的是「怎么合并」。看到一道分治题卡住了，九成是卡在合并上，不是卡在怎么分。

归并排序：合并是主戏

function mergeSort(nums) {
  if (nums.length <= 1) return nums;         // base case

  const mid = nums.length >> 1;
  const left = mergeSort(nums.slice(0, mid));   // 分解 + 解决
  const right = mergeSort(nums.slice(mid));

  return merge(left, right);                    // 合并
}

function merge(a, b) {
  const res = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) res.push(a[i++]);      // ⚠️ 这个 = 号见下
    else res.push(b[j++]);
  }
  while (i < a.length) res.push(a[i++]);
  while (j < b.length) res.push(b[j++]);
  return res;
}

分解只有一行 mid，合并占了整个 merge 函数 —— 这就是「合并才是主戏」。

🚨 `a[i] <= b[j]` 里的等号决定了排序稳不稳定

稳定排序指的是：值相等的元素，排序后的相对顺序和排序前一样。

a 是左半段、b 是右半段。两个值相等时：

写 <= —— 左半段的先出来，原来的先后顺序保住了，稳定
写 < —— 右半段的先出来，相等元素被调了个个儿，不稳定

⚠️ 这个 bug 用数字数组永远测不出来 —— 3 和 3 交换了位置你也看不见。只有排序的是对象（按某个字段排）时才会暴露，而那时候你多半已经忘了这一行。

📌 排数字随便写，排对象一定用 <=。JavaScript 内置的 Array.prototype.sort 在现代引擎里是稳定的（ES2019 起写进规范），自己写 merge 时别把这个性质弄丢了。

快速排序：合并是空的

function quickSort(nums, lo = 0, hi = nums.length - 1) {
  if (lo >= hi) return nums;

  const p = partition(nums, lo, hi);   // 先干活
  quickSort(nums, lo, p - 1);          // 再分解
  quickSort(nums, p + 1, hi);

  return nums;                          // 合并：什么都不用做
}

function partition(nums, lo, hi) {
  const pivot = nums[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi], nums[i]];
  return i;
}

⭐ 拿它跟归并对照，能看出一个很漂亮的对称：

	干活的位置	合并
归并排序	后序（子问题解决后）	是主戏
快速排序	前序（子问题解决前）	空的

这正是前中后序那三个时刻在排序算法上的体现。归并先分后治，快排先治后分 —— 两者加起来，恰好把「递归的两个位置」都用上了。

快速选择：只递归一半

快排每次 partition 之后，pivot 就落在它最终该在的位置上了。如果只想要第 k 大的那个数，根本不用把两边都排好 —— 看 pivot 的下标落在目标的哪一侧，只递归那一侧：

function findKthLargest(nums, k) {
  const target = nums.length - k;          // 第 k 大 = 升序里的下标 n-k
  let lo = 0, hi = nums.length - 1;
  while (true) {
    const p = partition(nums, lo, hi);     // 复用上面那个 partition
    if (p === target) return nums[p];
    if (p < target) lo = p + 1;            // 目标在右边，左边整段丢掉
    else hi = p - 1;
  }
}

[3,2,1,5,6,4]、k=2 → 5。

⭐ 丢掉一半带来的差别是量级上的：每层的规模是 n、n/2、n/4…，加起来是 O(n)，而不是排序的 n log n。

实测比较次数（数的是 partition 里 nums[j] < pivot 的执行次数；取中位数、找中位数最能体现平均行为；随机数据跑 201 轮取中位数，随机源用可播种的 mulberry32(7000+t) —— Math.random 播不了种，用它报出来的单个数字读者永远核对不了）：

数据形状	n=1000	n=4000
随机	3153 次（3.15n）	13100 次（3.27n）

⭐ 倍数在两个规模上都在 3.2n 附近，不随 n 增长 —— 这就是 O(n)。（上表 3.15n 和 3.27n 那点差别在噪声里，不是「涨了」，见下。）

🚨 那个「趋近 3.39n」的趋势是真的，但它小于测量噪声

理论渐近值是 3.39n，有限 n 下偏低。6 组种子各跑 201 轮取均值：

n	1000	4000	16000	64000
6 组均值	3.18n	3.23n	3.25n	3.27n
单组种子的跨度	0.16	0.23	0.27	0.11

趋势确实单调，可同一个 n 上换组种子就能得到 3.12n ~ 3.39n —— 单组种子的跨度比整个趋势的跨度（3.18 → 3.27，只有 0.09）还大。

🚨 所以拿单个种子测出来的「它涨了」或「它跌了」没有任何信息量。 我第一次就是这么写错的：随手一组种子在 n=16000 量到 3.32n，顺势写下「正往上靠」—— 换成正文这组种子是 3.12n，比 n=4000 那格还低。

⭐ 噪声是可以花时间买下来的，但得先知道自己在跟噪声比： n=4000 上把轮数从 201 加到 5001，三组种子的跨度从 0.147 收到 0.018。 📌 判据：报「随 n 变化的趋势」之前，先量一次同一个 n 上换种子的跨度。跨度盖过趋势，这个趋势就还没测出来。

⚠️ 随机数据每一轮都不同，所以这行报的是中位数，而只有分位数是稳的： n=1000 的那 201 轮里 p10 = 2211、p90 = 4628。 🚨 别报 min/max —— 换一组种子它们就变（8 组种子实测 min 在 999~~1610、 max 在 5815~~7900 之间跳）。而真正的下界是确定的 n−1：第一次 partition 就撞上 target，一次就返回，此后再无比较。 3000 轮里撞到过 2 次。📌 报一个抽样出来的最小值，会把这个确定的下界盖掉。

下面那两行已排序的数据则完全确定，你跑出来会是一模一样的数。

🚨 但最坏情况是 O(n²)，而「最坏输入」平淡得吓人

上面那个 partition 固定取 nums[hi] 当 pivot。 如果数组已经有序，每次切出来的都是空的一半，规模只减 1 不减半：

数据形状	n=1000	n=4000
随机（中位数）	3,153（3.15n）	13,100（3.27n）
已升序	374,750（375n）	5,999,000（1500n）
已降序	499,500（500n）	7,998,000（2000n）

⭐ 升序和降序差 1.33 倍 —— 因为切的方向不一样

已排序那两行都有闭式解，不用实测也能验。把每次 partition 的区间记下来就看清了：

已升序   partition 调用 500 次   [0,999] [0,998] [0,997] … [0,500] ← 命中
         pivot 恒是最大值 → 返回 hi → 只从右端切，走到 hi==target 就停
         Σ_{j=500}^{999} j = 374,750 ✓

已降序   partition 调用 1000 次  [0,999] [1,999] [1,998] [2,998] … [500,500]
         pivot 交替是最小值/最大值 → 返回 lo 和 hi 交替 → 两端轮流逼近，
         一次都没提前命中，一直做到区间只剩 1 个元素
         Σ_{j=1}^{999} j = 499,500 ✓

🚨 499,500 恰好等于 n(n−1)/2，也就是整个 quickSort 的最坏比较次数 —— 但这是巧合，两者机制不同。 quickSort 是切掉一个再递归剩下全部；这里是快速选择两端交替逼近、p === target 那个提前返回一次都没触发。 📌 数值撞上了就顺手写因果，是这类实测最容易出的错。两边都记一次账才分得清。

⚠️ 关键是看倍数那一列，不是看绝对值：随机数据 3.15n → 3.27n（不涨，差别在分位数宽度里），已排序 375n → 1500n（n 翻两番，倍数也翻两番）。 ⭐ 倍数随 n 线性增长，就是 O(n²) 的指纹 —— 这个读法比记住某个具体数字有用得多。

📌 而「已排序」不是什么刁钻构造，它是最常见的输入之一。判题机卡这道题用的就是它。

随机化 pivot：一行代码，省下的倍数随 n 线性增长

进 partition 之前先随机挑一个元素换到末尾：

const r = lo + Math.floor(Math.random() * (hi - lo + 1));
[nums[r], nums[hi]] = [nums[hi], nums[r]];   // 就这一行
const p = partition(nums, lo, hi);

在同样的已升序输入上实测（随机版 201 轮取中位数，同上用 mulberry32(7000+t)）：

n	固定末尾 pivot	随机 pivot（中位数）	省
500	93,625 次	1,605 次	58 倍
1000	374,750 次	3,244 次	116 倍
2000	1,499,500 次	6,517 次	230 倍
4000	5,999,000 次	13,073 次	459 倍
8000	23,998,000 次	26,188 次	916 倍

🚨 别记「省 N 倍」这个数字 —— 它不是常数，实测 ≈ n/8：n 翻倍，「省」也翻倍。这一节以前的标题写着「实测省 495 倍」，而表里从来没有 495 这个数（那时表只有 1000 和 4000 两行，116 倍和 455 倍）。 ⭐ 这正是上一节那条读法的反例，而且是自己打自己： 倍数随 n 线性增长恰恰说明左边那列是 O(n²)、右边是 O(n) —— 把它压成一个数字，就把结论本身丢掉了。

📌 加了随机化之后，已排序输入的开销（13,073）和随机输入（13,100） 差 0.2% —— 「最坏输入」这个概念被消解掉了。（两边用同一组种子、同一个口径量的；不同口径混着比会得出别的差值。）

⭐ 注意随机化并没有改变最坏复杂度 —— 理论上仍是 O(n²)，只是让「触发最坏」不再取决于输入长什么样，而取决于随机数。构造一个能稳定卡住它的输入，从「把数组排个序」变成了「猜中随机种子」。

⚠️ 分治不总是最优解：多数元素的两条路

多数元素（找出现次数 > n/2 的那个）有一个漂亮的分治解法：左右两半各自的多数元素，必有一个是整体的多数元素。但它是 O(n log n) 的，而这道题有 O(n) 时间、O(1) 空间的解 —— 摩尔投票：

function majorityElement(nums) {
  let cand = null, count = 0;
  for (const x of nums) {
    if (count === 0) cand = x;               // 票数归零，换一个候选人
    count += (x === cand) ? 1 : -1;          // 同票 +1，异票 -1
  }
  return cand;
}

⭐ 为什么成立：把每个「异票」和一个「同票」成对抵消掉。众数的数量 > n/2，也就是比其余所有元素加起来还多，所以无论怎么抵消，最后剩下的一定是它。

🚨 它依赖「众数一定存在」这个前提，而前提被打破时它不会报错。

2 万组随机数组里有 13437 组根本没有众数（长度 1–10、值域 0–3、 mulberry32(2026)），摩尔投票在这 13437 组上 全部返回了数组里确实存在的某个值，一次都没有异常：

[1,2,1,2,1,3,0,3]      → 返回 0   （它只出现了 1 次）
[0,1,0,3,3,0,3,2,0]    → 返回 0   （它只出现了 4 次，n=9 需要 ≥5）

📌 力扣 169 的题面明确保证众数存在，所以上面那段能过。但换成「可能不存在」的变体（或者你把它抄进真实项目），就必须再扫一遍验证：

const cand = majorityElement(nums);
let c = 0;
for (const x of nums) if (x === cand) c++;
return c > nums.length / 2 ? cand : -1;      // 多一遍 O(n)，换来结论可信

⚠️ 这和最近公共祖先那题是同一类陷阱：解法依赖题面给的前提，而返回值的形状不体现这个依赖 —— 前提不成立时它照样返回一个像模像样的答案。 ⭐ 判据：看到「题目保证……」这类措辞，就要意识到解法可能正在利用它。

至于为什么不用哈希计数（也是 O(n) 时间）：20 万个元素、6 万多个不同值时，哈希表要存 6 万多条，而摩尔投票始终只有两个变量。

主定理：够用的那个版本

递推式长这样时：

T(n) = a · T(n/b) + O(n^d)
       ↑        ↑       ↑
    几个子问题  规模缩小倍数  合并的代价

结论只看 d 和 log_b(a) 谁大：

条件	复杂度	直觉
d > log_b(a)	O(n^d)	合并的代价占主导
d = log_b(a)	O(n^d · log n)	每层代价相同，共 log n 层
d < log_b(a)	O(n^(log_b a))	叶子数量占主导

归并排序：切成 2 份（a=2）、每份规模减半（b=2）、合并是 O(n)（d=1）。 log₂2 = 1 = d，落在第二行 → O(n log n)。

📌 记不住三行也没关系，记住「比较合并代价和叶子数量，谁大听谁的」就够应付面试。

🚨 分治与动态规划的分界线：子问题重不重叠

这两者的框架长得几乎一样，都是「递归 + 用子问题答案拼」。唯一的区别是：

不同的分支会不会算到同一个子问题？

不会 → 分治。归并排序里，左半段和右半段是完全不同的元素，它们的子问题没有任何交集，所以不需要备忘录。
会 → 动态规划。斐波那契里 fib(5) 和 fib(4) 都要算 fib(3)，重复计算是指数级的，所以必须记下来。

⭐ 这条判据决定了你要不要加备忘录，而加错的代价是不对称的：

该加没加 → 指数级超时（斐波那契的 O(2ⁿ)）
不该加却加了 → 只是浪费一点内存，结果照样对

⚠️ 所以拿不准的时候倾向于加。真正的风险在另一边：看到「递归 + 返回值」就以为是分治、不去检查重叠性，然后被超时打回来 —— 而超时的报错不会告诉你原因是重叠子问题。

推导路径见动态规划解题框架那篇，它讲的正是「发现重叠之后该怎么办」。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

912. 排序数组中等归并或快排，自己实现
23. 合并 K 个升序链表困难分治两两合并，或用堆
169. 多数元素简单分治 O(n log n)，摩尔投票 O(n)/O(1)；⚠️ 后者依赖「众数一定存在」，前提没了也不报错
53. 最大子数组和中等分治与动规两种解法都值得写
215. 数组中的第K个最大元素中等⭐ 快速选择，只递归一半；已排序输入会退化成 O(n²)，随机 pivot 实测省 455 倍

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。