没有什么问题是分割成两半还解决不了的,如果有,就再分一次。╭(╯^╰)╮

分治法的设计思想

将一个难以直接解决的大问题,分割成一些规模较小的与原问题形式相同的子问题,用递归解决这些子问题,然后将子问题的解合并即为原问题的解。

分治法的适用范围

  • 1.该问题的规模缩小后可以容易地解决。
  • 2.该问题可以分解为若干个规模较小的相同问题。
  • 3.该问题的子问题的解可以合并。
  • 4.该问题的各个子问题相互独立。

TIP:如果一个问题具备前两条特征,但不具备第三条,可以考虑贪心算法或动态规划
TIP:如果一个问题不具备第四条特征,分治法的效率降低,用动态规划较好。

分治法的基本步骤

分治法在每一层递归上都有三个步骤:
step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;

step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题

step3 合并:将各个子问题的解合并为原问题的解。

可使用分治法求解的经典问题

  • 二分搜索
  • 大整数乘法
  • Strassen矩阵乘法
  • 棋盘覆盖
  • 归并排序
  • 快速排序
  • 线性时间选择
  • 最接近点对问题
  • 循环赛日程表
  • 汉诺塔

### 分治法实例

1.求x的n次幂

时间复杂度为O(lgn)
个人感悟:感觉有二分法的思想。

1
2
3
4
5
6
7
8
sum(x,n)
if(x==1)
result=x;
if(x%2==0)
result=sum(x,n/2)*sum(x,n/2);
else
result=sum(x,(n+1)/2)*sum(x,(n-1)/2);
return result;

2.归并排序

个人感悟:归并排序与快速排序的区别在于
1.使用二分法时,快速排序两边个数不一定相等,归并排序一定相等。
2.快速排序不需要额外数组。
3.快速排序不稳定,归并排序稳定。

12.20.1.png
12.20.1.png

合并方法:用两个指针分别指向两个子数组第一个元素,然后总是把小的数字填入结果中并将对应指针往右移一位;如果其中一个指针到头了,则直接把另外一个指针没到头的数组的剩余元素填入结果。

3.最大子数组问题

时间复杂度O(nlgn)
将数组等分,讨论最大子数组的位置:

  • 1.完全在左边或者右边。
  • 2.跨越中点。
    第一种情况直接递归找出最大子数组,第二种情况从中点开始向两边寻找最大子数组,问题的解就是两种情况里面和最大的那个子数组。
    关于最大子数组问题,也可以用动态规划的思想做,区别参照归并排序与快速排序的区别。

最大子数组问题

参考链接

TIP:参考链接中还有许多其他链接也是非常好的学习素材哦。
理论部分
示例部分1
示例部分2