算法：分治算法

分治算法的基本步骤

分治算法的基本步骤：

1.分解

将问题划分成一些子问题，子问题的形式与原问题一样，只是规模更小。

2.解决

递归的求解出子问题。如果子问题的规模足够小，停止递归，直接求解。

3.合并

将子问题的解组合成原问题的解。

算法的复杂度是O(nlogn)

举例：

归并排序

对一个乱序的数组[14,12,15,13,11,16]进行排序。

1.分解

将数组分解成两个数组A[14,12,15]和B[13,11,16]。这两个数组被之前的数组规模更小，是原数组规模的一半，另外子问题的形式也一样，对这两个数组进行排序。在拆分成子问题时，一般会采用折半的方式，这样两边的规模相似，总体的复杂度是最小的。

2.解决

可以继续拆分两个数组，将两个数组再分别拆分成两个数组，如此继续下去。当拆分到每个小子数组只剩一个元素的时候，就停止递归，直接求解。对于单个元素的数组本身就是有序的。

3.合并

需要将两个排序好的数组进行合并。可以采用这种方式：构建一个空的数组C，比较A数组的第一个元素和B数组的第一个元素，将较小着放入数组C。当数组A和B中的一个数组先被遍历完时，将另一个数组的剩余元素全部顺序的放入C。数组C即为排序好的数组。

（归并排序原理示意图）

分治算法是比较常用的算法，在处理大规模问题的时候，可以尝试将其分解成更小规模的问题进行处理，之后再将结果合并。

关注下方微信公众号：java圈子，获取价值999元全套java入门到进阶的学习资料以及教程，还有java技术交流群一起交流学习哦。

0 条评论