什么是分治
分而治之是一种很古老但很实用的策略，或者说战略，本意是将 一个较大的力量打碎分成小的力量，这样 每个小的力量都不足以对抗大的力量。在现实应用中，分而治之往往是将大片区域分成小块区域治理。战国时期，秦国破坏合纵连横即是一种分而治之的手段。
我们经常听到一句话： “山高皇帝远”，意思是山高路远，皇帝管不了。实际上无论山多 高， 皇帝有多远，都在朝庭的统治之下。皇帝一个人当然不可能管那么多的事情，那么怎么统治天下呢？分而治之。我们现在的制度也采用了分而治之的办法，国家分省、市、县、镇、村，层层管理，无论哪个偏远角落，都不是无组织的。
“凡治众如治寡， 分数是也。” 一一《孙子兵法》
“分数” 的 “ 分 ” 是指分各层次的部分，＂数” 是每部分的人数编制，意为通过把部队分为各级组织， 将帅就只需通过管理少数几个人来实现管理全军众多组织。这样，管理和指挥人数众多的大军，也如同管理和指挥人数少的部队一样容易。在我们生活当中也有很多这样的例子，例如电视节目歌唱比赛，如果全国各地的歌手都来报名参赛，那估计要累坏评委了，而且一个一个比赛需要很长的时间，怎么办呢？全国分赛区海选，每个赛区的前几名再参加二次海选，最后选择比较优秀的选手参加电视节目比赛。这样既可以把最优秀的歌手呈现给观众，又节省了很多时间，因为全国各地分赛区的海选比赛是同步进行的，有点 “ 并行” 的意思。
在算法设计中，我们也引入分而治之的策略，称为分治算法，其本质就是将 一个大规模的问题分解为若干个规模较小的相同子问题，分而治之。
什么样的问题才能使用分治法解决呢？简单来 说，需要满足以下3个条件。
（1）原问题可分解为若干个规模较小的相同子问题。
（2）子问题相互独立。
（3）子问题的解可以合并为原问题的解。
分治算法秘籍
分治法解题的一般步骤如下：
（1）分解：将要解决的问题分解为若干个规模较小、 相互独立、 与原问题形式相同的子 问题。
（2）治理： 求解各个子问题。 由于各个子问题与原问题形式相同， 只是规模较小而己， 而当子问题划分得足够小时， 就可以用较简单的方法解决。
（3）合并：按原问题的要求，将子问题的解逐层合并构成原问题的解。
一言以蔽之， 分治法就是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
在分治算法中，各个子问题形式相同，解决的方法也一样，因此我们可以使用递归算法快速解决，递归是彰显分治法优势的利器。（点我了解递归算法）
二分查找也是典型的分治问题（点我查看二分查找算法）
快速排序算法也用到了分治（点我查看快速排序算法）
0 评论 最近
没有评论！