目录

分治算法

基本介绍

分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法 12.快速排序13.归并排序,傅立叶变换(快速傅立叶变换)。

分治算法可以求解的一些经典问题

算法步骤

分治法在每一层递归上都有三个步骤:

  1. 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
  2. 解决:若子问题规模较小而容易被解决则直接解,递归地解各个子问题
  3. 合并:将各个子问题的解合并为原问题的解。

比如对汉诺塔:分就是将n个盘子分成上面盘子(n-1)个盘子和下面1个盘子,最终分到上面只有一个盘子编号1(阈值),直接移动即可。这样递归处理一轮后圆盘n移动到了目标塔,此时需要把之前放在中转塔上的(圆盘n-1~圆盘1)移动到目标塔。

对归并排序:分是指递归将一个序列二分成两个子序列,最终左边节点数+右边节点数<=2(阈值) ,解就是就是对两个有序数组进行合并排序,合就是递归的过程。 对快排:子算法

对快排:将一个序列递归分成两个序列并左右两边分别有序,无论挖坑还是选择,目的都是找到一个值放在当前序列的某处使得该值左右两个序列有序罢了。

分治(Divide-and-Conquer)算法设计模式如下: https://gitee.com/lienhui68/picStore/raw/master/null/20200701092347.png

最佳实践-汉诺塔

汉诺塔