Divide and Conquer - 分治法

在計算機科學中，分治法是一種很重要的演算法。分治法即『分而治之』，把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併。這個思想是很多高效演算法的基礎，如排序演算法（快速排序，合併排序）等。

分治法思想

分治法所能解決的問題一般具有以下幾個特徵：

1. 問題的規模縮小到一定的程度就可以容易地解決。
2. 問題可以分解爲若干個規模較小的相同問題，即該問題具有最優子結構性質。
3. 利用該問題分解出的子問題的解可以合併爲該問題的解。
4. 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

分治法的三個步驟是：

1. 分解（Divide）：將原問題分解爲若乾子問題，這些子問題都是原問題規模較小的實例。
2. 解決（Conquer）：遞歸地求解各子問題。如果子問題規模足夠小，則直接求解。
3. 合併（Combine）：將所有子問題的解合併爲原問題的解。

分治法的經典題目：

1. 二分搜索
2. 大整數乘法
3. Strassen矩陣乘法
4. 棋盤覆蓋
5. 歸並排序
6. 快速排序
7. 循環賽日程表
8. 河內塔