算法导论真的好（厚）啊，才看到分治策略

分治策略

递归式

递归式的形式

一个递归式就是一个等式或不等式，它通过更小的输入上的函数值来描述一个函数。

求解递归式的方法

• 代入法 我们猜测一个界，然后用数学归纳法证明这个界是正确的。

• 递归树法 将递归式转化为一棵树，其结点表示不同层次的递归调用产生的代价，然后采用边界和技术来求解递归式。

• 主方法 可求解形如下面公式的递归式的界：

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

  © 版权声明

  文章版权归作者所有，未经允许请勿转载。
  THE END
  后端