分治法
含义
分而治之
将原问题分解成与原问题相同但是规模更小的子问题,可以反复执行这个过程, 使得问题规模减小到可以求解为止.
案例
- 快速排序
给定1000个数, 从小到大进行排序
- 凯苏傅里叶变换算法
- Karatsuba 大数乘法算法
关键点
- 数学归纳是使用分治思想
只要出现可以用数学归纳公式来表示的大规模问题, 第一反应就是分治算法,通过特定的函数参数安排, 肯定可以套用递归结构
- 分治思想不一定使用递归结构
递归结构是循环结构的一种, 所以分治思想也可以是循环结构
- 分治思想的核心是如何分
流程
- 划分问题: 整个问题划分成多个无关联的子问题
- 递归求解: 递归调用求解各个子问题
- 合并问题: 合并子问题的解, 形成原始问题的解
使用条件
- 问题缩小到一定规模就可以很容易解决
- 问题可以拆分成若干个小问题
- 子问题的解可以合并成该问题的解
- 同一层分解出来的子问题是相互独立的(子问题之间不包含公共的子问题)(非必须)
条件2, 3 是分治的前提, 即必要条件. 第4条, 对于存在公共子问题的问题, 使用分治算法会存在重复计算的问题, 使用DP较为合适
分治和DP的共同点和不同点
分治法
各子问题独立
动态规划
各子问题重叠