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