一、分治法

  • 分治法,簡而言之就是分而治之,把複雜的問題分成兩個或更多個相似或相似的子問題,直到子問題可以直接求解,最後再將子問題的解做合併。
  • 三步驟:DivideConquerMerge
  • 以 pseudo code 來表示大概像:
    void func(collection set) {
        // 子問題求解
        if (base_case) {
            // 根據要求將子問題解合併成母問題解
            do_something
            return;
        }
        // 將母問題分解成子問題
        for (collection subset : set) {
            func(subset);
        }
    }
    

Merge

Conquer

Divide

母問題

子問題1

子問題2

最小子問題1

最小子問題2

最小子問題3

最小子問題4

最小子問題解1

最小子問題解2

最小子問題解3

最小子問題解4

合併

母問題解

  • 舉例說明,河內塔遊戲: hanoi
    • 河內塔是由三根桿子以大小不同碟片所組成的遊戲,僧人一次可以從一根桿子移動一個碟片到另一根桿子,但是小的碟片若放憂大的碟片下面會使得小的碟片裂開(也就是碟片只能由上而下從小排到大),試問將一座塔從一根桿子完整的移動到另一根桿子需要移動多少次。 solve
    • 思考上面的情形,以三個碟片為例,若我們要從 AC 移動一座塔,我們可以將之分解成「如何把上面兩個碟片移動到 B」,因為剩下的一個大碟片,可以很簡單的從 A 移動到 C。也就是說 f3(A->C) = f2(A->B) + f1(A->C) + f2(B->C)
    • 再更進一步,f2(A->B)f2(B->C) 其實就是移動兩個碟片到另一座塔,所以可以分解成 f2(A->C) = f1(A->B) + f1(A->C) + f1(B->C),至此,我們已經把 f3 都分解成可以代表一次移動的最小子問題的解 f1 了:

      f3,A->C

      f2,A->B

      f1,A->C

      f2,B->C

      f1,A->C

      f1,A->B

      f1,C->B

      f1,B->A

      f1,B->C

      f1,A->C

    • 故我們可以以數學方式證明:
      T(n)=T(n1)+T(1)+T(n1)=2T(n1)+T(1)T(n1)=T(n2)+T(1)+T(n2)=2T(n2)+T(1)T(n)=2[2T(n2)+T(1)]+T(1)T(n)=2×2T(n2)+(1+2)T(1)T(n)=2k×T(nk)+(1+2++2k)T(1)k=n1T(n)=2n1×T(1)+(1+2++2n1)T(1)T(n)=2n1×T(1)+2n1121T(1)T(n)=(2n1)×T(1)\begin{array}{l} T(n)=T(n-1)+T(1)+T(n-1)=2T(n-1)+T(1)\\ T(n-1)=T(n-2)+T(1)+T(n-2)=2T(n-2)+T(1)\\ T(n)=2[2T(n-2)+T(1)]+T(1)\\ T(n)=2\times2T(n-2)+(1+2)T(1)\\ T(n)=2^k\times T(n-k)+(1+2+…+2^k)T(1)\\ 令k=n-1\\ T(n)=2^{n-1}\times T(1)+(1+2+…+2^{n-1})T(1)\\ T(n)=2^{n-1}\times T(1)+\frac{2^{n-1}-1}{2-1}T(1)\\ T(n)=(2^n-1)\times T(1) \end{array}
    • 得所需要的移動次數為 2n12^n-1
  • 分治法的特色
    1. 要解決的問題有一定的規模
    2. 該問題可以分解成若干個規模較小的問題
    3. 可以找到一個 base case,可以直接求解(如上述數學證明的T(1)T(1))
    4. 分解出來的子問題都是相互獨立的。(若有相依性,則無法使用分治法)
  • 分治法的時間複雜度
    • 將規模為 n 的問題分為 k個規模為 n/m 的子問題去解,那麼可以得到
      T(n)=kT(n/m)+f(n)T(n)=kT(n/m)+f(n)

二、分治法的應用

  • 令有一已排序的數列,欲查找該數列中是否有數值 x
    • 由於該數列已經過排序,所以我們無需遍歷整個數列,我們可以選擇每次挑選數列的中間值,若目標比中間值大,則選擇大的那側再繼續做篩選,此法稱為二元搜索法,其時間複雜度可以從線性搜索法的 O(n)O(n) 降低到 O(nlogn)O(n\log n)
    int binarySearch(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right-left)/2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target) 
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
    

2. Strassen 矩陣乘法

  • 試做一個矩陣AA與矩陣BB內積。
    • A=[A11A12A21A22],B=[B11B12B21B22],C=[C11C12C21C22],其中[C11C12C21C22]=[A11A12A21A22][B11B12B21B22] A=\left[\begin{matrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{matrix}\right], B=\left[\begin{matrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{matrix}\right], C=\left[\begin{matrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{matrix}\right],其中\\ \left[\begin{matrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{matrix}\right]=\left[\begin{matrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{matrix}\right]\cdot\left[\begin{matrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{matrix}\right]
    • 若通過一般展開可得
      C11=A11B11+A12B21C12=A11B12+A12B22C21=A21B11+A22B21C22=A21B12+A22B22 C_{11}=A_{11}\cdot B_{11}+A_{12}\cdot B_{21}\\ C_{12}=A_{11}\cdot B_{12}+A_{12}\cdot B_{22}\\ C_{21}=A_{21}\cdot B_{11}+A_{22}\cdot B_{21}\\ C_{22}=A_{21}\cdot B_{12}+A_{22}\cdot B_{22}
    • 從上可得計算兩個 nnn\cdot n 的矩陣內積需要 兩個 n2n2\frac{n}{2}\cdot\frac{n}{2} 的矩陣做 8 次的乘法加上 4 次的加法,其時間複雜度可以表示成:
      • T(n)=8T(n2)+Θ(n2)T(n2)=8T(n4)+Θ(n22)T(n)=8[8T(n4)+Θ((n2)2)]+Θ(n2)T(n)=82T(n4)+Θ(n2)+8Θ(n24)=82T(n4)+(1+2)Θ(n2)T(n)=8kT(n2k)+(1+2++2k1)Θ(n2)n=2kT(n)=n3T(1)+(n/2121)Θ(n2)Θ(n3) T(n)=8T(\frac{n}{2})+\Theta(n^2)\\ T(\frac{n}{2})=8T(\frac{n}{4})+\Theta({\frac{n}{2}}^2)\\ T(n)=8\left[{8T(\frac{n}{4})+\Theta({{(\frac{n}{2}})}^2)}\right]+\Theta(n^2)\\ T(n)=8^2T(\frac{n}{4})+\Theta(n^2)+8\Theta(\frac{n^2}{4})=8^2T(\frac{n}{4})+(1+2)\Theta(n^2)\\ T(n)=8^kT(\frac{n}{2^k})+(1+2+…+2^{k-1})\Theta(n^2)\\ 令n=2^k\\ T(n)=n^3T(1)+(\frac{n/2-1}{2-1})\Theta(n^2)\approx \Theta(n^3)
    • 若使用 Strassen 演算法
      1. 同樣將矩陣A,B,CA,B,C作分解,時間Θ(1)時間\Theta(1)
      2. 創建 10 個 n2n2\frac{n}{2}\cdot\frac{n}{2} 的矩陣 S1,S2,,S10S_1,S_2,…,S_{10},時間Θ(n2)\Theta(n^2)
        S1=B12B22S2=A11+A12S3=A21+A22S4=B21B11S5=A11+A22S6=B11+B22S7=A12A22S8=B21+B22S9=A11A21S10=B11+B12 S_1=B_{12}-B_{22}\\ S_2=A_{11}+A_{12}\\ S_3=A_{21}+A_{22}\\ S_4=B_{21}-B_{11}\\ S_5=A_{11}+A_{22}\\ S_6=B_{11}+B_{22}\\ S_7=A_{12}-A_{22}\\ S_8=B_{21}+B_{22}\\ S_9=A_{11}-A_{21}\\ S_{10}=B_{11}+B_{12}\\
      3. 遞迴的計算 7 個矩陣積 P1,P2,,P7P_1,P_2,…,P_7,其中每個矩陣PiP_i都是n2n2\frac{n}{2}\cdot\frac{n}{2}的。
        P1=A11S1=A11B12A11B22P2=S2B22=A11B22+A12B22P3=S3B11=A21B11+A22B11P4=A22S4=A22B21A22B11P5=S5S6=A11B11+A11B22+A22B11+A22B22P6=S7S8=A12B21+A12B22A22B21A22B22P7=S9S10=A11B11+A11B12A21B11A21B12 P_1=A_{11}\cdot S_1=A_{11}\cdot B_{12}-A_{11}\cdot B_{22}\\ P_2=S_2\cdot B_{22}=A_{11}\cdot B_{22}+A_{12}\cdot B_{22}\\ P_3=S_3\cdot B_{11}=A_{21}\cdot B_{11}+A_{22}\cdot B_{11}\\ P_4=A_{22}\cdot S_4=A_{22}\cdot B_{21}-A_{22}\cdot B_{11}\\ P_5=S_5\cdot S_6=A_{11}\cdot B_{11}+A_{11}\cdot B_{22}+A_{22}\cdot B_{11}+A_{22}\cdot B_{22}\\ P_6=S_7\cdot S_8=A_{12}\cdot B_{21}+A_{12}\cdot B_{22}-A_{22}\cdot B_{21}-A_{22}\cdot B_{22}\\\\ P_7=S_9\cdot S_{10}=A_{11}\cdot B_{11}+A_{11}\cdot B_{12}-A_{21}\cdot B_{11}-A_{21}\cdot B_{12}\\\\\\
      4. 藉由 PiP_i 來計算得到 矩陣 CC:時間Θ(n2)\Theta(n^2)
        C11=P5+P4P2+P6C12=P1+P2C21=P3+P4C22=P5+P1P3P7 C_{11}=P_5+P_4-P_2+P_6\\ C_{12}=P_1+P_2\\ C_{21}=P_3+P_4\\ C_{22}=P_5+P_1-P_3-P_7
      • 綜合已上可得:
        • T(n)={Θ(1)n=17Tn2+Θ(n2)n>1 T(n)=\bigg\lbrace \begin{array}{ll} \Theta(1)&若n=1\\ 7T{\frac{n}{2}}+\Theta(n^2)&若n>1 \end{array}
        • 故時間複雜度可推得 T(n)=Θ(nlog27)Θ(n2.807)T(n)=\Theta(n^{\log_27})\approx \Theta(n^{2.807})
      • 參考來源 Wikipedia

3. 合併排序 Merge Sort

  • [Algo] 0-4. 二元樹(Binary Tree)中有介紹過,合併排序快速排序都有著類似前序、後序的結構,
  • 步驟:
    1. 將數列拆成若干個只有 1 個元素的子數列(因為只有一個元素,所有可以視為已排序的數列)。
    2. 將已排序的數列兩兩合併,直到所有的數列都合併完成,即完成排序。
  • 程式碼實作:mergeSort

4. 快速排序 Quick Sort

  • 步驟:
    1. 選定一個數當作樞紐(pivot),將小於此數的值都放到左邊,大於此數的都放到右邊。
    2. 反覆同樣動作,直到子數列只有一個數,即完成排序。
  • 程式碼實作:quickSort

三、例題

1. 樹類問題

  • 樹相關的問題很常有著類似的解題結構:

    • base state 時,直接回傳答案(base result)。
    • 對根的節點做遞迴的處理
    • 將遞迴過後的回傳值做處理之後回傳。
    T function(TreeNode* root) {
        if (BASE_STATE) return BASE_RESULT;
        T left = function(root->left);
        T right = function(root->right);
        T res = SOME_OPERATION(left, right, root);
        return res;
    }
    

    1. Maxmium Binary Tree

    • Leetcode 654. Maximum Binary Tree
    • 給定一個數列,數列中的最大值為根,其索引值比根的索引值還小的子數列形成另一個子節,比根的索引值還大的子數列同樣形成另一個子節,以此類推。 max barytree
      • 以分治法的想法思考,我們會想得到一個函式 f(nums, s, e)s 代表數列的最小索引值,e 代表數列的最大索引值,若 r 為該數列最大值的索引值,那麼我們應該會得到一個節點,其左子節點為 f(nums, s, r-1),右子節點為 f(nums, r+1, e
      • 分治法的目標是要將問題由大化小,直到 base state 出現(即可以直接得到結果的一個狀態),以此題而言就是當 s == es < e 時,
        • s == e 時,應該要回傳 new TreeNode(s)
        • s < e 時,應該要回傳 NULL
      • 根據上面的分析可以得到下面完整的程式碼:
      TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
          return build(nums, 0, nums.size()-1);
      }
      TreeNode* build(vector<int>& nums, int start, int end) {
          if (start > end) return nullptr;
          if (start == end) return new TreeNode(nums[start]);
          int r = start;
          for (int i = start; i <= end; i++) {
              if (nums[i] > nums[r]) r = i;       // 找尋最大值的索引值
          }
          TreeNode* left = build(nums, start, r-1);
          TreeNode* right = build(nums, r+1, end);
          return new TreeNode(nums[r], left, right);
      }
      

    2.Balance a Binary Search Tree

    • Leetcode 1382. Balance a Binary Search Tree balance BST
    • 這題若想要用 rotate 的方式去思考會很難解,但若把它想成是一個已排序的數列,要進行 BST 的建樹的話,就非常簡單了。
    • 首先我們想得到一個已排序的數列,我們可以用 inorder traversal(中序遍歷) 去收集所有的節點。
    • 剩下的部分就跟Leetcode 108. Convert Sorted Array to Binary Search Tree一樣了,當我們將數列索引值正中間的節點擺在根節點,那麼一定會滿足其兩邊的深度差不超過 1。
    • 用分治法的思維,我們會想得到一個函式f(vec, s, e)s 代表數列的最小索引值,e代表數列的最大索引值,若 mid 為該數列最中間的索引值,那麼我們會得到一個節點,其左子節點為 f(vec, s, mid-1,右子節點為 f(vec, mid-1, e)
    • base states == es < e 時,
      • s == e 時,回傳 vec[s]
      • s > e 時,回傳 NULL
    • 根據上面的分析可得完整的程式碼:
        TreeNode* balanceBST(TreeNode* root) {
        vector<TreeNode*> vec;
        collect(root, vec);
        return build(vec, 0, vec.size()-1);
    }
    // 中序遍歷以收集到已排序的節點數列
    void collect(TreeNode* root, vector<TreeNode*>& vec) {
        if (!root) return;
        collect(root->left,vec);
        vec.push_back(root);
        collect(root->right,vec);
        root->left = nullptr;   // 預先將節點之間的關係先清除
        root->right = nullptr;
    
    }
    TreeNode* build(vector<TreeNode*>& vec, int start, int end) {
        if (start > end) return nullptr;
        if (start == end) return vec[start];
        int mid = start + (end-start)/2;        // 求中間點
        auto left = build(vec, start, mid-1);
        auto right = build(vec, mid+1, end);
        vec[mid]->left = left;
        vec[mid]->right = right;
        return vec[mid];
    }
    
    • 從上面兩個範例可以發現,樹類應用分治法於建樹問題上,基本上有著分常相似的框架,基本上都是想辦法把大問題拆成若干個同質的小問題,直到拆成 base state 之後再將答案組合起來。

2. Quick Select

  • Quick select 跟 quick sort 很類似,只是 quick select 選定一個 pivot 後,只針對一邊繼續做 select,假設每次都可以選到 median,則時間複雜度是 O(n)+O(n2)+O(n4)++O(n2k)+O(1)=O(n)O(n)+O(\frac{n}{2})+O(\frac{n}{4})+…+O(\frac{n}{2^k})+O(1)=O(n)。但也有可能每次都剛好選到最大值或最小值,則時間複雜度會退化成O(n2)O(n^2)

    1. Kth Largest Element in an Array

    int findKthLargest(vector<int>& nums, int k) {
    k = nums.size()-k;
    nth_element(nums.begin(), nums.begin()+k, nums.end());
    return nums[k];
    }
    
    • 以下為彷照其核心思想的實作:
    int findKthLargest(vector<int>& nums, int k) {
        return nth(nums, nums.size()-k);
    }
    int nth(vector<int>& nums, int k) {
        int left = 0;
        int right = nums.size()-1;
        while (left < right) {
            int pivot = partition(nums, left, right);
            if (pivot < k) {
                left = pivot+1;
            } else if (pivot > k) {
                right = pivot-1;
            } else {
                break;
            }
        }
        return nums[k];
    }
    // 避免時間複雜度退化成 O(n^2) 的方法, 確保每次選到的 pivot 都是相對中間的值
    void med(vector<int>& nums, int left, int right) {
        int mid = left + (right-left)/2;
        if (nums[left] >= nums[mid] && nums[mid] >= nums[right]) {
            return;
        } else if (nums[left] >= nums[mid] && nums[left] >= nums[right]) {
            if (nums[mid] >= nums[right]) {
                swap(nums[left], nums[mid]);
            } else {
                swap(nums[left], nums[right]);
            }
        } else if (nums[left] <= nums[mid] && nums[left] <= nums[right]) {
            if (nums[mid] >= nums[right]) {
                swap(nums[left], nums[right]);
            } else {
                swap(nums[left], nums[mid]);
            }
        }
    }
    int partition(vector<int>& nums, int left, int right) {
        med(nums, left, right);
        int pivot = left;
        int i = left;
        int j = right+1;
        while (i < j) {
            while (i < right && nums[++i] < nums[pivot]);
            while (j > left && nums[pivot] < nums[--j]);
            if (i >= j) break;
            swap(nums[i], nums[j]);
        }
        swap(nums[pivot], nums[j]);
        return j;
    }
    
  • 二元搜索法是經典的分治法應用之一,試想一個情景,若你有一本電話簿,已知電話簿是按照 alphabetical order 排序(按字母排序),那麼你會使用什麼樣的策略快速的找到你想要找的人的電話號碼呢?
    • 假設我們要找的人叫作 Willy。
    • 若用線性搜索法,從第一頁開始一頁一頁的找,直到找到 Willy,我們需要找完 A, B, C, ….,U, V 字首的名字才能找到 W 字首的頁面,也就是說其實 A - U 這段查找其實是多餘的,這樣的搜索法時間複雜度是 O(n)O(n),寫成程式碼會是這樣:
    string findWilly(vector<pair<string, string>> book) {
        for (int i = 0; i < book.size(); i++) {
            if (book[i].first == "Willy") return book[i].second;
        }
        return "Not Found";
    }
    
    • 若用二元搜索法,我們可以任意從書的中間選一頁,若選到的字首在 W 之前,我們只需從這頁開始往後,再任選一頁;反之,若選到的字首在 W 之後,我們只需從這頁開始往前,再任選一頁,重覆上面的動作直到找到 W,再依同樣的方法,找第二個字母。這樣的搜索法,時間複雜度是 O(logn)O(\log n),寫成程式碼會是這樣:
    string findWilly(vector<pair<string, string>> book) {
        int left = 0, right = book.size()-1;
        while (left <= right) {
            int mid = left + (right-left)/2;
            if (nums[mid].first == "Willy")
                return nums[mid].second;
            else if (nums[mid].first < "Willy")
                left = mid + 1;
            else if (nums[mid].first > "Willy")
                right = mid -1;
        }
        return "Not Found";
    }
    
      + 其中 `int mid = left + (right-left)/2` 是求中間值的寫法,為什麼不寫成 `int mid = (left+right)/2` 的原因是,避免兩數相加會溢數。
    
    • 遇到 strictly increase 的題目,二元搜索法的基本寫法如上,是左閉右閉的寫法,另一種常見的寫法是左閉右開的寫法。
    • 當遇到非 strictly increase 的題型,就會伴隨著左限跟右限的題型出現,這部分的詳細內容會在之後二元搜索篇詳細介紹。