算法之分治法

程序=算法+数据结构

著名计算机科学家niklaus wirth提出了著名论断程序=数据结构+算法，这里我们就来谈谈分治法。

分治法与贪心法的区别

首先我们需要区分一下贪心法与分治法，贪心法是局部最优解，旨在用局部最优累加成一个最终结果；而分治法，则是将一个大问题分解成k个小问题，这每个小问题互相独立且与大问题相似，我们只需要递归的解决掉这小问题就可以实现解决大问题的目标。
日常生活中，大部分人都会采用贪心法来处理日常事务，比如当你在找工作的时候，你可能大概率选择一个薪水比较高的工作，而不会去考虑一个长远的得失问题；面对同样一个找工作问题，如果我们采用分治法，又会是怎么样一个情景呢？
我们可以将找工作这个事看作一个大问题，我们首先要对它进行分解，分解的问题规模要足够小，以便可以直接得出答案。我们可以这样，首先将找工作分为薪水、强度、压力、是否可持续等几个维度，然后将我们可以匹配到的工作分别去对应这几个维度，最后就可以得出一个结果。这里我们就用到了分治法的思想。

分治法的特征与所能解决的问题

一般而言分治法所能解决的问题都包含如下几个特征：
1.问题具有足够的规模，即该问题不能直接给出解；
2.问题可以拆分成相互独立且与原问题相近似的小问题；
3.各个小问题的解集合起来，就可以得出原问题的解；
大多数情况下，我们是需要将很多个算法的思想结合起来做事，也有很多情况，我们需要灵活的运用算法。

分治法解决问题的数学模型

未完待续，博主持续更新中~