動態分治演算法

⑴ 遞歸，分治演算法，動態規劃和貪心選擇的區別

遞歸，簡單的重復，計算量大。 分治，解決問題獨立，分開計算，如其名。 動態規劃演算法通常以自底向上的方式解各子問題， 貪心演算法則通常以自頂向下的方式進行； 動態規劃能求出問題的最優解，貪心不能保證求出問題的最優解

⑵ 分治演算法時間復雜度

一：分治演算法和遞歸
1.簡述遞歸

我們要講到分治演算法，我覺得有必要說一下遞歸，他們就像一對孿生兄弟，經常同時應用在演算法設計中，並由此產生許多高效的演算法。
直接或間接的調用自身的演算法稱為遞歸演算法。用函數自身給出定義的函數稱為遞歸函數。

int fibonacci(int n){
if (n <= 1) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
先簡單看一下經典的遞歸例子，博主會找個時間系統詳細的總結一下關於遞歸的內容。

2.簡述分治

分治法的設計思想是：

分–將問題分解為規模更小的子問題；
治–將這些規模更小的子問題逐個擊破；
合–將已解決的子問題合並，最終得出「母」問題的解；
一個先自頂向下，再自底向上的過程。

凡治眾如治寡，分數是也。—孫子兵法

3.分治法與遞歸的聯系

由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。

二：分治法的適用條件
分治法所能解決的問題一般具有以下幾個特徵：

1) 該問題的規模縮小到一定的程度就可以容易地解決
2) 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。
3) 利用該問題分解出的子問題的解可以合並為該問題的解；
4) 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。

第一條特徵是絕大多數問題都可以滿足的，因為問題的復雜性一般是隨著問題規模的增加而增加；

第二條特徵是應用分治法的前提它也是大多數問題可以滿足的，此特徵反映了遞歸思想的應用；、

第三條是關鍵，能否利用分治法完全取決於問題是否具有第三條特徵，如果具備了第一條和第二條特徵，而不具備第三條特徵，則可以考慮用貪心法或動態規劃法。

第四條特徵涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好

三：分治法的基本步驟
分解問題：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；（自頂向下）
這里涉及到一個平衡子問題的思想：人們從大量實踐中發現，在用分治法設計演算法時，最好使子問題的規模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規模大致相等的做法是出自一種平衡子問題的思想，它幾乎總是比子問題規模不等的做法要好。

解決問題：如果問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題，以得到小問題的解。
合並結果：將各個子問題的解合並為原問題的解：（自底向上）。
它的一般演算法設計模式如下：
divide-and-conquer(P){
if ( | P | <= n0) adhoc(P); //（2）解決問題：遞歸到小問題，則解決小規模的問題（自頂向下）
divide P into smaller subinstances P1,P2,...,Pk；//（1）分解問題
for (i=1,i<=k,i++)
yi=divide-and-conquer(Pi); //利用遞歸的解各子問題
return merge(y1,...,yk); //將各子問題的解合並為原問題的解（自底向上）
}
四：分治法的復雜性分析
從分治法的一般設計模式可以看出，用他設計出的程序一般是遞歸演算法。因此分治法的計算效率通常可以用遞歸方程來進行分析。
一個分治法將規模為n的問題分成k個規模為n/m的子問題去解。設分解閥值（表示當問題P規模不超過n0時，問題已容易解出，不必再繼續分解）n0=1，且adhoc解規模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合並為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規模為|P|=n的問題所需的計算時間，則有：

通常可以用展開遞歸式的方法來解這類遞歸方程，反復帶入求解得

⑶ 比較「分治法」和「動態規劃法」的異同點和優缺點

共同點：
將待求解的問題分解成若乾子問題，先求解子問題，然後再從這些子問題的解得到原問題的解。
不同點：
1、適合於用動態規劃法求解的問題，分解得到的各子問題往往不是相互獨立的；
而分治法中子問題相互獨立。
2、動態規劃法用表保存已求解過的子問題的解，再次碰到同樣的子問題時不必重新求解，而只需查詢答案，故可獲得多項式級時間復雜度，效率較高；
而分治法中對於每次出現的子問題均求解，導致同樣的子問題被反復求解，故產生指數增長的時間復雜度，效率較低。

⑷ 動態規劃演算法的基本思想

動態規劃演算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題。

拓展資料：

動態規劃的實質是分治思想和解決冗餘，因此動態規劃是一種將問題實例分析為更小的、相似的子問題，並存儲子問題的解而避免計算重復的子問題，以解決最優化問題的演算法策略
動態規劃所針對的問題有一個顯著的特徵，即它對應的子問題樹中的子問題呈現大量的重復。動態規劃的關鍵在於，對於重復的子問題，只在第一次遇到時求解，並把答案保存起來，讓以後再遇到時直接引用，不必要重新求解。