算法设计与分析-分治法
分治法
问题具有的特征
- 该问题的规模缩小到一定的程度就可以容易的解决
- 问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结 构性质。
- 问题分解的子问题的解可以合并为该问题的解（递归思想）
- 分解的各个子问题相互独立，子问题之间不包含公共子问题。(涉及分治法 效率问题，动态规划较好）
例子
divide-and-conquer(P)
{
if (|P|<N0)adhoc(P);//解决小规模的问题
divide P into smaller subinstances P1,P2，，，<Pk;//分解问题
for(i=1,i<=k,i++)
Yi=divide-and-conquer(Pi);//递归各子问题的解
renurn merge(Y1,…,Yk);//将各子问题的解合并为原问题的解
}
时间复杂度：
规模为n的问题，分解成k个规模为n/m的子问题，子问题解合并为原问题解需要f(n)的时间