c语言算法设计策略–2 分治法


分治法的思想和特征

分治法是一种重要的算法。分治法的思想可以描述为:对于一个规模为n的问题,若该问题可以容易地解决,则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立与原问题相同,递归地解决这些子问题,然后将各问题的解合并到原问题的解中。


分治法所能解决的问题一般具有以下特征:
1 该问题的规模缩小到一定程序就很容易得到解决
2 该问题可以分解为若干个规模较小的相同问题
3 分解出的问题,最后可以通过合并解得到原问题的解
4 该问题分解出的各个子问题是相互独立,子问题之间不包含公共的子问题