Ch4：Divide-and-Conquer

分治法是透過將原問題分解成幾個規模較小、形式相同或相似的子問題，遞迴地解決各子問題，最後再將這些子問題的解合併，得到原問題的解。

基本步驟

所有分治法皆可拆分為三個步驟：

1. Divide（分割）：把大規模問題分割成好幾個小問題
2. Conquer（征服）：對每個小問題遞迴求解
3. Combine（合併）：整合小問題的答案，形成原問題的答案

範例：矩陣乘法

$n\times n$ 矩陣乘法可以透過分治法來加快執行時間

• 問題：
  $A\times B=C$
• 先把
  $n\times n$ 矩陣分割成 4 個
  $\frac{n}{2}\times \frac{n}{2}$ 矩陣
• $A=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right),B=\left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right)$
• $$\begin{array}{rl}C=A\times B& =\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right)\times \left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right)\\ & =\left(\begin{array}{cc}{A}_{11}\times B_{11}+A_{12}\times B_{21}& A_{11}\times B_{12}+A_{12}\times B_{22}\\ A_{21}\times B_{11}+A_{22}\times B_{21}& A_{21}\times B_{12}+A_{22}\times B_{22}\end{array}\right)\end{array}$$
• 我們必須求出這八個小乘法然後加起來，就可以得到 C 的答案
• Presudo code：
  
• 遞迴式：
  $T(n)=8T(n/2)+\mathrm{\Theta }(1)$

遞迴式轉一般式的解法

替換法（Substitution Method）：

• 先猜測遞迴式的解
• 利用 數學歸納法 或 直接替換來證明

遞迴樹法（Recursion-Tree Methods）：

• 將遞迴關係化成一顆樹，每一層代表一次分割子問題
• 步驟：
  • 範例：
    $T(n)=3T(n/4)+\mathrm{\Theta }(n^2)$
  • 先畫出第一層：
    
  • 然後畫出第二層：
    
  • 第三層：
    • $T(n/4)=3T(n/16)+\mathrm{\Theta }((n/4{)}^2)$
      
  • 依此類推，然後每一層加起來找規律：
    

主定理（Master Theorem）

主定理並非萬用，必須遞迴式符合格式才可以用

• 當遞迴式為
  $T(n)=aT(n/b)+f(n)$ 時：
  • Case 1：當
    $\frac{f(n)}{n^{{\log }_{b}a}}\to 0$
    • 即
      $f(n)<n^{{\log }_{b}a}$
    • $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$
  • Case 2：當
    $\frac{f(n)}{n^{{\log }_{b}a}}=constant$
    • 即
      $f(n)=n^{{\log }_{b}a}$
    • $T(n)=\mathrm{\Theta }(f(n)\lg n)$
  • Case 3：當
    $\frac{f(n)}{n^{{\log }_{b}a}}\to \mathrm{\infty }$
    • 滿足
      $\mathrm{for}ϵ>0,f(n)=\mathrm{\Omega }(n^{{\log }_{b}a-ϵ})$
    • 正規化條件：
      • 滿足
        $af(n/b)\le cf(n)$
      • 即
        $f(n)$ 為多項式函數
    • 即
      $f(n)>n^{{\log }_{b}a}$
    • $T(n)=\mathrm{\Theta }(f(n))$