owned this note   changed a year ago  
Published Linked with GitHub

分治法內容

  • 分治法介紹
  • 複雜度
  • 費式數列
  • 結論

分治法 (Divide and Conquer)

分治是一種非常重要的演算法思維模式與策略，有很多重要的演算法都是根據分治的思維模式，例如快速排序法、合併排序法、快速傅立葉轉換(FFT)、矩陣乘法、整數乘法以及在一些在計算幾何的知名演算法都是分治的策略。

當碰到一個不曾見過的問題，分治往往是第一個思考的重點，因為分治的架構讓我們很容易找到比暴力要好的方法。

核心想法

分治法主要有三個步驟，切割，解決，合併。

  • 切割：把問題以「相同問題」切割成更多小的子問題。
  • 解決：把切割完的子問題解決。
  • 合併：把解決完的子問題合併起來成為問題的答案。

代碼


















// 看問題需要回傳什麼型態
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 的序列，找到最大值/最小值

想法

按照分治法三個步驟，切割，解決，合併，把問題大化小。

  • 切割: 分成左右兩半 (切到剩下兩個以下就停止)
  • 解決: 計算其最大值/最小值
  • 合併: 根據左右兩半回傳的值，計算其最大值最小值並回傳

代碼 (計算最大值演示)














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\)

所以發現可以直接根據奇數偶數分治下去

實作

















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 來存，但好在數量小，所以不太影響。

實作





















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)\)

實測

當然也可以用程式碼來粗估複雜度



















































#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
Select a repo