分治法（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) {// 基础情况：空树深度为0if (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) 的分析。
应用场景：理解分治法在排序、搜索、树等数据结构中的应用。
与其他算法的区别：重点区分分治法与动态规划（子问题独立性）。