分治策略

在计算机科学中, 分治法是基于多项分支递归的一种很重要的算法范式. 字面上的解释是"分而治之", 就是把一个复杂的问题分成两个或更多的相同或相似的子问题, 知道最后子问题可以简单的直接求解, 原问题的解就是子问题的解的合并.

分治法的步骤

  1. 分解: 将问题划分为一些子问题, 子问题的形式与原问题相同, 只是规模更小.
  2. 解决: 递归地求解出子问题.
  3. 合并: 将子问题的解合并.

求解递归式的方法

  1. 代入法
  2. 递归树法
  3. 主方法

在这里我们不对前两种方法进行说明, 仅仅讨论一下主方法的使用, 以及适用的情况.

主方法

主方法(Master Method)可以求解一下形式的递归式的边界.

T(n) = aT(n/b) + f(n)  

其中 a >= 1 b > 1 f(n) 是一个给定的函数. 这个递归式刻画了一个如下的分治算法:

生成 a 个子问题, 每个子问题的规模是原问题规模的 1/b , 分解和合并步骤总共消耗 f(n) 的时间.

使用

  1. 求出 c = log(b,a)
  2. 比较 n^cf(n) 的大小
    • 如果前者多项式的小于后者, 那么该递归式的边界为 Θ(f(n)).
    • 如果前者多项式的大于后者, 那么该递归式的边界为 Θ(n^log(b,a)).
    • 如果两者多项式意义上的相等, 那么只需要乘上一个对数因子 lgn, ex, T(n) = T(n/2) + 1 => Θ(lgn)

总结

恰当运用主方法可以解决大多数的递归式边界问题, 但是当两项非多项式意义上的小于或者大于, 那么就不能使用主方法求解, ex, T(n)=2T(n/2)+n/lgn

Draveness

继续阅读此作者的更多文章

comments powered by Disqus