<style> .reveal .slides { text-align: left; font-size:35px; } #red{ color:red; } #gre{ color:green; } </style> # 分治法(Divide&Conquer) Introduction to Competitive Programming 2/7 --- ## 核心概念 - 分(divide):將大問題分成小問題 - 治(conquer):遞迴計算出小問題的答案 - 合(merge):將小問題的答案合併成大問題的答案 - 通常子問題的大小是大問題的分數倍($\frac{n}{b}$) ---- ## 套用分治法找序列最小值 給一個長度為 $N$ 的整數序列，找出最小值 如何套用分治 ? ---- ## 套用分治法找序列最小值 分(divide):將大問題分成小問題 把當前序列分成左右兩半 每半找最小值 直到序列大小變成只有一個元素 ---- ## 套用分治法找序列最小值 治(conquer):遞迴計算出小問題的答案 左半右半分別遞迴找最小值 ---- ## 套用分治法找序列最小值 合(merge):將小問題的答案合併成大問題的答案 當前序列的最小值為兩半最小值中比較小的 ---- ## 套用分治法找序列最小值 ```cpp= 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; } ``` 複雜度是多少呢 ? ---- ## 套用分治法找序列最小值 ```cpp= 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) 複雜度 因此複雜度為所有子問題數量的總和 一開始原問題 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)$ ---- ### 分治法 v.s. DP DP 屬於分治法的一種，而他們之間的差別在於 DP 會將子狀態的答案用空間儲存下來，以在重複呼叫時不用重複計算。而一般的分治法子問題不會被重複呼叫，因此不需要記錄所有答案。   --- ## 分治法的複雜度 分治法的複雜度通常能寫成遞迴函數 可用數學方式解出遞迴函數的一般項以得到複雜度(但很難很麻煩) ---- ### 主定理(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)$ ---- - 經由[證明](https://oi-wiki.org/geometry/nearest-points/)可以發現，若將這些點以 $y$ 排序，那麼每個點只需要考慮後3個點而已 - 因此可以做到 $O(n\lg n)$ 合併，若用 merge sort 的概念，在遞迴時順便對 $y$ 排序，那麼就能做到$O(n)合併$ - 複雜度：$T(n)=2T(\frac{n}{2})+O(n)=O(n\lg n)$ </br> <font color="#252525"><small>然而這個問題唬爛才是正解</small></font> --- ### 分治困難點 - 想到可以用分治解 - 合併通常是最難的，分與治通常都很制式 ---- ### 優化 - 由於分治法使用遞迴，因此常數偏大 - 如果仔細去解遞迴函數會發現主定理省掉的常係數其實很大 - 因此一個常見的常數優化方法是：當遞迴到 $n$ 很小時改用暴力計算 - 例如最近點對遞迴到 $n<10$ 時改用暴力計算 - 例如 merge sort 遞迴到 $n<50$ 時改用 insertion sort