演算法 - 分治法 (Divide and conquer)

簡介

Divide and conquer 中文翻作分治法，概念如字面上的意義，將問題先切分成小問題後再解決，再將結果合併求出原始問題的答案。

優點

Divide and conquer 有許多優點，舉出常見的幾點如下：

• 將困難的問題簡化為容易實作的方式，例如河內塔 (Tower of Hanoii) 問題。
• 提升程式效率，例如合併排序 (Merge Sort) 讓排序速度提升。
• 能夠平行處理，例如 MapReduce 也是 Divide and conquer 的一種。

步驟

以下摘錄自 Wiki

• 分解：將原問題分解為若干個規模較小，相對獨立，與原問題形式相同的子問題。
• 解決：若子問題規模較小且易於解決時，則直接解。否則，遞歸地解決各子問題。
• 合併：將各子問題的解合併為原問題的解。

不適合的情況

Divide and conquer 是利用遞迴的方式來實作，所以當不適合使用遞迴的時候也就不適合使用 Divide and conquer，例如費波那西數列 (fibonacci)：

雖然費波那西數列使用 Divide and conquer 來思考很容易實作，但可以從圖中看到，單純使用遞迴會重覆計算黃色的部分，造成效能下降。

相關範例

• 河內塔 (Tower of Hanoii)
• 費波那西數列 (Fibonacci)
• 合併排序 (Merge Sort)
• 快速排序 (Quick Sort)
• 二元搜索法 (Binary Search)
• 大整數 (Biginteger)
• 施特拉森 (Strassen) 演算法 (矩陣相乘)
• 最大子序列 (Maximum Subarray)