数据结构与算法 / 系统课时
分治算法的基本框架
分治算法的基本框架
分治算法把大问题拆成结构相同的小问题,分别求解后再合并结果。本课以归并排序为主示例,建立“分解、求解、合并”的固定分析路径,并据此推导时间与空间复杂度。
学习目标
- 区分递归调用方式与分治设计策略
- 掌握分解、求解和合并三个阶段
- 使用递推式分析归并排序复杂度
分治的三个阶段
分治通常满足三个条件:子问题与原问题结构相同、规模严格缩小、子问题之间相对独立。其通用过程是先拆分问题,再递归求解每个子问题,最后合并子结果。
text
solve(problem):
if problem is small enough:
return directAnswer
subProblems = divide(problem)
subResults = solve each subProblem
return combine(subResults)递归是一种实现手段,分治是一种设计策略。阶乘虽然递归调用自身,但每层只产生一个子问题,也没有合并多个子结果,通常不称为分治。

主示例:归并排序
示例采用闭区间 [left, right]。临时数组只创建一次并在递归中复用,避免每次合并重复分配大对象;相等时优先取左侧元素,从而保持排序稳定性。
java
import java.util.Arrays;
public class DivideAndConquerDemo {
public static void main(String[] args) {
int[] values = {8, 3, 6, 2, 7, 1, 5, 4};
mergeSort(values);
System.out.println(Arrays.toString(values));
}
public static void mergeSort(int[] values) {
if (values == null || values.length <= 1) {
return;
}
int[] temp = new int[values.length];
mergeSort(values, 0, values.length - 1, temp);
}
private static void mergeSort(
int[] values,
int left,
int right,
int[] temp
) {
if (left >= right) {
return;
}
int middle = left + (right - left) / 2;
mergeSort(values, left, middle, temp);
mergeSort(values, middle + 1, right, temp);
merge(values, left, middle, right, temp);
}
private static void merge(
int[] values,
int left,
int middle,
int right,
int[] temp
) {
int i = left;
int j = middle + 1;
int k = left;
// 两个子区间此时已经分别有序。
while (i <= middle && j <= right) {
temp[k++] = values[i] <= values[j]
? values[i++]
: values[j++];
}
while (i <= middle) {
temp[k++] = values[i++];
}
while (j <= right) {
temp[k++] = values[j++];
}
for (int index = left; index <= right; index++) {
values[index] = temp[index];
}
}
}预期输出:
text
[1, 2, 3, 4, 5, 6, 7, 8]复杂度如何得到
归并排序每次把规模为 n 的问题拆成两个约为 n / 2 的子问题,合并阶段线性扫描当前区间,因此递推式为:
递归树共有 O(log n) 层,每层处理元素总量为 O(n),所以时间复杂度是 O(n log n)。临时数组需要 O(n) 空间,递归栈需要 O(log n),总体额外空间仍为 O(n)。
边界与常见错误
闭区间拆分应使用 [left, middle] 和 [middle + 1, right],否则两个元素时可能反复进入相同区间。合并前必须先完成左右递归;主循环结束后,还要复制未耗尽的一侧元素。
中点写成 left + (right - left) / 2,可避免 left + right 在极端情况下溢出。分治并不天然高效,若拆分长期极不均衡,递归深度可能退化为 O(n)。
按自己的节奏,确认真正理解。