算法设计与分析 第5章 减治策略和变治策略_48292.pptx

减治策略及变治策略;元素的求解过程与n个元素求解过程的联系，使问题的求解直接通过表达式来求解，从而简化问题的求解难度。 一般采用自顶向下的分析方法，但求解时往往采用自底向上的求解过程。这也是递归的方法。 （2）减去一个常量因子 在规模中减去一个常量因子，使求解的规模成倍的缩小，从而提高问题求解的效率。 ; （3）减去的规模可变。 根据求解过程的变化来确定每次规模减少的程度。 具体实例： 1、直接插入排序 2、拓扑排序 3、全排列问题 4、子集问题;变治策略;实例; 2、进制之间的转换问题。 此外，还有一些具体问题的求解方法均可采用变治策略。