算法：分治算法
分治算法的基本步骤
分治算法的基本步骤：
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技术交流群一起交流学习哦。
- 发表于 2021-11-27 09:54
- 阅读 ( 1303 )
- 分类：Java开发
