image.png
当一个问题的规模很大时，直接求解往往比较困难。对于这类问题，很大一部分是可以采取分而治之的思想来处理的。
分治法是把问题划分成多个子问题来进行处理。这些子问题，在结构上跟原来的问题一样，但是规模比原来的问题要小。如果得到的子问题还是比较大，那么可以接着细分，一直细分到可以接受的程度为止。这样就可以用迭代的方法，分别求解这些子问题，最后再将子问题的解组合起来，就可以得到原问题的解。
分治法的设计原理
对于一个规模为n的问题P(n)，可以将它分解成k个规模较小的子问题，这些子问题互相独立，且结构跟原问题的结构相同。在解这些问题的时候，又可以对每一个子问题进行进一步的分解，直到某一个阈值n0时为止。递归地解这些子问题，再把各个子问题的解结合起来，就得到原问题的解。这就是分而治之的思想。
分治法的设计步骤：
image
其中n0是一个阈值，当问题规模小于等于n0时，就不需要再对问题进行分解，而直接调用adhoc求解。adhoc是用来直接求解规模最小问题p的子算法。merge用来把所有子问题的解合并成原问题的真正解。
从上面的图中可以看出，分支思想的实现有三个步骤：
（1）划分步：把输入的问题划分成k个子问题。一般使这k个问题的规模大致相同。
（2）治理步：当问题的规模大于预定义的n0时，治理步由k个递归调用组成。
（3）组合步：组合步主要用来将各子问题的解合并成原问题的解。这一步对分治法的实际性能很重要。
水平分治思想
顾名思义需要解决的问题是水平方向的大问题，例如多线程处理业务问题。水平分治思想主要针对，如何快速获取到问题的答案。从而将问题拆分为水平方向上的小问题来处理。这样的问题复杂度比较低只需要注意的是合理分配资源即可。
树形分治思想
当遇到一个复杂度比较高存在多个维度彼此关联的大问题时，这里就需要采用树形分治思想。
（1）需要完整的分析问题的每一个维度，并绘制出树形的关系分布图。
（2）然后根据树形结点的分布进行拆分归纳，将用的同样资源和同样逻辑的小问题抽取出来作为处理单元使用。
（3）合并结果将各各小问题的解汇总分析得出大问题的结果。
例如现在有一堆大小不一颜色不同的小球需要分拣。这里的解决思路有两种，一种是先按照颜色区分然后在按照大小区分。另一种是先按照大小区分然后在按照颜色区分。至于选择哪种需要根据资源和时间消化来选择最优解。分析得出我们可就将工作分为，区分颜色分类归纳和区分大小分类归纳这个两种工作我们可以选择擅长的人做擅长的事。而不是每个人完成所有筛选工作。
在编程中我们也用的这样的思想就是将小问题抽取出来作为公共的方法使用。从而减少代码量、内存的占用。分治思想深入后就演变成了、工具包、框架、架构最后到平台。
网友评论