第2章 递归及分治策略.pdf

算法总体思想 第2章 递归与分治策略 将一个难以直接解决的规模较大的问题分解为 若干个规模较小的子问题，并各个击破，分而 治之。 n 2.1 递归概念 2.2 分治算法的基本思想 n/4 n/4 n/4 n/4 2.3 典型分治算法举例 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 … … … … … … … … … … … … … … … … 1 2 将求出的较小规模的问题解合并成一个较大规 2.1 递归概念 模的问题解，并 自底向上地求出原问题的解。 分治算法的特征：将较大规模的问题分解为若 干个较小规模的子问题，每个子问题的求解过 程与原问题一样，并利用自底向上的求解策略 (1) n=1 最底层问题 得到最终的解。 T(n) = aT(n/b) + f(n) n1 分治算法 递归技术 分治与递归像一对孪生兄弟 a 为分解的子问题数量； n/b 为每个子问题的数据规模； 直接或间接地调用自身的算法称为递归算法。 f(n) 为合并子问题解所消耗的时间。 在定义函数时调用到函数自身称为递归函数。 3 4 递归应用举例1: Fibonacci数列 递归应用举例2: Ackerman函