簡介

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

優點

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

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

步驟

以下摘錄自Wiki

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

不適合的情況

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

lect3-9      

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

相關範例

河內塔(Tower of Hanoii)

費波那西數列(Fibonacci)

合併排序(Merge Sort)

快速排序(Quick Sort)

二元搜索法(Binary Search)

大整數(Biginteger)

施特拉森(Strassen)演算法(矩陣相乘)

最大子序列(Maximum Subarray)

...

持續更新

文章標籤
創作者介紹
創作者 emn178 的頭像
emn178

小殘的程式光廊

emn178 發表在 痞客邦 留言(0) 人氣()