假如一家公司要举办“金嗓子”歌唱比赛，但是公司一共有4000多人，这么多人参加比赛，每个人都要唱几分钟，估计评委要累坏了。但是要如何解决呢？
这个问题如果使用分治算法可以缩短很多时间的，那么什么是分治算法呢？分治算法，就是把一个复杂的问题分割成多个的相同或相似的子问题，再把子问题分割更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
一般来说，分治算法有三个条件：
1.原问题可以分割成若干个规模较小的子问题
2.子问题互相独立，并且可以求解
3.子问题的解可以合并
比如说，举办歌唱比赛，如果人数太多，就可以把选手按部门进行分组，每一组自己去比赛，选出两个人晋级，晋级选手再去进行复赛，这样就可以有效的减少比赛的时间了。
简单的说，分治算法的特点就是：分解问题，各个击破，分而治之。
例如：在猜数字游戏中，让嘉宾猜一个10以内的整数。可以使用分治算法，每一次都将真个数字分割为两个部分，所以第一次猜5，如果5猜小了，那么就把6-10这部分数字再分割成两部分。第二次猜8.依次类推，这样可以在较短的时间内找到正确的结果。
分治算法其实是一个很古老的算法，在《孙子兵法》中就说过：凡治众如治寡，分数是也。就是说管理多个人和管理几个人是一样的，只要按人数将所有人分割成不同的部分就可以了。
在军事上，指挥大规模的军队都是用这种办法，例如二战期间，斯大林格勒战役中，苏军总计动用了250万人进行反击，这么多军队不可能依靠一个人来指挥，因此，将所有军队分为三个方面军，方面军之下还有集团军、师旅团营等等，这也是分治的方法。
分治算法与贪心算法都是将一个大问题分解成不同的小问题，但是区别在于:
1.贪心算法要求小问题求出最优解，分治算法不一定。
2.贪心算法要求小问题之间具有依赖关系，求完一个问题再求第二个；分治算法要求小问题之间不能有关联，这些小问题是可以同时计算的。也就是说贪心算法类似于串联，分治算法类似于并联。
3.分治算法在小问题求解之后要将所有结果合并，但贪心算法不一定，有可能最后一个小问题的结果就是整个问题的解。
分治算法有很多时候是和递归相关的。在问题分解的过程中，分解不一定一步到位，有可能小问题再分解成小小问题。那么如果这些问题具有相同的解法，就可以使用递归的方法执行相同的函数，区别在于调用函数的时候问题的规模和范围不同。
获取更多免费的算法干货、课程，微信上搜索“恒企行家网校”公众号~
同时，在“恒企行家网校”公众号后台回复“加算法老师微信”，有任何算法的问题都可以直接撩我们的老师哦~
网友评论