Introduction to Competitive Programming
將分治套用在序列上
分(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)\)
給定一個 \(2^{n}\times 2^{n}\) 的方格,其中有一格已經填滿了
你要使用很多 L 型的方塊填滿方格,求出一種符合的解
考慮分治 ?
既然是二維的,那嘗試看看分四半?
左上、左下、右上、右下
會發現分的四半中只有其中一半有填滿一格,因此我們可以放一個方塊
讓其他三塊也恰好填滿一格
如此一來會發現,每半都有一格被填滿,
對於每半又會變成原本的問題
給定 \(2^{n-1}\times 2^{n-1}\) 的 的方格,其中有一格已經填滿了
你要使用很多 L 型的方塊填滿方格,求出一種符合的解
然後繼續分四半,遞迴求解…
遞迴到 \(2\times 2\) 時會發現,每個 \(2\times 2\) 的區域會剛好
此時就是遞迴的中止條件,至於複雜度怎麼算呢?
第一層 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)\)
DP 屬於分治法的一種,而他們之間的差別在於 DP 會將子狀態的答案用空間儲存下來,以在重複呼叫時不用重複計算。而一般的分治法子問題不會被重複呼叫,因此不需要記錄所有答案。
分治法的複雜度通常能寫成遞迴函數
可用數學方式解出遞迴函數的一般項以得到複雜度(但很難很麻煩)
把遞迴的狀態畫出來會發現長的就是一棵樹,
根節點為一開始的原問題,往下子節點為遞迴下去的子問題
把整棵遞迴樹畫出來後計算時間總和
第一層為 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)\)
大多情況子問題是大問題的分數倍,且遞迴之外的部分為多項式複雜度:
\(T(n)=aT(\frac{n}{b})+O(n^\alpha\log^kn)\),令\(c=\log_ba\)
遞迴式 | 時間複雜度 | 範例 |
---|---|---|
\(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 作法 |
合:將兩個已排序好的陣列合併成一個有序陣列
使用內建函式 std::sort 每次複雜度為 \(O(N\log N)\)
\(T(n) = 2 T(\frac{n}{2})+O(N\log N) = O(N\log^2 N)\)
實際上合併兩個排序好的序列只需要 \(O(N)\)
使用雙指針分別指向兩半的開頭,每次把比較小的放進陣列裡
\(O(N\log N)\to O(N)\)
複雜度即可降低 !
\(T(n) = 2 T(\frac{n}{2})+O(N) = O(N\log N)\)
input
5
2 1 5 4 2
output
4
考慮分治法
分: 將序列分成前半與後半
治: 遞迴分別算出前半與後半的逆序數對
合: 計算橫跨兩半邊的逆序數對數量,也就是 \(i\) 在左半邊,\(j\) 在右半邊
簡單的作法:
難一點點的作法:
回想 merge sort,既然你都遞迴分別處理了左半邊與右半邊,
不如用 merge sort 在計算完後順便把它排序好,
那麼就不需要重新排序了,\(O(n)\)
給一長度為 n 的陣列,詢問陣列中的最大連續元素總和
input
5
1 1 -3 4 5
output
9
考慮分治法
分: 將陣列分成前半與後半
治: 遞迴分別算出前半與後半各自範圍內的最大連續和
合: 計算橫跨兩半邊的最大連續和
今天的內容為基礎的分治,之後還有很多很難的應用,
如計算符合的區間數量、樹上分治、圖上分治等等。
分治可能對於初學者來說是一個很大的檻,
但熟悉後對於你的基礎功、計算遞迴複雜度,
都會有很大的進步、以及往後的一些算法 (線段樹、CDQ 分治、DP優化)
也是建立在分治之上
而分治往往也能在很難的題目應用,如果熟悉的話也能應用在很多題目上
往往可以在比賽中為你找到另一條出路。