算法学习之分治法



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

    分治法的设计思想

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

    分治法的适用范围

    • 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.快速排序不稳定,归并排序稳定。
    12.20.1.png
    合并方法:用两个指针分别指向两个子数组第一个元素,然后总是把小的数字填入结果中并将对应指针往右移一位;如果其中一个指针到头了,则直接把另外一个指针没到头的数组的剩余元素填入结果。

    3.最大子数组问题

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

    • 1.完全在左边或者右边。
    • 2.跨越中点。
      第一种情况直接递归找出最大子数组,第二种情况从中点开始向两边寻找最大子数组,问题的解就是两种情况里面和最大的那个子数组。

    关于最大子数组问题,也可以用动态规划的思想做,区别参照归并排序与快速排序的区别。

    最大子数组问题

    参考链接

    理论部分
    示例部分1
    示例部分2



  • 哇 我也想分享算法



  • @tangbin 一起啊一起啊 把分治动规贪心写完就差不多可以转正了23333


 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开,我们正在尝试重连,请耐心等待