簡介

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 發表在 痞客邦 PIXNET 留言(0) 人氣()