本文首发自「慕课网」，想理解更多 IT 干货内容，程序员圈内热闻，欢送关注！
作者 | 慕课网精英讲师 JdreamZhang
在计算机科学与技术畛域中，分治法（Divide and Conquer) 是一种常见的算法思维。
分治法的了解其实很简略，间接依照字面的意思了解就能够：“分而治之”。分（divide）是将一个大的问题分解成一些小的问题别离求解，治（conquer）则是将合成的问题答案合并在一起，整个过程则是分而治之。这个算法技巧是很多算法的根底，咱们之前学过的疾速排序，其中就有分治思维的利用。
简略来说，分治法就是将一个简单的大问题分解成两个或者更多雷同或者类似的子问题，再把子问题持续拆分成更小的子问题，直到子问题能够间接求解，而后原问题的解就是子问题的解的合并。
- 分治法的根本思维及实现策略
次要思维：分治法将一个规模较大的问题，拆分成一些规模较小的雷同问题，小问题各个求解，再合并成大问题的解。这个是分值算法的次要思维。
实现策略：分治算法对于一个规模较大 的问题（假如其规模为 n），如果当规模 n 的问题很容易解决则间接解决；否则就将这个规模为 n 的大问题拆分为几个规模为 k（规模 k 小于规模 n）的子问题，这些子问题与原问题的模式雷同，则能够递归地求解这些子问题，而后将各个子问题的解合并失去原先的大问题的解。
分治法是否可行次要就在于这个大问题是否能够拆分为雷同模式的小问题，而后这些小问题可解并将小问题的解合并成为原问题的解。因而，分治法所可能解决的问题个别都会具备如下几个特色：
待求解问题能够拆分成雷同模式的规模较小的问题；
待求解问题在规模放大到肯定水平之后就能够很容易求解；
利用待求解问题拆分出的子问题的解能够合并为待求解问题的解；
待求解问题拆分进去的子问题是互相独立的，子问题之间不会蕴含雷同的子问题。
- 分治法的根本步骤
在明确分治法的定义及其次要思维和实现策略之后，咱们须要把握实现分治法的次要步骤：
步骤 1：
将待求解问题拆分成若干个规模较小、互相独立的子问题，子问题的模式与待求解问题雷同；
步骤 2：
若干个子问题如果很容易求解则间接求解，如果不容易求解则递归的解各个子问题；
步骤 3：
将各个子问题别离求解的后果合并成待求解问题的解。
基于以上的三个步骤，分治算法个别能够总结成上面的伪代码：
divideAndConquer(big_problem){
if (canSolve(big_problem)){// 问题能够间接求解则间接求解返回
solve(big_problem); // 求解
return; }else {
small_problem_A = divide(big_problem); // 不能间接求解的问题拆分
small_problem_B = divide(big_problem); // 不能间接求解的问题拆分
divideAndConquer(small_problem_A); // 递归求解子问题
divideAndConquer(small_problem_B); // 递归求解子问题
return merge(); // 合并子问题的解}
}
代码块 123456789101112
- 分治法的利用场景
在日常的生存学习中，分治算法个别能够用来解决很多理论问题。上面，咱们来看两个分治算法求解问题的实例。
实例 1: 二分搜寻
二分搜寻是一种很常见的搜寻策略，他的核心思想也是利用到分治算法。二分搜寻是在一个有序的数组中，通过平均二分，每次折半查找，就是利用到分治法中将大问题缩减到小问题，这个小问题的最初后果就是刚好找到须要查找搜寻的元素，这样小问题得出解，这个解也是最开始的待搜寻的元素。
实例 2: 全排列问题
现实生活中，咱们常常会遇见这样的场景，比方有 3 个小朋友排成一列，问你一共有多少种能够排列的状况，这个问题相似于数学中的全排列问题，这个时候利用分治算法也能够很好地进行求解。
先顺次从三个小朋友中抉择一位排在队列最后面，剩下的两个小朋友能够进行全排列，也能够持续拆分，二者抉择其一进行即可，这个时候其实很分明，他们只有两种排列状况了，而后跟后面的小朋友排列组合在一起。
比方咱们用 A，B，C 代表三个小朋友，他们的排列状况演示如下：
// 初始须要排列的元素
[A,B,C]
// 顺次从三个小朋友中抉择一位排在队列最后面，剩下的两个小朋友全排列
A[B,C]; B[A,C]; C[A,B]
// 剩下的两个小朋友排列状况只有两种，与之前的合并在一起
ABC,ACB,BAC,BCA,CAB,CBA
代码块 12345678
在事实工作和学习中会常常遇见，这是一种解决问题的思路与办法，将待求解的大问题拆分成小问题，而后解决小问题，再将小问题的解合并得出整个问题的解。
- 小结
本篇文章次要介绍了分治算法的定义及根本思维，须要大家明确分治算法的根底思维和实现逻辑是什么样的，如何本人去设计一个分治算法，什么样的问题适宜用分治算法求解，以及在咱们日常中常见的分治算法求解的问题。
欢送关注「慕课网」，发现更多 IT 圈优质内容，分享干货常识，帮忙你成为更好的程序员！