MIT算法导论三 分治法

分治法分为三个步骤:
Divide - 将一个问题拆分成若干个子问题(规模更小)
Conquer - 通过递归的方法分别解决第一步中的每个子问题
Combine - 将各个子问题的结果合并起来得到整个问题的结果

典型的分治法算法

  • 归并排序(Merge sort之前介绍过)
    T(n) = 2T(n/2) + n | 满足主定理Case2
    =》T(n) = Θ(nlgn)

  • 二分查找(Binary search)
    在一个已经排序的数组中找到x
    把x于数组的中间节点比较,有三种结果:
    1.x=middle,返回结果
    2.x<middle,左半边数组进行递归查找
    3.x>middle,同理右半边数组进行递归查找
    T(n) = T(n/2) + Θ(1) =》 T(n) = Θ(lgn)

  • 乘方问题(Power the number
    给定x,n>0,求解xn
    if n是偶数,xn = xn/2 * xn/2
    if n是基数,xn = x(n-1)/2 * x(n-1)/2 * x
    T(n) = T(n/2) + Θ(1) =》 T(n) = Θ(lgn)

  • 斐波那契数列
    0 1 1 2 3 5 8 13 ...

    朴素算法:Fn = Fn-1 + Fn-2
    算法效率为Ω(φn),指数级别的,递归子问题的规模没有明显减小,并且又重复计算的部分

    自底向上算法:计算 0 1 1 2 3 5... 直到Fn
    避免了重复计算,算法效率提高到了Θ(n)

    递归平方算法:

    定理

    问题的求解即成为了矩阵的乘方问题,算法效率于是提高到了Θ(lgn)

  • 矩阵乘法nxn阶矩阵
    有两个矩阵A[ij]、B[ij],求解C=A*B
    Cij=Σ(Aik * Bkj) | k <- 1 to n
    朴素算法:需要三层循环(i\j\k分别从1到n循环计算,见文末补充),算法的效率为Θ(n3)

    分治算法:将矩阵分成四个相同大小

    分解矩阵

    r=ae+gb
    s=af+bh
    t=ce+dg
    u=cf+dh
    T(n) = 8T(n/2) + Θ(n2) | 分成递归八个乘法,每个小问题是原来的1/2,加上4次矩阵加法运算
    => T(n) = Θ(n3) 效率并没有提高

    Strassen算法:
    主定理方法可知必须想办法将2中递归式中的系数8减少。Strassen提出了一种将系数减少到7(log27<3)的分治法方案
    P1=a(f-h)
    P2=(a+b)h
    P3=(c+d)e
    P4=d(g-e)
    P5=(a+d)(e+h)
    P6=(b-d)(g+h)
    P7=(a-c)(e+f)
    r=P5+P4-P2+P6
    s=P1+P2
    t=P3+P4
    u=P5+P1-P3-P7
    问题转变成递归7次乘法和18次加减法
    T(n) = 7T(n/2) + Θ(n2) =》 T(n) = Θ(nlg7) = Θ(n2.81)
    效率提高,并且因为是指数级增长,当n更大时提升效率明显
    ~现在理论上矩阵乘法的效率最好的是:Θ(n^2.376…)。但是在这众多的优化算法中,Strassen算法却是最简单的~


补充:矩阵乘法nxn阶矩阵朴素算法
for i ← 1 to n 
   do for j ← 1 to n 
       do c[i][j] ← 0 
           for k ← 1 to n 
               do c[i][j] ← c[i][j] + a[i][k]⋅ b[k][j] 
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 算法和数据结构 [TOC] 算法 函数的增长 渐近记号 用来描述算法渐近运行时间的记号,根据定义域为自然数集$N=...
    wxainn阅读 1,082评论 0 0
  • 我有个特别小的发小 我是说真的,这个姑娘和我一个发小,像到连我都觉得这肯定是她背着我生下来得闺女。 说实话,今天看...
    小魔女张张阅读 87评论 0 0
  • 办户口相关事宜 标签(空格分隔): 办户口 步骤一:从深圳到长安 从深圳到长安可以从“福田汽车站——竹子林地铁站”...
    机器猫狗阅读 507评论 0 0
  • 回住处的路上有一位地摊书法家,之前见过许多次,今天又见到了。要知道浊某为人最庸俗且好附庸风雅。见着书法一类的艺术作...
    化浊阅读 252评论 0 0
  • 更多优秀的国外作曲编曲教程请戳这里哦:作曲编曲相关讲座资料翻译整理 本文原文地址:より進んだコード進行(その4) ...
    Huisama阅读 2,438评论 0 51