算法基础07——设计技巧之分治算法

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。

分:递归解决较小的问题(基本情况除外)
治:从子问题的解构建原问题的解

当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,我们往往先把它分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。这就是分治策略的基本思想。

利用分治策略求解时,所需时间取决于分解后子问题的个数、子问题的规模大小等因素,而二分法,由于其划分的简单和均匀的特点,是经常采用的一种有效的方法,例如二分法检索。

一般步骤:

  1. 分解,将要解决的问题划分成若干规模较小的同类问题;
  2. 求解,当子问题划分得足够小时,用较简单的方法解决;
  3. 合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。

例子:
归并排序,最近点问题,选择问题等等

更新时间:2020-02-17 14:10:26

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/算法基础07设计技巧之分治算法
最后更新:2020-02-17 14:10:26

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×