Divide and Conquer - 分治法
在計算機科學中,分治法是一種很重要的演算法。分治法即『分而治之』,把一個複雜的問題分成兩個或更多的相同或相似的子問題,再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併。這個思想是很多高效演算法的基礎,如排序演算法(快速排序,合併排序)等。
分治法思想
分治法所能解決的問題一般具有以下幾個特徵:
- 問題的規模縮小到一定的程度就可以容易地解決。
- 問題可以分解爲若干個規模較小的相同問題,即該問題具有最優子結構性質。
- 利用該問題分解出的子問題的解可以合併爲該問題的解。
- 該問題所分解出的各個子問題是相互獨立的,即子問題之間不包含公共的子問題。
分治法的三個步驟是:
- 分解(Divide):將原問題分解爲若乾子問題,這些子問題都是原問題規模較小的實例。
- 解決(Conquer):遞歸地求解各子問題。如果子問題規模足夠小,則直接求解。
- 合併(Combine):將所有子問題的解合併爲原問題的解。
分治法的經典題目:
- 二分搜索
- 大整數乘法
- Strassen矩陣乘法
- 棋盤覆蓋
- 歸並排序
- 快速排序
- 循環賽日程表
- 河內塔