算法学习之分治法
-
没有什么问题是分割成两半还解决不了的,如果有,就再分一次。╭(╯^╰)╮
分治法的设计思想
将一个难以直接解决的大问题,分割成一些规模较小的与原问题形式相同的子问题,用递归解决这些子问题,然后将子问题的解合并即为原问题的解。
分治法的适用范围
- 1.该问题的规模缩小后可以容易地解决。
- 2.该问题可以分解为若干个规模较小的相同问题。
- 3.该问题的子问题的解可以合并。
- 4.该问题的各个子问题相互独立。
TIP:如果一个问题具备前两条特征,但不具备第三条,可以考虑贪心算法或动态规划
TIP:如果一个问题不具备第四条特征,分治法的效率降低,用动态规划较好。分治法的基本步骤
分治法在每一层递归上都有三个步骤:
step1 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;step2 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
step3 合并:将各个子问题的解合并为原问题的解。
可使用分治法求解的经典问题
- 二分搜索
- 大整数乘法
- Strassen矩阵乘法
- 棋盘覆盖
- 归并排序
- 快速排序
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
分治法实例
1.求x的n次幂
时间复杂度为O(lgn)
个人感悟:感觉有二分法的思想。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.快速排序不稳定,归并排序稳定。
合并方法:用两个指针分别指向两个子数组第一个元素,然后总是把小的数字填入结果中并将对应指针往右移一位;如果其中一个指针到头了,则直接把另外一个指针没到头的数组的剩余元素填入结果。3.最大子数组问题
时间复杂度O(nlgn)
将数组等分,讨论最大子数组的位置:- 1.完全在左边或者右边。
- 2.跨越中点。
第一种情况直接递归找出最大子数组,第二种情况从中点开始向两边寻找最大子数组,问题的解就是两种情况里面和最大的那个子数组。
关于最大子数组问题,也可以用动态规划的思想做,区别参照归并排序与快速排序的区别。
- 当我解决Two Sum时也想到到了使用分治法,可以参考一下我的思路
- 我的Two Sum解决思路
参考链接
-
哇 我也想分享算法
-
@tangbin 一起啊一起啊 把分治动规贪心写完就差不多可以转正了23333