分治法(Divide&Conquer)

Introduction to Competitive Programming

核心概念

  • 分(divide):將大問題分成小問題
  • 治(conquer):遞迴計算出小問題的答案
  • 合(merge):將小問題的答案合併成大問題的答案
  • 通常子問題的大小是大問題的分數倍 (\(\frac{n}{b}\))

將分治套用在序列上

  • 分(divide):將大問題分成小問題
    通常序列上的問題都會把序列分成兩半，左半&右半

  • 治(conquer):遞迴計算出小問題的答案
    分成左半序列&右半序列後，分別遞迴求出各自的答案

  • 合(merge):將小問題的答案合併成大問題的答案
    求出左右兩半各自的答案後，合併跨越兩半的答案

套用分治法找序列最小值

給一個長度為 \(N\) 的整數序列，找出最小值

如何套用分治 ?

套用分治法找序列最小值

分(divide):將大問題分成小問題

把當前序列分成左右兩半
每半找最小值 直到序列大小變成只有一個元素

套用分治法找序列最小值

治(conquer):遞迴計算出小問題的答案

左半右半分別遞迴找最小值

套用分治法找序列最小值

合(merge):將小問題的答案合併成大問題的答案

當前序列的最小值為兩半分別的最小值中，比較小的

套用分治法找序列最小值













int arr[100005];
int divide(int l, int r){
    if(l == r)    return arr[l];
    // 分
    int m = (l+r)/2;
    // 治
    int x = divide(l, m); 
    int y = divide(m+1, r);
    // 合
    int ret = min(x, y);
    return ret;
}

複雜度是多少呢 ?

套用分治法找序列最小值













int arr[100005];
int divide(int l, int r){
    if(l == r)    return arr[l];
    // 分
    int m = (l+r)/2;
    // 治
    int x = divide(l, m); 
    int y = divide(m+1, r);
    // 合
    int ret = min(x, y);
    return ret;
}

每次分兩半: O(1)
遞迴下去: O(1)
合併答案: O(1)

會發現每個子問題內都是 O(1) 複雜度
因此複雜度為所有子問題數量的總和

一開始原問題分成兩半
兩半再各自分成兩半
最後一層總共有 n 個子問題

\(1+2+4+...+n\to n+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}...=2n\)

\(1+2+4+...+n\to n+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}...=2n\)

因此複雜度為 \(O(N)\)

Tiling Problem

給定一個 \(2^{n}\times 2^{n}\) 的方格，其中有一格已經填滿了
你要使用很多 L 型的方塊填滿方格，求出一種符合的解
image

考慮分治 ?
既然是二維的，那嘗試看看分四半?

左上、左下、右上、右下
image
會發現分的四半中只有其中一半有填滿一格，因此我們可以放一個方塊
讓其他三塊也恰好填滿一格

image
如此一來會發現，每半都有一格被填滿，
對於每半又會變成原本的問題

給定 \(2^{n-1}\times 2^{n-1}\) 的 的方格，其中有一格已經填滿了
你要使用很多 L 型的方塊填滿方格，求出一種符合的解
image image image image

然後繼續分四半，遞迴求解…

image

image
遞迴到 \(2\times 2\) 時會發現，每個 \(2\times 2\) 的區域會剛好

  • 一個已填滿的格子
  • 一個 L 型的區域未填滿

此時就是遞迴的中止條件，至於複雜度怎麼算呢?

第一層 1 個 \(2^n\times 2^n\)
第二層 4 個 \(2^{n-1}\times 2^{n-1}\)
第三層 \(4^2\) 個 \(2^{n-2}\times 2^{n-2}\)
…
總共 \(n\) 層

對於每層都花 O(1) 的時間放 L 型方塊
複雜度為 \(1 + 4 + 16 + ... +4^n = O(4^n)\)

分治法 v.s. DP

DP 屬於分治法的一種，而他們之間的差別在於 DP 會將子狀態的答案用空間儲存下來，以在重複呼叫時不用重複計算。而一般的分治法子問題不會被重複呼叫，因此不需要記錄所有答案。

分治法的複雜度

分治法的複雜度通常能寫成遞迴函數
可用數學方式解出遞迴函數的一般項以得到複雜度(但很難很麻煩)

遞迴樹法(Recursion-Tree Method)

把遞迴的狀態畫出來會發現長的就是一棵樹，
根節點為一開始的原問題，往下子節點為遞迴下去的子問題

把整棵遞迴樹畫出來後計算時間總和


第一層為 1 個長度為 N 的問題，\(O(N)\)
第二層為 2 個長度為 \(\frac{N}{2}\) 的問題，\(O(\frac{N}{2})\times 2\)
第三層為 4 個長度為 \(\frac{N}{4}\) 的問題，\(O(\frac{N}{4})\times 4\)
…
總共 \(O(\log N)\) 層

\(T(N) = O(N) + O(\frac{N}{2})\times 2 + O(\frac{N}{4})\times 4\)…
\(= O(N\log N)\)

主定理(Master Method)

大多情況子問題是大問題的分數倍，且遞迴之外的部分為多項式複雜度:
\(T(n)=aT(\frac{n}{b})+O(n^\alpha\log^kn)\),令\(c=\log_ba\)

  1. 若 \(c>\alpha\) 則複雜度為 \(T(n)=O(n^c)=O(n^{\log_ba})\)
  2. 若 \(\alpha>c\) 則複雜度為 \(T(n)=O(n^\alpha\log^kn)\)
  3. 若 \(c=\alpha\) 則複雜度為 \(T(n)=O(n^\alpha\log^{k+1}n)\)

常見遞迴函數複雜度

遞迴式 時間複雜度 範例
\(T(n) = T(\frac{n}{b})+O(1)\) \(O(\log N)\) 遞迴的二分搜
\(T(n) = 2 T(\frac{n}{2})+O(1)\) \(O(N)\) 序列找最大值
\(T(n) = 2 T(\frac{n}{2})+O(N)\) \(O(N\log N)\) Merge Sort
\(T(n) = 2 T(\frac{n}{2})+O(N\log N)\) \(O(N\log^2 N)\) 使用 std::sort 合併的 Merge Sort 作法

其餘情況

  • 如果只有一個子問題很好計算(與迴圈類似)
  • 如果子問題的大小與大問題成線性關係(\(n-k\))則是指數複雜度
  • 剩下的自己想通靈解遞迴函數

範例

合併排序(merge sort)

  • 問題：將一個長度為 \(n\) 的陣列排序
  • 分：將此陣列切半，分成左半邊與右半邊
  • 治：遞迴分別將左半邊與右半邊排序
  • 合：將兩個已排序好的陣列合併成一個有序陣列
  • 複雜度：\(T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)\)

合併排序(merge sort)

  • 問題：將一個長度為\(n\)的陣列排序
  • 分：將此陣列切半，分成左半邊與右半邊
  • 治：遞迴分別將左半邊與右半邊排序
  • 合：將兩個已排序好的陣列合併成一個有序陣列

合併排序(merge sort)

合：將兩個已排序好的陣列合併成一個有序陣列

使用內建函式 std::sort 每次複雜度為 \(O(N\log N)\)

\(T(n) = 2 T(\frac{n}{2})+O(N\log N) = O(N\log^2 N)\)

合併排序(merge sort)

實際上合併兩個排序好的序列只需要 \(O(N)\)
使用雙指針分別指向兩半的開頭，每次把比較小的放進陣列裡

\(O(N\log N)\to O(N)\)

合併排序(merge sort)

複雜度即可降低 !

\(T(n) = 2 T(\frac{n}{2})+O(N) = O(N\log N)\)

快速排序(quick sort)

  • 問題：將一個長度為 \(n\) 的陣列排序
  • 分：找一個 pivot，將陣列分成小於/大於 pivot 兩類(小於的丟左邊，大於的丟右邊)
  • 治：遞迴分別將分出來的兩段排序
  • 合：將兩陣列合併，由於左右邊皆有序，且右邊大於左邊，因此不用做動作
  • 平均複雜度：\(T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)\)
  • 最差複雜度：\(T(n)=T(n-1)+O(n)=O(n^2)\)

逆序數對

  • 問題：給你一個陣列，求有多少組 \((i,j)\) 符合 \(i<j, a_i>a_j\)，也就是前項大於後項(此問題等價 bubble sort 最少交換次數)

input

5
2 1 5 4 2

output

4

考慮分治法

分: 將序列分成前半與後半

治: 遞迴分別算出前半與後半的逆序數對

合: 計算橫跨兩半邊的逆序數對數量，也就是 \(i\) 在左半邊，\(j\) 在右半邊

  • 對於左半邊的每一項，右半邊有多少項比它小

  • 簡單的作法：

    • 將右半邊排序就可以用 lower_bound 計算，\(O(n\log n)\)

  • 難一點點的作法：

    • 將兩半邊分別排序就可以用雙指針計算，然而瓶頸在排序，\(O(n\log n)\)

回想 merge sort，既然你都遞迴分別處理了左半邊與右半邊，
不如用 merge sort 在計算完後順便把它排序好，
那麼就不需要重新排序了，\(O(n)\)

  • 複雜度：\(T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)\)

最大連續和

給一長度為 n 的陣列，詢問陣列中的最大連續元素總和

  • \(1\le n\le 2\cdot 10^5\)

input

5
1 1 -3 4 5

output

9

考慮分治法

分: 將陣列分成前半與後半

治: 遞迴分別算出前半與後半各自範圍內的最大連續和

合: 計算橫跨兩半邊的最大連續和

  • 從切的位置往左找最大後綴和，往右找最大前綴和
    加起來即為橫跨區間的最大連續和

最近點對

  • 問題：座標平面上給你 \(n\) 個點，求最近兩個點的距離
  • 分治：先把 \(n\) 個點用 \(x\) 排序，再分成左右兩半邊
  • 遞迴分別找出左右兩半的最近距離，剩下就是兩邊各選一點的情況
  • 假設遞迴出來的最近距離是 \(d\)，很直觀的可以知道只需考慮分割線左右各 \(d\) 距離內的點
  • 窮舉範圍內的點計算最近距離，最差仍是\(O(n^2)\)
  • 經由證明可以發現，若將這些點以 \(y\) 排序，那麼每個點只需要考慮後 4 個點而已
  • 因此可以做到 \(O(n\log n)\) 合併，若用 merge sort 的概念，在遞迴時順便對 \(y\) 排序，那麼就能做到\(O(n)合併\)
  • 複雜度：\(T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)\)


    然而這個問題唬爛才是正解

分治困難點

  • 想到可以用分治解
  • 合併通常是最難的，分與治通常都很制式

優化

  • 由於分治法使用遞迴，因此常數偏大
  • 如果仔細去解遞迴函數會發現主定理省掉的常係數其實很大
  • 因此一個常見的常數優化方法是：當遞迴到 \(n\) 很小時改用暴力計算
  • 例如最近點對遞迴到 \(n<10\) 時改用暴力計算
  • 例如 merge sort 遞迴到 \(n<50\) 時改用 insertion sort

總結

今天的內容為基礎的分治，之後還有很多很難的應用，
如計算符合的區間數量、樹上分治、圖上分治等等。

分治可能對於初學者來說是一個很大的檻，
但熟悉後對於你的基礎功、計算遞迴複雜度，
都會有很大的進步、以及往後的一些算法 (線段樹、CDQ 分治、DP優化)
也是建立在分治之上

而分治往往也能在很難的題目應用，如果熟悉的話也能應用在很多題目上
往往可以在比賽中為你找到另一條出路。

Question Time and Practice

Problem Set

Select a repo