算法导论 ——分治中求解递归式的三种方法

在分治算法中，求解递归式（求解了递归式就知道了时间复杂度）主要有三种方法：代入法、递归树法、主方法。

• 代入法
  这种方式主要靠猜测，然后用数学归纳法进行证明，一般需要大量的经验才可以。

• 递归树法
  把递归式逐层展开，直接就能得到一个树形结构。比如，这次我们以T(n) = 3T(n/4) + O(n2)**为例。每个节点代表一个单一子问题的代价，子问题对应某次递归函数的调用。我们将函数中每层的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层的递归调用的递归调用的总代价。这里会涉及级数的计算，一般理解了递归树怎么画，然后利用它配合主方法即可解决大部分问题。
  

• 主方法
  对于形如T(n) = aT(n/b) + f(n)的递归式，其中a>=1和b>1是常数，a代表把每个问题分解成a个子问题，每个问题的规模是1/b，这时有下面的三个规则。递归树中叶子节点的个数为n**(log以b为底，a的对数)，这里把叶子节点的个数记为T
  1）当T < f(n)时，T(n) = O(f(n))，这里的O表示渐近符号
  2）当T = f(n)时，T(n) = O(Tf(n))
  3) 当T > f(n)时， T(n) = O(T)
  这里的三个规则是笔者自己的理解，和书中的介绍略有不同，标准请参考算法导论正版书籍。