算法:分治算法

分治算法的基本步骤:

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即为排序好的数组。

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

未经允许不得转载:转载请注明出处-代码猫代码猫 » 算法:分治算法
分享到:
赞(0)

评论抢沙发

评论前必须登录!

日主题已更新到 V3.2版本

点我日她