分治算法
约 1005 字大约 3 分钟
2019-06-09
概述
分治算法（Divide and Conquer） , 字面上的解释是「分而治之」。 把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
核心流程包含三步：
- 分解（Divide）：将原问题拆分为独立子问题
- 解决（Conquer）：递归求解子问题
- 合并（Combine）：将子问题的解合并为原问题的解
算法特征
- 该问题的规模缩小到一定的程度就可以容易地解决。
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
注意
如果各子问题是不独立的，则分治法要重复地解公共的子问题，也就做了许多不必要的工作。 此时虽然也可用分治法，但一般用 动态规划 较好。
过程
以归并排序为例。
假设实现归并排序的函数名为 mergeSort。明确该函数的职责，即 对传入的一个数组排序。 这个问题显然可以分解。给一个数组排序等于给该数组的左右两半分别排序，然后合并成一个数组。
function mergeSort(一个数组) {
if (可以很容易处理)
return
mergeSort(左半个数组)
mergeSort(右半个数组)
merge(左半个数组, 右半个数组)
}传给它半个数组，那么处理完后这半个数组就已经被排好了。 注意到，mergeSort 与二叉树的后序遍历模板极其相似。 因为分治算法的套路是 分解 -> 解决（触底）-> 合并（回溯），先左右分解，再处理合并，回溯就是在退栈，即相当于后序遍历。
merge 函数的实现方式与两个有序链表的合并一致。
分治示例
归并排序（经典分治）
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1)
return arr // 终止条件
// 分解阶段
const mid = Math.floor(arr.length / 2)
const left = mergeSort(arr.slice(0, mid))
const right = mergeSort(arr.slice(mid))
// 合并阶段
return merge(left, right)
}
function merge(left: number[], right: number[]): number[] {
let result: number[] = []
let i = 0
let j = 0
// 合并两个有序数组
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i++])
}
else {
result.push(right[j++])
}
}
// 处理剩余元素
return result.concat(left.slice(i)).concat(right.slice(j))
}
// 测试
const arr = [38, 27, 43, 3, 9, 82, 10]
console.log(mergeSort(arr)) // [3, 9, 10, 27, 38, 43, 82]分治算法优化技巧
- 避免重复计算：使用记忆化存储中间结果
- 尾递归优化：减少递归栈深度
- 迭代替代递归：降低空间复杂度
- 并行计算：子问题独立时可并行处理
适用场景
- 问题可分解为独立子问题（归并排序、快速排序）
- 子问题结构相似（二叉树遍历）
- 合并操作复杂度低于暴力求解（矩阵乘法）
- 问题具有递归特性（汉诺塔、斐波那契数列）
相关问题
基础分治应用
子问题合并技巧
分治优化：三路划分
进阶问题
- 4. 寻找两个有序数组的中位数（LeetCode）困难