分治算法的思想:
将规模大而复杂的问题分割成多个规模小而易于解决的问题,最终将小问题的结果进行合并作为原始问题的结果即可..
对于一个规模为n的原始问题,当这个问题容易解决的时候可以直接求解,无需分治;但是当问题比较复杂的时候,考虑使用分治算法来转化,将原始问题分隔为k个小规模且简单的子问题.在解决子问题的过程中采用递归算法解决,让后再合并,这就是分治算法的基本策略.
由于分治算法分解得到的子问题,往往是原始问题的类型相同但是规模更小的问题.在解决这些子问题的时候不可避免的会用到递归算法,因此递归和分治往往同时出现,在许多问题中二者相辅相成.
适合使用分治算法来解决的问题一般具有一下特征:
1.原始问题可以分解为多个形式相同但是规模较小的子问题,说明原始问题具有最优子结构的特点
2.子问题之间相互独立,不包含公共子问题
3.子问题可解,当子问题规模小到一定程度时易于解决
4.可以通过合并各个子问题的解来得到原始问题的解
