分治法(Divide and conquer)

文藝復興
學士級達人
發表於 2021年3月22日 12:48
點閱數 243

分治法是建基於多項分支遞迴的一種很重要的演算法範式。字面上的意思是指「分而治之」,就是把一個複雜的問題分成兩個或更多的相同或相似的子問題,直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併。分治法將大小為n的問題分成兩個獨立的子問題來解决,每個子問題的大小大約是原來問題的一半。通常的解法是採用遞迴(recursive)重複處理,並以能夠輕鬆解決的基本情況來結束重複的運作。當針對較小的兩個子問題提供兩個解法時,其中必定有某個解析(resolution)算可以決定主問題的解法。

分治演算法通常以數學歸納法來驗證。而它的計算成本則多數以解遞迴關係式來判定。

大部分的排序演算法,例如合併排序、快速排序都是用非治法來進行。

分治法的優勢

  1. 解決困難問題 分治演算法是一個解決複雜問題的好工具,它可以把問題分解成若干個子問題,把子問題逐個解決,再組合到一起形成大問題的答案。

  2. 演算法效率

  3. 同步性

  4. 修正控制

關於分治法的實現

遞迴

在每一層遞迴上都有三個步驟:

  1. 分解:將原問題分解為若干個規模較小,相對獨立,與原問題形式相同的子問題。

  2. 解決:若子問題規模較小且易於解決時,則直接解。否則,遞迴地解決各子問題。

  3. 合併:將各子問題的解合併為原問題的解。

若在其解決步驟能在常數O(1)時間完成,則會顯現O(n)效能。當此解決步驟本身需求O(n)的運算時,則整體效能會是O(n log n)。注意: 利用掃描每個元素並對以找到的最大元素進行排序,可以更快速找到一個合集中的最大元素。

分治法並非始終都提供最快的實作內容。

標籤:演算法
(使用 Facebook 留言外掛程式 留言無法滿足本網站參加活動之資格,僅供非會員討論使用)

© 2021 - 耐美知識網