算法学习-递归和分治

递归

直接或者间接不断反复调用自身来达到解决问题的方法。要求原始问题可以分解为相同问题的子问题。

先决条件

  • 递归边界
  • 自身调用

特点
思路简单清晰,如果分析出将很快得到结果;递归将多次调用,使用到堆栈,算法效率低,费时费内存。

常用场景

  • 阶乘
  • 斐波纳契数列
  • 汉诺塔问题
  • 整数划分
  • 枚举排列及二叉树
  • 图的搜索相关问题。

分治

把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

基本思想
将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

策略
对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。

使用场景

  • 问题的规模缩小到一定的程度就可以容易地解决
  • 问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
  • 问题分解出的子问题的解可以合并为该问题的解
  • 问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

基本操作步骤
分治法在每一层递归上都有三个步骤:

  • 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
  • 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题
  • 合并:将各个子问题的解合并为原问题的解

常用场景

  • 二分搜索
  • 大整数乘法
  • Strassen矩阵乘法
  • 棋盘覆盖
  • 合并排序
  • 快速排序
  • 线性时间选择
  • 最接近点对问题
  • 循环赛日程表
  • 汉诺塔