分治算法

分治算法

前言

参考文章

概念

分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）等等。

适用条件

采用分治法解决的问题一般具有的特征如下：

问题的规模缩小到一定的规模就可以较容易地解决。
问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质。
合并「原问题分解出的子问题的解」可以得到原问题的解。
原问题所分解出的各个子问题之间是独立的，即：子问题之间不存在公共的子问题。(非必需)

条件 1 随着问题规模的减少，问题自然会容易解决。

条件 2，3 是分治的前提。即 Divide-and-Conquer 的必要条件。

条件 4 对于存在公共子问题的问题，使用分治算法会存在重复计算的问题，使用动态规划较为合适。

设计步骤

划分步：把输入的问题划分为 k 个子问题，并尽量使这 k 个子问题的规模大致相同。
治理步：当问题的规模大于某个预定的阈值 n0 时，治理步由 k 个递归调用组成。
组合步：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。
分治法的关键是算法的组合步。究竟应该怎样合并，没有统一的模式，因此需要对具体问题进行具体分析，以得出比较好的合并算法。

得结合实际问题来理解。

分治法通俗解释

有这样一个非常经典的问题 —— 有 100 枚硬币，其中 1 枚重量与众不同，是假币，略轻一些。如果用天平秤，请问至少称几次一定能找到这枚假币？假如我们用传统的逐枚比较法的话，显然至少需要比较 50 次。

而假如我们采用分治法的话，称量步骤如下：

将 100 枚硬币分成 3 份，33/33/34。
称量 1、2 份，若天平平衡，则假币必在另外 34 枚中。若不平衡，假币在轻的那 33 枚里。
…后面再按照相同的逻辑不断细分。会发现这种方法只需要 5 次就能解决这个问题。