JavaScript 學演算法（二十三）- 分治法、動態規劃

這週是六角鼠年鐵人賽第三十二週。

何謂分治法

分治法（Divide-and-Conquer） 或稱 各個擊破法、切割征服法，是一種演算法思想，而不是用於解決特定問題的演算法。

設計思想如字面上的意義：將難以直接解決的問題，切分成可簡單處理的小問題，再將小問題的結果合併，即原始問題的答案。

1. 演算法思想

對於一個規模為 n 的問題，若該問題可以容易地解決（比如說規模 n 較小）則直接解決，否則將其分解為 k 個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞迴地解這些子問題，然後將各子問題的解合併得到原問題的解。

2. 基本流程

分治法在每一層遞迴上都有三個步驟：

分解（divide）：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
解決（conquer）：若子問題規模較小且易於解決時，則直接求解。
合併（combine）：將各子問題的解合併，合併後的結果為原問題的解。

3. 適用的情況

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

該問題的規模縮小到一定的程度就可以容易地解決；
該問題可以分解爲若干個規模較小的相同問題，即該問題具有 最佳子結構（Optimal Substructure） 性質；
利用該問題分解出的子問題的解，可以合併爲該問題的解；
該問題所分解出的各個子問題是相互獨立的。

若子問題不是互相獨立的，有互相重疊部分（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解），如果使用分治法會重複計算重疊的子問題，造成浪費效能。建議改用 動態規劃。

4. 實作方式

分治法最適合使用遞迴來實作，但遞迴和迭代是一一對應的，分治法只是一種演算法思想，所以使用迭代來實作也沒問題。

之前提過的 合併排序 和 快速排序 都是使用分治法的經典問題。

何謂動態規劃

動態規劃（Dynamic programming, DP） 與分治法類似。

1. 演算法思想

動態規劃也是一種分治思想，同樣是將待求解的問題分解為若干個子問題。但與分治法最大的差別是，動態規劃經分解後得到的子問題往往不是互相獨立的，有互相重疊部分（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解），因此需要用記憶體儲存解子問題的解，以便下次需要同一個子問題解之時直接使用（避免重複運算）

2. 基本流程

動態規劃的主要難點在於理論上的設計：

定義原問題與子問題的關係，可使用遞迴關係表示；
以自底向上或自頂向下的記憶化方式，儲存子問題的解；
決定如何得到完整的最佳解。

3. 適用的情況

使用動態規劃的問題具有以下性質：

最佳子結構（Optimal Substructure）；
無後效性，即子問題的解一旦確定，就不再改變，不受在這之後、包含它的更大的問題的求解決策影響。
子問題重疊的性質。

3. 費氏數列

我們來看費氏數列。

若使用遞歸實作：

1
2
3
4
5
6


function fibonacci(n) {
  if (n < 2) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

雖然使用遞歸簡單明瞭，但子問題並不是獨立：

1
2
3
4
5
6


f(5) = f(4) + f(3);
f(4) = f(3) + f(2);
f(3) = f(2) + f(1);
f(2) = f(1) + f(0);
f(1) = 1;
f(0) = 0;

求 f(5) 就必須算出 f(4) 和 f(3)
求 f(4) 就必須算出 f(3) 和 f(2)
求 f(3) 就必須算出 f(2) 和 f(1)

很明顯的，子問題重疊，會出現重複計算，因此導致執行效率不佳，當 n 非常大時，直接計算到爆炸，時間複雜度 $O(2^n)$、空間複雜 $O(n)$。

若我們用變數 dp 將結果儲存，就可以避免重複計算：

1
2
3
4
5
6
7


function fibonacci(n) {
  let dp = [0, 1, 1];
  for (let i = 3; i <= n; i += 1) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

時間複雜度 $O(n)$、空間複雜 $O(n)$。

優化，只存上一個和當前的值，減少記憶體空間：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


function fibonacci3(n) {
  if (n === 0) return 0;
  if (n === 2 || n === 1) return 1;
  let prev = 1;
  let curr = 1;
  for (let i = 3; i <= n; i += 1) {
    let sum = prev + curr;
    prev = curr;
    curr = sum;
  }
  return curr;
}

時間複雜度 $O(n)$、空間複雜 $O(1)$。