Skip to content

Files

Latest commit

 

History

History
40 lines (25 loc) · 2.68 KB

divideandconquer.md

File metadata and controls

40 lines (25 loc) · 2.68 KB

分治算法

分治算法的核心思想就是分而治之。将问题尺寸为N的问题分解成两个独立的部分,然后递归性去解决这些子问题,最后将子问题的解合并成结果,就得到了原问题的解.

分治算法能解决的问题,一般要满足下面几个条件:

  1. 原问题和分解的小问题具有相同的求解模式.
  2. 分解的子问题可以独立求解,子问题之间没有任何关联,这是分治和动态规划最明显的区别
  3. 具有分解的终止条件,也就是说当问题足够小时,可以直接求解.
  4. 可以将子问题的求解合并成原问题,而这个合并操作的复杂度不能太高,否则就起不到减少算法总体的复杂度效果了。

分治算法的范例:

  • 二分搜索
  • 归并排序

它们都是将规模为N的大问题一分为二,在对子问题求解的过程. 递归表明了每个算法的分治计算本质.

快速排序和二叉树搜索代表了分治算法的变异版本,它将问题剖成为k-1N - k的子问题,其中的k是由输入决定的某个值. 对于随机输入,这些算法将问题分解成大体上一半大小的子问题. 当我们讨论这些算法时,就会分析这种差异的效果.