分治法（Divide and Conquer）是计算机科学中最经典的算法设计思想之一，其核心思想是将复杂问题分解为若干个规模较小的子问题，通过解决子问题并合并结果来求解原问题。这种思想不仅在排序、搜索等基础算法中广泛应用，也是考研计算机专业基础综合（408）的核心考点。
分治法核心思路
算法定义与步骤
分治法的字面含义是 “分而治之”，其基本流程可分为三个步骤：
- 分解（Divide）：将原问题分解为若干个与原问题结构相似但规模更小的子问题。
- 解决（Conquer）：若子问题规模足够小，则直接求解；否则递归求解子问题。
- 合并（Combine）：将子问题的解合并为原问题的解。
适用条件
并非所有问题都适合用分治法解决，其适用条件包括：
- 可分解性：原问题可分解为规模较小的相似子问题。
- 独立子问题：子问题之间相互独立，不存在重叠依赖（否则更适合动态规划）。
- 可合并性：子问题的解可有效合并为原问题的解。
- 基础情况：存在最小子问题的直接解法。
典型应用场景
分治法在计算机科学中应用广泛，典型场景包括：
- 排序算法：归并排序、快速排序。
- 搜索问题：二分查找、寻找第 k 大元素。
- 矩阵运算：Strassen 矩阵乘法。
- 组合问题：全排列、子集和。
- 图论问题：最近点对问题、连通分量求解。
分治法在 LeetCode 中的实战
例题 1：912. 排序数组（中等）
题目描述：给你一个整数数组 nums，请你将该数组升序排列。
示例：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解题思路（归并排序）
归并排序是分治法的经典应用，其步骤为：
- 分解：将数组从中间分为左右两个子数组，递归分解直至子数组长度为 1（可直接求解）。
- 解决：当子数组长度为 1 时，数组天然有序。
- 合并：将两个有序子数组合并为一个更大的有序数组（核心步骤）。
代码实现
class Solution {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int n = nums.length;
int[] temp = new int[n]; // 临时数组，用于合并
mergeSort(nums, 0, n - 1, temp);
return nums;
}
// 分解：将数组[left..right]排序
private void mergeSort(int[] nums, int left, int right, int[] temp) {
if (left < right) {
int mid = left + (right - left) / 2; // 避免溢出
mergeSort(nums, left, mid, temp); // 左子数组排序
mergeSort(nums, mid + 1, right, temp); // 右子数组排序
merge(nums, left, mid, right, temp); // 合并两个有序子数组
}
}
// 合并：将[left..mid]和[mid+1..right]合并为有序数组
private void merge(int[] nums, int left, int mid, int right, int[] temp) {
int i = left; // 左子数组指针
int j = mid + 1; // 右子数组指针
int k = left; // 临时数组指针
// 比较并合并元素
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 处理左子数组剩余元素
while (i <= mid) {
temp[k++] = nums[i++];
}
// 处理右子数组剩余元素
while (j <= right) {
temp[k++] = nums[j++];
}
// 复制临时数组到原数组
for (k = left; k <= right; k++) {
nums[k] = temp[k];
}
}
}复杂度分析
- 时间复杂度：O (nlogn)。分解过程产生 logn 层递归，每层合并操作总时间为 O (n)。
- 空间复杂度：O (n)。需要临时数组存储合并结果。
- 分治体现：通过递归分解数组为子数组，合并子数组的解（有序子数组）得到原数组的解（有序数组）。
例题 2：215. 数组中的第 K 个最大元素（中等）
题目描述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
示例：
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
解题思路（快速选择算法）
快速选择算法基于分治法，是快速排序的变种：
- 分解：随机选择基准元素（pivot），将数组分为三部分：小于 pivot、等于 pivot、大于 pivot。
- 解决：通过基准元素的位置判断是否为目标元素：
-
- 若基准位置等于 n - k（n 为数组长度），则基准元素即为第 k 大元素。
-
- 若基准位置小于 n - k，则递归处理右子数组。
-
- 若基准位置大于 n - k，则递归处理左子数组。
- 合并：无需合并，直接返回找到的目标元素。
代码实现
class Solution {
private Random random = new Random();
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
int targetIndex = n - k; // 第k大元素在有序数组中的索引
return quickSelect(nums, 0, n - 1, targetIndex);
}
// 分治：在nums[left..right]中寻找索引为target的元素
private int quickSelect(int[] nums, int left, int right, int target) {
if (left == right) {
return nums[left]; // 子数组长度为1，直接返回
}
// 分解：分区并返回基准元素位置
int pivotIndex = randomPartition(nums, left, right);
// 解决：判断基准位置是否为目标
if (pivotIndex == target) {
return nums[pivotIndex];
} else if (pivotIndex < target) {
return quickSelect(nums, pivotIndex + 1, right, target); // 递归右子数组
} else {
return quickSelect(nums, left, pivotIndex - 1, target); // 递归左子数组
}
}
// 随机选择基准并分区
private int randomPartition(int[] nums, int left, int right) {
int pivotPos = left + random.nextInt(right - left + 1); // 随机选择基准位置
swap(nums, pivotPos, right); // 将基准元素移至末尾
return partition(nums, left, right);
}
// 分区：将小于基准的元素放左边，大于基准的放右边
private int partition(int[] nums, int left, int right) {
int pivot = nums[right];
int i = left - 1; // 小于基准区域的边界
for (int j = left; j < right; j++) {
if (nums[j] <= pivot) {
i++;
swap(nums, i, j); // 扩展小于基准的区域
}
}
swap(nums, i + 1, right); // 将基准元素放至最终位置
return i + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}复杂度分析
- 时间复杂度：平均 O (n)，最坏 O (n²)（随机化后最坏情况概率极低）。
- 空间复杂度：O (logn)，来自递归栈（平均情况）。
- 分治体现：通过分区将原问题分解为规模更小的子问题（寻找子数组中的目标元素），递归求解后直接返回结果。
考研 408 例题解析
例题 1：概念辨析题（选择题）
题目：下列关于分治法的叙述中，正确的是（ ）。
A. 分治法的时间复杂度总是优于蛮力法
B. 分治法要求子问题必须完全独立，无任何关联
C. 分治法的合并步骤对算法效率无影响
D. 快速排序和归并排序的分治策略完全相同
答案：B
解析：
- A 错误：分治法的时间复杂度取决于子问题规模和合并成本，例如某些问题的分治法时间复杂度可能与蛮力法相同（如寻找最大值）。
- B 正确：分治法要求子问题独立，若存在重叠子问题，动态规划更合适。
- C 错误：合并步骤的效率直接影响算法总复杂度（如归并排序的合并步骤为 O (n)，是总复杂度的关键）。
- D 错误：快速排序的分解基于基准元素分区，合并步骤可省略；归并排序的分解是等分，合并步骤为核心。
例题 2：算法设计题（408 高频考点）
题目：设计一个分治算法，求二叉树的深度。二叉树的深度是指从根节点到最远叶子节点的最长路径上的节点数。
解题思路：
- 分解：将二叉树分解为左子树和右子树两个子问题。
- 解决：递归求解左子树深度和右子树深度。
- 合并：二叉树的深度为左、右子树深度的最大值加 1（根节点）。
基础情况：空树的深度为 0。
代码实现：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class TreeDepth {
public int maxDepth(TreeNode root) {
// 基础情况：空树深度为0
if (root == null) {
return 0;
}
// 分解：求左、右子树深度
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
// 合并：取最大值加1（当前节点）
return Math.max(leftDepth, rightDepth) + 1;
}
}复杂度分析：
- 时间复杂度：O (n)，每个节点被访问一次。
- 空间复杂度：O (h)，h 为树的深度（递归栈空间）。
- 分治体现：通过递归分解为左、右子树的深度问题，合并时取最大值加 1 得到原树深度。
例题 3：综合应用题
题目：使用分治法求 n 个元素的最大子数组和（子数组是连续的）。例如，数组 [-2,1,-3,4,-1,2,1,-5,4] 的最大子数组和为 6（对应子数组 [4,-1,2,1]）。
解题思路：
- 分解：将数组从中间分为左半部分、右半部分、跨越中点的子数组三部分。
- 解决：
-
- 递归求左半部分的最大子数组和。
-
- 递归求右半部分的最大子数组和。
-
- 直接求跨越中点的最大子数组和（从中间向左扩展求最大左和，向右扩展求最大右和，总和为两者之和）。
- 合并：原数组的最大子数组和为三部分的最大值。
代码实现：
public class MaximumSubarray {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
return maxSubArray(nums, 0, nums.length - 1);
}
private int maxSubArray(int[] nums, int left, int right) {
if (left == right) {
return nums[left]; // 基础情况：单元素子数组
}
int mid = left + (right - left) / 2;
// 分解：求左、右、跨越中点的最大子数组和
int leftMax = maxSubArray(nums, left, mid);
int rightMax = maxSubArray(nums, mid + 1, right);
int crossMax = maxCrossingSum(nums, left, mid, right);
// 合并：取三者最大值
return Math.max(Math.max(leftMax, rightMax), crossMax);
}
// 求跨越中点的最大子数组和
private int maxCrossingSum(int[] nums, int left, int mid, int right) {
// 向左扩展求最大和
int leftSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = mid; i >= left; i--) {
sum += nums[i];
leftSum = Math.max(leftSum, sum);
}
// 向右扩展求最大和
int rightSum = Integer.MIN_VALUE;
sum = 0;
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
rightSum = Math.max(rightSum, sum);
}
return leftSum + rightSum;
}
}复杂度分析：
- 时间复杂度：O (nlogn)。分解为两个规模为 n/2 的子问题，合并步骤（求跨越中点的最大和）为 O (n)，递归方程为 T (n) = 2T (n/2) + O (n)。
- 空间复杂度：O (logn)，来自递归栈。
分治法的扩展与考研 408 考点总结
分治法与其他算法的对比
算法思想 |
核心策略 |
适用场景 |
典型算法 |
分治法 |
分解为独立子问题 |
子问题无重叠，可合并 |
归并排序、快速选择 |
动态规划 |
分解为重叠子问题 |
子问题有重叠，需记录中间结果 |
斐波那契数列、最短路径 |
贪心算法 |
局部最优决策 |
问题具有贪心选择性质 |
哈夫曼编码、活动选择 |
考研 408 中的分治法考点
- 算法设计：能根据问题设计分治策略（如二叉树深度、最大子数组和）。
- 复杂度分析：掌握递归方程求解（主方法、递归树法），如 T (n) = aT (n/b) + f (n) 的分析。
- 应用场景：理解分治法在排序、搜索、树等数据结构中的应用。
- 与其他算法的区别：重点区分分治法与动态规划（子问题独立性）。
总结
分治法作为一种经典的算法设计思想，通过 “分解 - 解决 - 合并” 的流程，将复杂问题转化为可处理的子问题，在计算机科学中有着不可替代的地位。
掌握分治法不仅需要理解其核心步骤，更要能根据问题特性判断是否适用，并设计合理的分解与合并策略。在考研备考中，分治法的复杂度分析和算法设计是重点，需结合具体问题深入练习。
希望本文能够帮助读者更深入地理解分治法，并在实际项目中发挥其优势。谢谢阅读！
希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。
