算法之分治策略

简介

在计算机科学中,分治策略是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

这个技巧是很多高效算法的基础,如排序算法(快速排序、归并排序)、傅立叶变换(快速傅立叶变换)。

分治算法通常以数学归纳法来验证,在计算机中以递归来解决。而它的计算成本则多数以解递回关系式来判定。

递归

分治和递归是紧密相连的。让我们先来看看递归的简单概念

递归情况

当子问题足够大,需要递归求解的时候,我们称之为递归情况

基本情况

当子问题变得足够小,不需要再递归即可求解的时候,我们称之为基本情况

分治策略步骤

在分支策略中,我们递归地解决一个问题,在每层递归中应用如下三个步骤:

  1. 分解:将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。
  2. 解决:递归地求解出子问题。如果子问题的规模够小,则停止递归,直接求解(这就是递归至底的情况)。
  3. 合并:将子问题的解组合成原问题的解。

复杂性分析

可详见《算法导论》第4章

可使用分治法求解的一些经典问题

  1. 二分搜索
  2. 大整数乘法
  3. Strassen矩阵乘法
  4. 棋盘覆盖
  5. 合并排序
  6. 快速排序
  7. 线性时间选择
  8. 最接近点对问题
  9. 循环赛日程表
  10. 汉诺塔
文章目录
  1. 简介
  2. 递归
    1. 递归情况
    2. 基本情况
  3. 分治策略步骤
  4. 复杂性分析
  5. 可使用分治法求解的一些经典问题
|