分治策略

• 分治策略中，递归地求解一个问题，在每层递归中应用如下三个步骤：
  • 分解：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小
  • 解决：递归地求解出子问题，如果子问题的规模足够小，则停止递归，直接求解
  • 合并：将子问题的解组合成原问题的解

当子问题足够大，需要递归求解时，称之为 递归情况，反之足够小，不再需要递归时，称之为 基本情况

• 递归式
  • 一个等式或不等式，通过更小的输入上的函数值来描述一个函数，使用递归式可以很自然地刻画分治算法的运行时间
  • 如：用递归式描述 MERGE-SORT 过程的最坏情况运行时间 T(n)

求解可得
**

• 求解递归式

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

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

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

其中 a>=1, b>1, f(n) 是一个给定的函数。
即：生成 a 个子问题，每个子问题的规模是原问题的 1/b，分解和合并步骤共花费时间为 f(n)

• 最大子数组问题

  • 运行时间分析：FIND-MAXIMUM-SUBARRAY 同 MERGE-SORT 一样

• 矩阵乘法的 Strassen 算法

  • 核心思想：令递归树稍微不那么茂盛一点儿，即只递归进行7次而不是8次 n/2 x n/2 矩阵的乘法
  • 步骤：
    1. 将输入矩阵A、B和输出矩阵C分解为 n/2 x n/2 的子矩阵。采用下标计算方法，此步骤花费 时间
    2. 创建10个 n/2 x n/2 的矩阵S1, S2, …, S10, 每个矩阵保存步骤1中 创建的两个子矩阵的和或差。花费时间为
    3. 用步骤1中创建的子矩阵和步骤2中创建的10个矩阵，递归地计算7个矩阵积P, P, …, P。每个矩阵P都是 n/2 x n/2的
    4. 通过P矩阵的不同组合进行加减运算，计算出结果矩阵C的子矩阵C, C, C, C。 花费时间
  • 运行时间T(n)的递归式：

求解可得
**

• 代入法求解递归式

  • 猜测解的形式
  • 用数学归纳法求出解中的常数，并证明解是正确的

• 用递归树方法求解递归式

  • 递归式适合用来生成好的猜测，然后即可用代入法来验证猜测是否正确

• 用主方法求解递归式