第三章：分治（Divide and Conquer）

一、 分治法核心知识点

1. 分治法的设计思想

• 核心理念：“凡治众如治寡，分数是也”。对于一个规模为 $n$ 的问题，若规模较小则直接解决；否则将其分解为 $k$ 个规模较小的子问题。
• 这些子问题必须互相独立且与原问题形式相同。
• 递归求解这些子问题，最后将各子问题的解合并得到原问题的解。
• 二分法：实践中发现，将问题分成大小相等的 $k=2$ 个子问题最为有效，这种平衡子问题的思想几乎总是优于子问题规模不等的做法。当 $k=1$ 时，这种策略被称为减治法。

2. 适用分治法的特征

• 问题规模缩小到一定程度易于解决。
• 问题可分解为若干规模较小的相同子问题。
• 子问题的解可以合并为该问题的解。
• 分解出的各个子问题相互独立（即子问题之间不包含公共的子问题）。

3. 求解过程（三大步骤）

• 分解：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
• 求解子问题：若子问题规模较小而易于解决则直接求解，否则递归地求解各个子问题。
• 合并：将各个子问题的解合并为原问题的解。

---

二、 经典例题与推导过程精讲

例题 1：快速排序 (Quick Sort)

• 题意描述：对含有 $n$ 个元素的序列进行排序。
• 算法设计与推导：
  • 分解：在序列中任取一个元素（通常取第一个）作为基准（pivot）。通过一趟扫描（Partition），将序列分割成两个子序列：左边所有元素 $\le$ 基准，右边所有元素 $\ge$ 基准，基准元素被放置在最终位置。
  • 求解：对左右两个子序列分别递归地重复上述过程，直至子序列长度为0或1（此时子序列天然有序，直接返回）。
  • 合并：由于排序是就地进行的（直接在原数组上交换元素），所以合并步骤不需要执行任何额外操作。
• 复杂度分析：在最好和平均情况下，每次划分能将序列分成长度大致相等的两半，时间复杂度为 $O(n \log_2 n)$。最坏情况下（如原序列已经有序），每次划分极度不平衡，时间复杂度退化为 $O(n^2)$。

例题 2：查找最大和次大元素 / 最大和最小元素

• 题意描述：在一个给定的无序序列中，找出最大和次大的两个不同元素，或寻找最大和最小元素。
• 算法设计与推导（最大和次大元素）：
  • 边界情况：若只有1个元素，max1 = a[low], max2 = -INF；若有2个元素，max1 = MAX(a[low], a[high]), max2 = MIN(a[low], a[high])。
  • 分解与求解：若元素 $>2$，将数组从中间 mid 一分为二，递归求出左区间的 (lmax1, lmax2) 和右区间的 (rmax1, rmax2)。
  • 合并：如果 lmax1 > rmax1，那么全局最大值 max1 = lmax1，而次大值 max2 则是左区间的次大值 lmax2 和右区间最大值 rmax1 中的较大者（即 MAX(lmax2, rmax1)）；反之亦然。
  • 复杂度：比较次数的递推式为 $T(n) = 2T(n/2) + 1$，时间复杂度为 $O(n)$。
• （最大和最小元素）的推导：
  • 基本逻辑类似，返回左右区间合并的结果：max = MAX(lmax, rmax)，min = MIN(lmin, rmin)。
  • 复杂度推导：递推式为 $T(n) = 2T(n/2) + 2$，利用展开法推导可得 $T(n) = \frac{3}{2}n - 2$。

例题 3：折半查找 (Binary Search)

• 题意描述：在一个有序序列中查找给定的关键字 $k$。
• 算法设计与推导：
  • 确定区间中点 mid = (low + high) / 2。
  • 若 $k == a[mid]$，查找成功，返回下标。
  • 若 $k < a[mid]$，说明 $k$ 必定位于左子表，新的查找区间更新为 $a[low \dots mid-1]$，递归查找。
  • 若 $k > a[mid]$，说明 $k$ 必定位于右子表，区间更新为 $a[mid+1 \dots high]$，递归查找。
• 复杂度分析：最坏情况下元素比较次数 $C(n) \le 1 + C(n/2)$，解得算法的时间复杂度为 $O(\log_2 n)$。

例题 4：寻找一个序列中第 k 小元素

• 题意描述：给定 $n$ 个元素的无序序列，求其中第 $k$ $(1 \le k \le n)$ 小的元素。
• 算法设计与推导：
  • 借用快速排序的 Partition 划分思想，以第一个元素为基准，将其放入最终下标 $i$ 处。
  • 计算基准元素是当前区间的第几个：$len = i - s + 1$。
  • 情况1：若 $k == len$，说明 $a[i]$ 恰好就是第 $k$ 小的元素，直接返回。
  • 情况2：若 $k < len$，说明目标元素在左半部分，递归在 $a[s \dots i-1]$ 中找第 $k$ 小元素。
  • 情况3：若 $k > len$，说明目标在右半部分，递归在 $a[i+1 \dots t]$ 中寻找第 $k - len$ 小的元素。
• 复杂度分析：递推方程 $T(n) = T(n/2) + O(n)$。最好和平均情况（每次划分比较均匀）下，时间复杂度为 $O(n)$；最坏情况（每次划分都在边缘）时间复杂度退化为 $O(n^2)$。

例题 5：寻找两个等长有序序列的中位数（重点）

• 题意描述：给定两个长度均为 $n$ 的升序序列 $a$ 和 $b$，求这两个序列合并后所有元素的中位数。
• 算法设计与推导：
  • 核心策略（舍弃法）：分别求出 $a$ 和 $b$ 当前区间的中位数 $a[m1]$ 和 $b[m2]$。每次比较后，舍弃掉不可能包含中位数的一半元素，从而将问题规模减半。
  • 若 $a[m1] == b[m2]$，则这个值就是全局中位数，直接返回。
  • 若 $a[m1] < b[m2]$：说明中位数一定不会出现在 $a$ 的前半部分（太小）和 $b$ 的后半部分（太大）。此时舍弃 $a$ 的前半段和 $b$ 的后半段。
    • 奇偶数边界处理（极易错点）：
    • 如果当前元素个数 $n$ 为奇数：保留 $a$ 的后半部分 $a[m1 \dots t1]$ 和 $b$ 的前半部分 $b[s2 \dots m2]$。
    • 如果当前元素个数 $n$ 为偶数：为了保证舍弃后两个序列仍然等长，保留 $a$ 的后半部分必须是 $a[m1+1 \dots t1]$（连同较小的中间元素一并舍弃），保留 $b$ 的前半部分为 $b[s2 \dots m2]$。
  • 若 $a[m1] > b[m2]$：舍弃 $a$ 的后半段和 $b$ 的前半段。处理方式与上述对称：奇数保留 $b[m2 \dots t2]$，偶数保留 $b[m2+1 \dots t2]$。
• 复杂度分析：每次将问题规模缩小一半，执行时间 $T(n) = T(n/2) + 1$，时间复杂度为 $O(\log_2 n)$。

例题 6：求解最大连续子序列和问题

• 题意描述：给定含有 $n$ 个整数的序列，求出其最大连续子序列的和。规定长度为0的子序列和为0（即如果全为负数则结果为0）。
• 算法设计与推导：
  • 取序列中间位置 $mid = (n-1)/2$。最大连续子序列可能存在于三个位置：
    1. 完全落在左半部 $a[0 \dots mid]$ 中。
    2. 完全落在右半部 $a[mid+1 \dots n-1]$ 中。
    3. 跨越序列中部，包含 $a[mid]$ 和 $a[mid+1]$。
  • 对于位置 1 和位置 2：直接递归调用，求出左半部最大和 maxLeftSum 以及右半部最大和 maxRightSum。
  • 对于位置 3：从 $mid$ 开始分别向左、向右连续扫描，分别求出左边延伸的最大和 maxLeftBorderSum 与右边延伸的最大和 maxRightBorderSum。然后将两者相加。
  • 最终结果：取上述三种情况的最大值，即 max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum)。
• 复杂度分析：求跨越中部最大和需要 $O(n)$ 次比较，递推式为 $T(n) = 2T(n/2) + n$，根据主方法解得时间复杂度为 $O(n \log_2 n)$。

例题 7：求解棋盘覆盖问题

• 题意描述：在一个 $2^k \times 2^k$ 的棋盘中，恰好有一个方格与其他不同（特殊方格）。用L型骨牌（占3个小方格）覆盖除特殊方格外所有方格，骨牌不重叠，求覆盖方法。
• 算法设计与推导：
  • 由于棋盘大小是 $4^k$，总共需要 $(4^k-1)/3$ 个L型骨牌。
  • 分解：将大棋盘十字划分为4个大小相同的 $2^{k-1} \times 2^{k-1}$ 的象限子棋盘。特殊方格必定落在其中一个象限中。
  • 骨牌放置与同构转化：在棋盘正中央（4个象限的交界处），放置一个L型骨牌，去覆盖另外3个没有特殊方格的象限的各一个角（即靠近中央的那个方格）。
  • 递归求解：通过放置这个L型骨牌，这3个象限也被人为地制造出了一个“特殊方格”（即被骨牌覆盖的那个方格）。此时，4个子棋盘都各自拥有了1个“特殊方格”，完全转化为了与原问题形式相同的较小规模子问题，分别递归处理即可。