分治法 - HackMD

{%hackmd @hipp0\Hippotumuxthem %} <style> .text-center{ text-align: center; //文字置中 } .text-left{ text-align: left; //文字靠左 } .text-right{ text-align: right; //文字靠右 } </style> <style> .reveal .slides { text-align: left; font-size:30px; } </style> ### 分治法內容 - 分治法介紹 - 複雜度 - 費式數列 - 結論 --- ### 分治法 (Divide and Conquer) 分治是一種非常重要的演算法思維模式與策略，有很多重要的演算法都是根據分治的思維模式，例如快速排序法、合併排序法、快速傅立葉轉換(FFT)、矩陣乘法、整數乘法以及在一些在計算幾何的知名演算法都是分治的策略。當碰到一個不曾見過的問題，分治往往是第一個思考的重點，因為分治的架構讓我們很容易找到比暴力要好的方法。 ---- ## 核心想法分治法主要有三個步驟，切割，解決，合併。 - 切割：把問題以「相同問題」切割成更多小的子問題。 - 解決：把切割完的子問題解決。 - 合併：把解決完的子問題合併起來成為問題的答案。 ---- ### 代碼 ```cpp= // 看問題需要回傳什麼型態 int Divide_and_Conquer(int left, int right) { // 要多小才不繼續分 if (right - left < 1) { // 回傳你小問題的答案 return 1; } int mid = (left + right)/2; // 切割問題 int left_return = Divide_and_Conquer(left, mid); int right_return = Divide_and_Conquer(mid+1, right); // 合併問題 (假設回傳相加) int total_return = left_return + right_return; return total_return; } ``` ---- ### 簡單例子1 (找序列最大/小值) 題目 : 給定長度為 N 的序列，找到最大值/最小值 ---- ### 想法按照分治法三個步驟，切割，解決，合併，把問題大化小。 - 切割: 分成左右兩半 (切到剩下兩個以下就停止) - 解決: 計算其最大值/最小值 - 合併: 根據左右兩半回傳的值，計算其最大值最小值並回傳 ---- ### 代碼 (計算最大值演示) ```cpp= int Divide_find_max(int left, int right, vector<int> &vec) { // 最小問題 if (right - left < 2) { return max(vec[left], vec[right]); } // 切割 int mid = (left + right)/2; int left_ret = Divide_find_max(left, mid, vec); int right_ret = Divide_find_max(mid+1, right, vec); int total_ret = max(left_ret, right_ret); return total_ret; } ``` ---- ### 簡單例子2 (合併排序法) 在排序那篇中，有提到合併排序法，合併排序法的根本原理就是分治法 ---- ### 想法按照分治法三個步驟，切割，解決，合併，把問題大化小。 - 切割: 分成左右兩半 (切到剩下兩個以下就停止) - 解決: 回傳排序好的序列 ---- ### 合併: 合併的時候，會拿到左右兩區間 "排序好的序列" ，這邊可以利用排序好的特性來進行合併。假設目前左區間回傳 \[ 1, 3, 8, 9] 右區間回傳 \[2, 4, 6,] ---- ### 合併: \[ 1, 3, 8, 9] \[2, 4, 6] 利用已經排序的特性，左邊一定比右邊小，所以可以把兩個序列從左邊比到右邊，放進新的序列中。 ---- ### 第一輪 \[ 1 , 3, 8, 9] \[ 2 , 4, 6] #### 新序列 \[ 1 ] ---- ### 第二輪 \[1, 3 , 8, 9] \[ 2 , 4, 6] #### 新序列 \[1, 2 ] ---- ### 第三輪 \[1, 3 , 8, 9] \[2, 4 , 6] #### 新序列 \[1, 2, 3 ] ---- ### 第四輪 \[1, 3, 8 , 9] \[2, 4 , 6] #### 新序列 \[1, 2, 3, 4 ] ---- ### 第五輪 \[1, 3, 8 , 9] \[2, 4, 6 ] #### 新序列 \[1, 2, 3, 4, 6 ] ---- ### 第六輪 \[1, 3, 8 , 9] \[2, 4, 6] #### 新序列 \[1, 2, 3, 4, 6, 8 ] ---- ### 第七輪 \[1, 3, 8, 9 ] \[2, 4, 6] #### 新序列 \[1, 2, 3, 4, 6, 8, 9 ] --- ### 複雜度這兩個簡單的例子可以推到 - 找最大值/最小值: $O(N)$ - 合併排序法: $O(NlogN)$ ---- ### 複雜度如果分割的很少，那每個問題的"量"就會很多，如果分割的很多，那每個問題的"量"雖然少，但合併次數也會很多，到底要怎麼來計算複雜度呢? ---- ### 複雜度分治是一個遞迴的演算法，不像迴圈的複雜度可以用加總的方法或是乘法計算，遞迴的複雜度是由遞迴關係式(recurrence relation)所表達。計算複雜度必須解遞迴關係式。遞迴關係又稱為差分方程式(difference equation)，解遞迴關係是個複雜的事情。分治演算法的常見形式是將一個大小為 n 的問題切成 a 個大小為 b 的子問題此外必須做一些分割與合併的工作。假設大小為 n 的問題的複雜度是 T(n)，而分割合併需要的時間是 f(n)，可以得到以下遞迴關係: $T(n) = aT(\frac{n}{b}) + f(n)$ ---- ### 主定理 (Master Method) 原理就是根據剛剛說到的，要來評估分割，合併的關係。一個分治的問題可以寫成 $T(n) = aT(\frac{n}{b}) + f(n)$ 主定理分成三種情況 ---- ### 情況一 (簡單說，合併解決問題 < 分割) 如果存在 ε > 0 使得 $f(n) = O(n^{log_b (a) - ε})$ 則 $T(n) = Θ(n^{log_b a})$ ---- ### 情況二 (合併解決問題 = 分割) 如果存在 ε $\geq$ 0 使得 $f(n) = Θ(n^{log_b a} log^εn)$ 則 $T(n) = Θ(n^{log_b a} log^{ε+1}n)$ ---- ### 情況三 (合併解決問題 > 分割) 如果存在 ε > 0 使得 $f(n) = Ω(n^{log_b (a) + ε})$ 且存在 c < 1 滿足 $af(\frac{n}{b}) \leq cf(n)$ $T(n) = Θ(f(n))$ ---- ### 複雜度分析-找最大值/最小值 $T(n) = aT(\frac{n}{b}) + f(n)$ 根據切割和合併寫下 $T(n) = 2T(\frac{n}{2}) + Θ(1)$ 根據情況一存在 ε > 0 使得 $f(n) = O(n^{log_2 (2) - ε})$ 所以 $T(n) = Θ(n^{log_2 2}) = Θ(n)$ ---- ### 複雜度分析-合併排序法 $T(n) = aT(\frac{n}{b}) + f(n)$ 根據切割和合併寫下 $T(n) = 2T(\frac{n}{2}) + Θ(n)$ 根據情況二存在 ε = 0 使得 $f(n) = Θ(n^{log_2 2} log^εn)$ 則 $T(n) = Θ(n^{log_2 2} log^{ε+1}n) = Θ(nlogn)$ ---- ### 題外話主定理並不是萬能的，還是會有很多例外，複雜一點就變得很難評估也有另外一種算法 Recursion-Tree Method，如果有興趣的話可以自行查詢。 --- ### 費式數列前面提過很多很多次，已經學會了最原始遞迴，後來的動態規劃，再到用線性代數的方式和矩陣快速冪求解。費式數列是一個很酷的數列，無處不在，甚至和黃金比例也產生了關係，接下來就來利用費式數列的一些性質，導出一些式子，就可以利用分治法求解。為了方便，定義費式數列從第一項開始，也就是 $F_1 = F_2 = 1$ ---- ### 性質一 (不會用到，但有趣提一下) $F_{n+2} = \sum_{k=1}^n F_k + 1$ ---- ### 證明首先有 $F_{n+2} = F_{n+1} + F_{n}$ 如果展開 n + 1 項 $F_{n+2} = F_{n} + F_{n-1} + F_{n}$ 繼續展開直到 n = 2 $F_{n+2} = F_{2} + F_{1} + ... + F_{n-1} + F_{n}$ 定義得 $F_{2} = 1$ 得到 $F_{n+2} = 1 + F_{1} + ... + F_{n-1} + F_{n}$ ---- ### 性質二第(m+n)項等於第 m 項乘上第(n-1)項後再加上第(m+1) 項乘上第 n 項之和 $F_{m+n} = F_m F_{n-1} + F_{m+1}F_{n}$ ---- ### 證明利用 $F_1 = F_2 = 1$，以及費式數列定義得 $F_{m+n} = F_{1}F_{m+n-2}+F_{2}F_{m+n-1}$ = $F_{1}F_{m+n-2} + F_{2}(F_{m+n-2} + F_{m+n-3})$ = $F_{m+n-2}(F_1 + F_2) + F_{2}F_{m+n-3}$ = $F_{2}F_{m+n-3} + F_3F_{m+n-2}$ 會發現是不是又跟一開始長的形式一樣，所以繼續推下去可以得到 = $F_{m-1}F_{n} + F_mF_{n-1}$ ---- ### 奇偶項恆等式 - 奇數項 $F_{2n-1} = F_n^2 + F_{n-1}^2$ - 偶數項 $F_{2n} = (F_{n-1} + F_{n+1})F_n = (2F_{n-1} + F_{n})F_n$ #### 證明由性質二 $F_{m+n} = F_m F_{n-1} + F_{m+1}F_{n}$ 奇數項令 m = n-1 直接得證偶數項令 m = n ，然後展開 n + 1 項得證 ---- ### 分治法求解剛剛得到 - 奇數項 $F_{2n-1} = F_n^2 + F_{n-1}^2$ - 偶數項 $F_{2n} = (F_{n-1} + F_{n+1})F_n = (2F_{n-1} + F_{n})F_n$ 所以發現可以直接根據奇數偶數分治下去 ---- ### 實作 ```cpp= const int mod = 1e9 + 7; long long fib(long long n) { // 從第一項算 if (n <= 2) return 1; if (n % 2 != 0) { long long left_ret = fib((n+1)/2 - 1); long long right_ret = fib((n+1)/2); long long total_ret = (left_ret*left_ret + right_ret*right_ret) % mod; return total_ret; } else { long long left_ret = fib(n/2 - 1); long long right_ret = fib(n/2); long long total_ret = (2*left_ret + right_ret)*right_ret % mod; return total_ret; } } ``` ---- ### 複雜度分析很不幸的，目前複雜度還是 $O(N)$，雖然分成了一半一半，但並沒有做到任何可以加快的部分。 #### 主定理 $T(n) = 2T(\frac{n}{2}) + O(1)$ 這個跟找最小/大值一樣。所以時間複雜度真的為 $O(N)$ ---- ### 加快會發現雖然分成了一半，可以讓 n 快速下降，但是總數量卻是不變的，不過，雖然總數量一樣，但是卻是會重複非常多次，所以如果能夠紀錄走過的路，那就可以優化了! 這邊使用 map 來儲存，因為除二的結果不重複的數量大概為 $logn$ 但是如果想用陣列儲存會因為 n 太大沒辦法存，所以只能使用速度較慢的 map 來存，但好在數量小，所以不太影響。 ---- ### 實作 ```cpp= const int mod = 1e9 + 7; map<long long,long long> mp; long long fib(long long n) { if (n == 0) return 0; if (n <= 2) return 1; if (mp.find(n) != mp.end()) return mp[n]; if (n % 2 != 0) { long long left_ret = fib((n+1)/2 - 1); long long right_ret = fib((n+1)/2); long long total_ret = (left_ret*left_ret + right_ret*right_ret) % mod; mp[n] = total_ret; return total_ret; } else { long long left_ret = fib(n/2 - 1); long long right_ret = fib(n/2); long long total_ret = (2*left_ret + right_ret)*right_ret % mod; mp[n] = total_ret; return total_ret; } } ``` ---- ### 時間複雜度 $O(logn)$ 因為每次都除二，所以總數量大概為 logn 雖然 map 的查詢，儲存時間為 $O(NlogN)$ 但是因為 $N = logn$，和題目總數 n ~ 1E12，實在是小到可以忽略，可以當成 O(1) (嚴謹一點當然可以寫成 $O(logn \times loglogn)$，放去主定理推也是可以得到一樣的結果) #### 主定理分成了左右兩半，但另外一邊反而會因為記錄過所以不會重複算到 $T(n) = T(n/2) + O(1)$ 根據情況二， ε = 0，可得時間複雜度為 $O(logn)$ ---- ### 實測當然也可以用程式碼來粗估複雜度 ```cpp= #include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; map<long long,long long> mp; int times = 0; long long fib(long long n) { if (n == 0) return 0; if (n <= 2) return 1; if (mp.find(n) != mp.end()) return mp[n]; times ++; if (n % 2 != 0) { long long left_ret = fib((n+1)/2 - 1); long long right_ret = fib((n+1)/2); long long total_ret = (left_ret*left_ret + right_ret*right_ret) % mod; mp[n] = total_ret; return total_ret; } else { long long left_ret = fib(n/2 - 1); long long right_ret = fib(n/2); long long total_ret = (2*left_ret + right_ret)*right_ret % mod; mp[n] = total_ret; return total_ret; } } void solve(){ long long n; mp.clear(); times = 0; cin >> n; if (n == 0) { cout << 0 << endl; }else{ cout << fib(n) << endl; } cout << "times = " << times << endl; cout << "----" << endl; return; } signed main(){ ios::sync_with_stdio(0), cin.tie(0); long long t = 1; cin >> t; while(t--){ solve(); } } ``` --- ### 優缺點 ---- ### 優點較為直觀，就是核心三步驟(分割，求解，合併)，通用問題全部都可以用。 ---- ### 缺點分治法的題目較為難寫，同時並不是說分治下去的時間複雜度就會好，還是需要去評估的。另外，雖然複雜度一樣，但只要有分出去的動作，就是一種 cost ，所以正常情況下，如果有不需要分治的狀況，分治的常數往往都是較差的一方。 ---- ### 常見優化方式 - 在分到量很小的時候，可以考慮暴力計算 - 注意是否會遇到相同子問題，可以儲存起來。 ---- ### 比較 (貪心，DP，分治) | | 貪心 | 動態規劃 | 分治法 | | -------- | -------- | -------- | -------- | | 類型 | 優化問題 | 優化問題 | 通用問題 | | 子問題結構 | 一個子問題 | 很多子問題 (不獨立) | 很多子問題 (獨立) | | 最優子結構 | 必須滿足 | 必須滿足 | 不須要 | | 子問題數 | 解決一個子問題 | 全部都要解決 | 全部都要解決 | | 子問題在最優解中 | 部分 | 部分 | 全部 | | 選擇/求解次數 | 先選擇再解決問題 | 先解決子問題再選擇 | 先選擇再解決問題 | ---- ### 總結分治對於初學者來說較有難度，但是對於基本功，看待遞迴複雜度很有幫助。分治法有很多延伸，像是線段樹、CDQ分治法、DP優化，FFT，NTT，Karatsuba，甚至數值方法中也很常用像是勘根法，也都是建立在分治上，可以說是非常實用(且困難)的算法。 ---- ### 練習 - J001 - J002 - I009 (費式數列用分治法求解) 挑戰題 (經典題) - J003