高级算法设计第2章递归与分治.pdf

第2章 递归与分治策略 二分搜索技术；=>最大最小值 合并排序 大整数乘法 Strassen矩阵乘法 快速排序 线性时间选择； 棋盘覆盖； 循环赛日程表。 最接近点对问题； 最大子段和 算法总体思想 ◼ 对这k个子问题分别求解。如果子问题的规模 仍然不够小，则再划分为k个子问题，如此递 ◼ 归的进行下去，直到问题规模足够小，很容 易求出其解为止。 问题 = T(n) T(n/2) T(n/2) T(n/2) T(n/2) 算法总体思想 ◼ ◼ 将求出的小规模的问题的解合并为一个 更大规模的问题的解，自底向上逐步求 出原来问题的解。 问题 T(n ） T(n/2) T(n/2) T(n/2) T(n/2) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4 算法总体思想 ◼ 将求出的小规模的问题的解合并为一个 更大规模的问题的解，自底向上逐步求 出原来问题的解。 问题 T(n) T(n/2) T(n/2) T(n/2) T(n/2) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4 算法总体思想 ◼ 将求出的小规模的问题的解合并为一个 更大规模的问题的解，自底向上逐步求 出原来问题的解。 分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。 2.1 递归的概念 ◼ 直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 ◼ 由分治法产生的子问题往往是原问题的较小模 式，这就为使用递归技术提供了方便。在这种 情况下，反复应用分治 ，可以使子问题与 原问题类型一致而其规模却不断缩小，最终使 子问题缩小到很容易直接求出其解。这自然导 致递归过程的产生。 ◼ 分治与递归像一对孪生兄弟，经常同时应用在 算法设计之中，并由此产生许多高效算法。 下面来看几个实例。 2.1 递归的概念 例1 阶乘函数 阶乘函数可递归地定义为： 边界条件  1 n = 0 n!=  n(n −1)! n  0 递归方程 边界条件与递归方程是递归函数的二个要素，递归函 数只有具备了这两个要素，才能在有限次计算后得出 结果。 2.1 递归的概念 例2 Fibonacci数列 无穷数列1，1，2，3，5，8 ，13，21，34，55，……，称为 Fibonacci数列。它可以递归地定义为： 边界条件