第4章 分治策略

导读

分治策略（Divide and Conquer）是算法设计中最基本、最重要的策略之一。其核心思想是将一个大问题分解为若干个规模较小的相似子问题，递归地求解这些子问题，然后将子问题的解合并为原问题的解。从归并排序到快速排序，从大整数乘法到矩阵乘法，从最近点对问题到凸包问题，分治策略的应用无处不在。

本章将深入探讨分治策略的设计思想、分析方法和典型应用。我们将学习如何建立和求解递归式，掌握主定理的使用方法，并通过一系列经典算法来理解分治策略的威力和局限性。

核心概念详解

4.1 分治策略的基本框架

分治策略遵循三个步骤：

分解（Divide）：将原问题分解为若干个规模较小的子问题。理想情况下，子问题之间相互独立且规模大致相等。

解决（Conquer）：递归地求解各子问题。当子问题规模足够小时，直接求解（基本情况）。

合并（Combine）：将子问题的解组合成原问题的解。

分治策略的关键在于分解和合并步骤的设计。好的分解方式可以使问题规模快速缩小，而高效的合并步骤则确保整体效率。

4.2 递归式的建立与求解

分治算法的时间复杂度通常用递归式来描述。建立递归式的关键是分析三个步骤的代价：

T(n) = 分解代价 + 子问题求解代价 + 合并代价

常见递归式类型：

类型1：等分递归

T(n) = aT(n/b) + f(n)

• a个子问题，每个规模为n/b
• f(n)为分解和合并的代价
• 示例：归并排序 T(n) = 2T(n/2) + O(n)

类型2：不等分递归

T(n) = T(αn) + T((1-α)n) + f(n)

• 子问题规模不均匀
• 示例：快速排序（平均情况）T(n) = T(k) + T(n-k-1) + O(n)

类型3：递减递归

T(n) = T(n-1) + f(n)

• 每次规模减1
• 示例：某些动态规划问题

4.3 主定理（Master Theorem）

主定理是求解形如T(n) = aT(n/b) + f(n)的递归式的通用工具。其中a ≥ 1, b > 1。

设n^(log_b a)为"临界指数"，比较f(n)与n^(log_b a)的增长率：

情况1：若f(n) = O(n^(log_b a - ε))，对某个常数ε > 0

则T(n) = Θ(n^(log_b a))

子问题的求解代价占主导。

情况2：若f(n) = Θ(n^(log_b a))

则T(n) = Θ(n^(log_b a) · log n)

子问题代价和合并代价相当。

情况3：若f(n) = Ω(n^(log_b a + ε))，对某个常数ε > 0

且满足正则条件：af(n/b) ≤ cf(n)，对某个c < 1和足够大的n

则T(n) = Θ(f(n))

合并代价占主导。

示例分析：

• T(n) = 8T(n/2) + n²：a=8, b=2, log_b a = 3, f(n) = n² = O(n^(3-ε))，情况1，T(n) = Θ(n³)
• T(n) = 2T(n/2) + n：a=2, b=2, log_b a = 1, f(n) = n = Θ(n¹)，情况2，T(n) = Θ(n log n)
• T(n) = 2T(n/2) + n²：a=2, b=2, log_b a = 1, f(n) = n² = Ω(n^(1+ε))，情况3，T(n) = Θ(n²)

4.4 最大子数组问题

最大子数组问题（Maximum Subarray Problem）是分治策略的经典应用：给定一个整数数组，找到和最大的连续子数组。

分治解法：

分解：将数组从中间分成两半

解决：递归地找左半部分和右半部分的最大子数组

合并：最大子数组要么在左半部分，要么在右半部分，要么跨越中间。跨越中间的情况需要额外计算。

时间复杂度：T(n) = 2T(n/2) + O(n) = O(n log n)

Kadane算法（动态规划解法）：

实际上，这个问题可以用动态规划在O(n)时间内解决，比分治更高效。这说明分治并不总是最优策略。

4.5 Strassen矩阵乘法

标准矩阵乘法的时间复杂度为O(n³)。Strassen算法通过分治策略将其降低到O(n^2.807)。

基本思想：

将n×n矩阵分成4个(n/2)×(n/2)的子矩阵，通过7次(n/2)×(n/2)矩阵乘法（而非通常的8次）来计算结果。

递归式：T(n) = 7T(n/2) + O(n²)

由主定理：a=7, b=2, log_2 7 ≈ 2.807, f(n) = n² = O(n^(2.807-ε))

因此T(n) = Θ(n^log_2 7) ≈ Θ(n^2.807)

虽然Strassen算法在理论上更快，但由于较大的常数因子，只在矩阵规模很大时才优于标准算法。

4.6 递归树方法

递归树是求解递归式的直观方法。将递归式的展开画成树形结构：

构建步骤：

根节点表示原问题的代价f(n)

每个节点有a个子节点，表示a个子问题

子节点的代价为f(n/b)

叶子节点的代价为T(1)

计算方法：

计算每层的总代价

确定树的深度（叶子节点对应的规模）

将所有层的代价求和

示例：T(n) = 3T(n/4) + cn²

• 第0层：cn²
• 第1层：3c(n/4)² = 3cn²/16
• 第2层：9c(n/16)² = 9cn²/256
• 每层代价以3/16的比例递减
• 总代价 = cn²(1 + 3/16 + 9/256 + ...) = cn² · 1/(1-3/16) = O(n²)

4.7 代入法

代入法通过猜测解的形式，然后用数学归纳法证明。

步骤：

猜测解的形式（可通过递归树或其他方法获得直觉）

用数学归纳法证明

示例：证明T(n) = 2T(n/2) + n的解为O(n log n)

• 假设T(k) ≤ ck log k对所有k < n成立
• T(n) = 2T(n/2) + n ≤ 2c(n/2)log(n/2) + n = cn(log n - 1) + n = cn log n - cn + n
• 当c ≥ 1时，-cn + n ≤ 0，因此T(n) ≤ cn log n
• 证毕

4.8 分治策略的变体

减治法（Decrease and Conquer）：

每次只产生一个子问题，规模比原问题小。

• 示例：插入排序 T(n) = T(n-1) + O(n)

变治法（Transform and Conquer）：

先将问题变换为更易求解的形式，再求解。

• 示例：预排序、平衡二叉搜索树

分治的并行化：

分治策略天然适合并行计算。子问题可以独立地在不同处理器上求解，最后合并结果。

4.9 分治策略的局限性

分治策略并非万能，其局限性包括：

子问题不独立：当子问题之间有重叠时，分治会导致大量重复计算。此时应使用动态规划。

分解或合并代价过高：如果分解或合并步骤的代价太大，分治可能不如其他方法。

问题不可分：某些问题天然不具有可分性，无法有效分解为子问题。

常数因子过大：分治的递归调用和合并步骤可能引入较大的常数因子。

重要知识点

知识点1：递归式的三种求解方法

• 代入法：先猜测后证明，需要一定的直觉和经验
• 递归树法：直观但不够严格，适合获得猜测
• 主方法：直接套用，但只适用于特定形式

实际分析中，通常先用递归树获得猜测，再用代入法证明。

知识点2：主定理的边界情况

主定理不能覆盖所有情况。例如：

• T(n) = 2T(n/2) + n/log n：f(n)不在主定理的三种情况中
• T(n) = 2T(n/2) + n log n：同样不在主定理范围内

这类递归式需要其他方法求解。

知识点3：分治与递归的关系

分治策略通常通过递归来实现，但两者不是同一概念：

• 分治是算法设计策略
• 递归是编程技术
• 分治算法通常用递归实现，但递归不一定都是分治

知识点4：子问题规模的平衡

分治的效率与子问题规模的平衡密切相关：

• 平衡分治（子问题规模相等）通常效率最高
• 不平衡分治可能导致递归树退化为链状

知识点5：分治的内存访问模式

分治算法的内存访问模式对实际性能有重要影响：

• 良好的局部性可以利用缓存
• 归并排序的合并步骤对缓存不友好
• 快速排序的分区步骤对缓存友好

常见误区

误区1：分治总是比简单方法好

分治策略引入了递归调用的开销和合并步骤的代价。对于小规模问题，简单的迭代方法可能更快。实际中常采用混合策略：大规模用分治，小规模切换到简单方法。

误区2：递归式只能用于分治算法

递归式可以描述任何递归过程的时间复杂度，不仅限于分治算法。例如回溯算法、递归遍历等都可以用递归式分析。

误区3：主定理可以解决所有递归式

主定理只适用于T(n) = aT(n/b) + f(n)形式的递归式，且f(n)需要满足特定条件。对于更复杂的递归式，需要使用其他方法。

误区4：分治的子问题必须规模相等

虽然等分通常是最优的，但分治并不要求子问题规模相等。快速排序的分区可能产生不均匀的子问题，但仍然是分治策略。

误区5：递归深度越大越慢

递归深度大不一定意味着运行时间长。例如二分查找的递归深度为O(log n)，但每次只做O(1)工作，总时间为O(log n)。

实践应用

应用1：大规模数据处理

分治策略在大规模数据处理中广泛应用：

• MapReduce：Google的大规模数据处理框架，核心思想就是分治
• 分布式排序：将数据分块，各节点排序后归并
• 分布式搜索：在多个节点上并行搜索

应用2：计算几何

分治策略在计算几何中有重要应用：

• 最近点对：将点集分成两半，递归求解，合并时检查跨越分界线的点对
• 凸包：分治求解左右凸包，然后合并
• Voronoi图：递归地将空间分割

应用3：信号处理

快速傅里叶变换（FFT）是分治策略的经典应用：

• 将N点DFT分解为两个N/2点DFT
• 递归分解直到N=1
• 时间复杂度从O(N²)降低到O(N log N)

应用4：数值计算

大整数乘法的分治算法：

• Karatsuba算法：将n位数乘法分解为3次n/2位数乘法，O(n^1.585)
• Toom-Cook算法：更一般的分解方法
• Schönhage-Strassen算法：基于FFT，O(n log n log log n)

应用5：并行算法设计

分治策略是并行算法设计的基础：

• 任务并行：子问题在不同处理器上并行求解
• 数据并行：数据分块后并行处理
• 工作窃取（Work Stealing）：动态平衡各处理器的工作量

4.10 分治策略的更多经典应用

快速傅里叶变换（FFT）：

FFT是分治策略在信号处理中的经典应用。将N点离散傅里叶变换分解为两个N/2点的DFT：

X[k] = Σ(n=0 to N-1) x[n] · e^(-2πink/N)

将偶数下标和奇数下标分开：

X[k] = Σ(m=0 to N/2-1) x[2m] · e^(-2πimk/(N/2)) + e^(-2πik/N) · Σ(m=0 to N/2-1) x[2m+1] · e^(-2πimk/(N/2))

递归分解，时间从O(N²)降到O(N log N)。

大整数乘法：

Karatsuba算法：将n位数x分为x₁·10^(n/2) + x₀，y类似。

xy = x₁y₁·10^n + (x₁y₀ + x₀y₁)·10^(n/2) + x₀y₀

关键观察：x₁y₀ + x₀y₁ = (x₁+x₀)(y₁+y₀) - x₁y₁ - x₀y₀

只需3次n/2位乘法，递归式T(n) = 3T(n/2) + O(n)，解为O(n^log₂3) ≈ O(n^1.585)。

最近点对问题：

给定平面上n个点，找最近的点对。

分治算法：

按x坐标排序，从中间分成两半

递归找左右两半的最近点对

合并：检查跨越分界线的点对

关键优化：只需检查距分界线<δ的点（δ为左右最近距离的最小值）

时间：T(n) = 2T(n/2) + O(n) = O(n log n)

凸包问题：

分治法求凸包：

找最左和最右点，连线将点集分为两半

递归求两半的凸包

合并两个凸包

时间：O(n log n)

4.11 主定理的扩展和局限

主定理不能处理的情况：

T(n) = 2T(n/2) + n/log n

- f(n) = n/log n，不在主定理的三种情况中

- 需要使用扩展主定理或其他方法

T(n) = 2T(n/2) + n·log n

- f(n) = n·log n，比n大但比n^(1+ε)小

- 不在主定理范围内

扩展主定理：

对于T(n) = aT(n/b) + f(n)，如果f(n) = Θ(n^(log_b a) · log^k n)，则T(n) = Θ(n^(log_b a) · log^(k+1) n)。

Akra-Bazzi方法：

更一般的递归式求解方法，可以处理T(n) = Σ aᵢT(n/bᵢ) + f(n)形式的递归式。

4.12 分治算法的缓存分析

缓存模型：

现代计算机有层次化的缓存结构。缓存行（cache line）通常为64字节。顺序访问内存可以利用缓存预取，而随机访问会导致缓存未命中。

分治算法的缓存友好性：

• 归并排序：合并步骤需要访问两个不连续的子数组，缓存不友好
• 快速排序：分区步骤顺序扫描数组，缓存友好
• 矩阵乘法：朴素算法按行访问缓存友好，按列访问缓存不友好

缓存 oblivious 算法：

某些分治算法不需要知道缓存大小就能自适应缓存：

• 缓存 oblivious 归并排序：使用递归的"漏斗排序"
• 缓存 oblivious 矩阵转置：递归分块

本章小结

本章深入探讨了分治策略的设计思想和分析方法。我们学习了：

分治策略的三步框架：分解、解决、合并。关键在于子问题的独立性和合并的高效性。

递归式的求解方法：代入法（猜测+证明）、递归树法（直观展开）、主方法（直接套用）。

主定理：对于T(n) = aT(n/b) + f(n)形式的递归式，通过比较f(n)和n^(log_b a)的增长率直接确定解。主定理有局限性，某些情况需要扩展方法。

经典应用：最大子数组问题、Strassen矩阵乘法、FFT、Karatsuba大整数乘法、最近点对、凸包等。

局限性：子问题不独立时应使用动态规划，分解或合并代价过高时分治可能不优。

缓存分析：分治算法的缓存友好性对实际性能有重要影响。

分治策略是算法设计的基石。掌握分治策略，不仅能解决大量实际问题，更为理解更复杂的算法设计策略（如动态规划、贪心算法）奠定基础。

关键术语

思考题

使用递归树方法求解T(n) = 4T(n/3) + n log n的渐近界。

设计一个分治算法，在O(n log n)时间内找到数组中第k大的元素。

分析当Strassen算法中的7次乘法改为8次时，时间复杂度如何变化。

证明或反驳：对于所有递归式T(n) = aT(n/b) + f(n)，主定理的三种情况覆盖了所有可能的f(n)。