算法设计与分析基础第2版清华出版社ch4分治法 02讲义教材.ppt

第4章 分治法;分治法是按照以下方案工作的 1. 将问题的实例划分为同一个问题的几个较小的实例最好拥有同样的规模 2.对这些较小实例的求解一般使用递归方法但在问题规模足够小的时候有时也会使用一些其他方法 3.如果必要的话合并这些较小问题的解以得到原始问题的解;子问题2的解 ; 主定理 如果在递推式中f(n(n)其中d>=0,那么 n 当a b时