# 分而治之法與遞迴關係

## 一、簡介

Divide-and-Conquer又稱為分而治之法。其中Divide指的是將一個較大的問題不斷切割成小問題。而Conquer是當最後切割成的小問題簡單到可以直接解決，就可以組合成大問題的答案。在程式語言中時常都會用到分而治之法的觀念，並結合遞迴的概念求解。

## 二、遞迴公式

#### 1.

$$
f(n) = a * f(n/b) + g(n)
$$

如果有一個大問題的大小是n，假設解出這個問題需要f(n)個步驟，而這個問題可以拆成a個小問題，每個小問題的大小是n/b，而拆成小問題需要g(n)個額外動作。那這個問題的通式就是如上面所示，然後f(n/b) 又能再進一步拆解。小問題再拆解到最後都有一個終止條件，也就是當拆到後面f(n/b)已經簡單到可以直接求解，就能把答案慢慢回推到原始的問題f(n)。這個概念可以延伸到以下各個範例。

#### 2.

$$
f(n) = a^kf(1) + \sum_{j=0}^{k-1}a^jg(n/b^j)
$$

如果假設n=b^k^，每個大問題都能拆成a個小問題，每個小問題大小都變成原本1/b倍，那麼可以如以下方式推導：
$$
f(n) = af(n/b) + g(n) = a^2 f(n/b^2) + ag(n/b) + g(n) = a^3 f(n/b^3) + a^2g(n/b^2) + ag(n/b) + g(n) ...
$$
經過k次的拆解後，問題已經拆成大小只剩下1，即可得到上述公式。

## 三、Big O

Big O可以讓我們來計算演算法的時間複雜度。

### 公式一：

$$
f(n) = af(n/b) + c
$$

##### 公式：

若f是遞增函數，且，如果b為>1的整數並能整除n，且a≧1、c是正實數。
$$
f(n)=
\begin{cases}
O(n^{log_ba})& \text{a > 1}\\
O(log~n)& \text{a = 1}
\end{cases}
$$
若n=b^k^(k為正整數)，且a≠1：
$$
f(n) = C_1n^{log_ba} + C_2
$$

$$
C_1 = f(1) + c/(a-1) \\C_2=-c/(a-1)
$$

##### 證明：

若n=b^k^ (k=log_bn)，且對照上面公式，g(n)=c，代回公式：
$$
f(n) = a^kf(1) + \sum_{j=0}^{k-1}a^jc=a^kf(1) + c\sum_{j=0}^{k-1}a^j
$$

###### 1. a=1

若n=b^k^，代回上面公式可以得到：
$$
f(n) = f(1) + ck = f(1) + c log_bn
$$
若n不是b的次方時，b^k^<n<b^(k+1)^，又因為f是遞增函數：
$$
f(n) ≦ f(b^{k+1}) = f(1) + c(k + 1) = (f(1) + c) + ck ≦ (f(1) + c) + c log_bn
$$
由此可知，不管n是不是b的次方，只要a=1時，f(n)都是O(log n)。

###### 2. a>1

若n=b^k^，代回上面公式根據等比級數公式可以得到：
$$
f(n)=a^kf(1) + c\sum_{j=0}^{k-1}a^j=a^k
f(1) + c(a^k − 1)∕(a − 1)=a^k[f(1) + c∕(a − 1)] − c∕(a − 1)= C_1n^{log_ba} + C2\\∵a^k = a^{log_b n} = n^{log_b a} ~~~∴C_1 = f(1) + c/(a-1)~~~C_2=-c/(a-1)
$$
若n不是b的次方時，b^k^<n<b^(k+1)^，又因為f是遞增函數：
$$
f(n) ≦ f(b^{k+1}) = C_1a^{k+1}+C_2≦(C_1a)a^{log_bn}+C_2≦(C_1a)n^{log_ba}+C_2
$$
由此可知，不管n是不是b的次方，只要a>1時，f(n)的Big-O得證。

### 公式二：

##### 公式：

f(n)是遞增函數，當n=b^k^(b為≧1的整數、k為正整數)，且a>=1、c為正實數、d為非負實數：
$$
f(n) = af(n∕b) + cn^d\\
f(n)=\left\{
\begin{aligned}
&O(n^d)& &{a < b^d}\\
&O(n^dlog~n)& &{ a=b^d}\\
&O(n^{log_ba})& &{a>b^d}
\end{aligned}
\right.
$$

##### 證明：

f(n) = a f(n/b) + cn^d^，假設n=b^k^，k=log_bn：

###### 1. a=b^d^

$$
f(n)=a^kf(1)+\sum_{j=0}^{k-1}a^jc(n/b^j)^d=a^kf(1)+\sum_{j=0}^{k-1}cn^d=a^kf(1)+kcn^d\\=a^{log_bn}f(1)+cn^dlog_bn=n^df(1)+cn^dlog_bn
$$

由此可證，a=b^k^時，f(n)=O(n^d^ log n)。

###### 2. a≠b^d^

$$
f(n) =C_1n^d + C_2n^{log_ba}~~~~~~~ C_1 = b^dc∕(b^d − a)，C_2 =f(1) + b^dc∕(a − b^d).
$$

利用數學歸納法可以證明以上的式子，這裡省略數學歸納法證明。

接著當a<b^d^時，log_ba<d：
$$
f(n)=C_1n^d+C_2n^{log_ba}<(C_1+C_2)n^d\\
∴f(n)=O(n^d)
$$
而當a>b^d^時，log_ba>d：
$$
f(n)=C_1n^d+C_2n^{log_ba}<(C_1+C_2)n^{log_ba}\\
∴f(n)=O(n^{log_ba})
$$

## 四、範例

### 1. 二分搜尋法

##### 觀念：

在一個已排序的數列中，可以利用二分搜尋法尋找特定的值。它的主要概念是每次都用一個範圍中間的值與目標值比大小，如果目標值比較大，表示目標元素在後半段；如果目標值比較小，表示目標元素在前半段。在下次搜尋的時候，只要拿新的範圍進行比較，如此反覆動作，直到找出相同的值，或者直到範圍只剩下一個元素時，表示要找的值並不存在。

##### 遞迴關係式：

f(n) = f(n/2) + 2 ；f(n)為利用二分搜尋法搜尋大小為n的數列所需的判斷次數

額外的判斷步驟g(n) = 2因為每一回合會跟中間值判斷一次，還會判斷目前的範圍還有沒有值存在。然後每回合要尋找的目標都會切一半，所以每回合原本大小為n的問題都會被切成一個大小為n/2的問題，如此不斷反覆。其中不一定每次n都是切成剛好一半，如果n是奇數，就會出現切成的兩半相差一個元素的情況。

##### 時間複雜度：

因為f(n) = f(n/2) + 2符合第三大點的第一個公式，a=1、b=2、c=2，因此由前面公式可以知道其時間複雜度為O(log n)。

### 2.數列中尋找最大最小值

##### 觀念：

每回合把數列都拆成兩半，並且把那兩半分別再重複切割動作，直到切成很多個大小為一的數列。如果大小為一的話，它就暫時是那個數列的最大值與最小值。然後再把它組合起來，問題就簡化成比較兩個數列的最大值與最小值，並且推算出新的最大值與最小值。

##### 遞迴關係式：

f(n) = 2 f(n/2) + 2 ；f(n)為算出大小為n的數列的最大值與最小值所需的比較次數

每回合先切成兩個數列，利用遞迴得出左右兩個數列的最大最小值再組合成原始的數列，需要的額外比較次數g(n)=2，因為要比較一次最大值與一次最小值：兩者最大值的較大值即為原始數列的最大值，兩者最小值的較小值即為原始數列的最小值。

##### 時間複雜度：

這個遞迴關係式符合第三大點的第一個公式，a=2、b=2、c=2，因此由公式可推得其時間複雜度為O(n^log2^)=O(n)。

### 3.Merge Sort

##### 觀念：

合併排序法是先不斷把數列分割成兩半，使其最後變成很多個大小為一的數列，然後再倆倆結合，結合的同時會順便排序兩個小數列，數列不斷結合最後就會結合成原本排序完的數列。

##### 遞迴關係式：

M(n) = 2M(n/2) + n ；M(n)為大小為n的數列排序所需的比較次數

額外的比較步驟g(n)<n，因為兩個已排序的數列結合時須分別會從兩個數列的最小值開始往後比較，每次取出兩者較小值放入新的數列並往後移一格，因此最少需判斷n/2次，最多需判斷n-1次。然後使用Merge Sort排序一個數列可以視為把兩個已排序數列結合，因此可以不斷分割成小問題解決。

##### 時間複雜度：

從M(n) = 2M(n/2) + n符合第三大點的第二個公式，a=2、b=2、c=1、d=1，a=b^d^，因此其時間複雜度為O(n log n)。

### 4.Fast Multiplication of Integers

##### 觀念：

把兩個整數利用二進位表示法轉換成兩個2n位數的數，假設a = (a_2n−1a_2n−2 ⋯ a1a0)₂ and b = (b_2n−1b_2n−2 ⋯ b1b0)₂。此時再假設a=2^n^A₁+A₀、b=2^n^B₁+B₀，則A₁ = (a_2n−1 ⋯ a_n+1a_n)₂、A₀ = (a_n−1 ⋯ a₁a₀)₂，B₁ = (b_2n−1 ⋯ b_n+1b_n)₂、B₀ = (b_n−1 ⋯ b₁b₀)₂。此時ab = (2^2n^ + 2^n^ )A₁B₁ + 2^n^ (A₁ − A₀)(B₀ − B₁) + (2^n^ + 1)A₀B₀。此時問題就簡化成3個n位數二進位數字的乘法運算相加。如此不斷重複簡化下去就可以只剩下一位數的二進位數字相乘。

##### 遞迴關係式：

f(n) = 3f(n/2) + Cn ；f(n)為兩個n位元的二進位數字相乘所需的位元運算次數

每回合額外所需的運算次數g(n)=Cn，代表把簡化的小問題相乘相加所需的位元運算次數。從上面的例子來說，ab = (2^2n^ + 2^n^ )A₁B₁ + 2^n^ (A₁ − A₀)(B₀ − B₁) + (2^n^ + 1)A₀B₀，因為是n個位數進行相乘相加，所以需要額外的運算次數是n的倍數，因此為Cn。

##### 時間演算法：

傳統的乘法時間複雜度為O(n^2^)，因為每個位數都要跟每個位數相乘到。

觀察其遞迴關係式，它符合第三大點的第二個公式，a=3、b=2、d=1，a>b^d^，其時間複雜度為O(n^log3^)，log₂3≒1.6。

### 5.Fast Matrix Multiplication

##### 觀念：

如果用一般的方式進行矩陣程法，n*n的矩陣程法總共需要n^3^次乘法以及n^2^(n-1)次加法。

假設A~H皆為(n/2)*(n/2)的矩陣：


如果用一般矩陣乘法的方式來看這個算式，一個n*n的矩陣乘法需要8次(n/2)\*(n/2)矩陣的相乘，以及4次的矩陣相加。

但如果用矩陣快速乘法的方式，又稱為施特拉森演算法：
$$
T_1=(A+D)(E+H)=AE+DH+AH+DE
$$

$$
T_2=(B-D)(G+H)=BG+BH-DG-DH
$$

$$
T_3=(C-A)(E+F)=CF+CE-AF-AE
$$

$$
T_4=D(G-E)=DG-DE
$$

$$
T_5=(A+B)H=BH+AH
$$

$$
T_6=(C+D)E=CE+DE
$$

$$
T_7=A(F-H)=AF-AH
$$

如此觀察其關係可以得出以下結論：
$$
M_{11}=T_1+T_2+T_4-T_5
$$

$$
M_{12}=T_5+T_7
$$

$$
M_{21}=T_4+T_6
$$

$$
M_{22}=T_1+T_3+T_6-T_7
$$

經過一回合，這個n\*n的矩陣乘法可以簡化成需7次(n/2)*(n/2)的矩陣乘法以及18次的矩陣加法。由於當n的數字較大時，乘法會比加法還要繁複很多，因此減少1次乘法增加14次加法還是能夠有效增加其矩陣乘法效率。

##### 遞迴關係式：

f(n) = 7f(n/2) + 18n^2^/4 ；f(n)為兩個n*n的矩陣相乘所需的運算次數(乘法/加減法)

因為每經過一回合n\*n的矩陣相成簡化為7個(n/2)\*(n/2)的矩陣乘法以及18次的矩陣加法，那7個(n/2)\*(n/2)的矩陣乘法又能繼續化簡，只要矩陣都還是偶數\*偶數就能夠繼續化簡。而額外的運算次數g(n)=18n^2^/4，因為每個(n/2)\*(n/2)的矩陣相加等同於兩個矩陣相對應的位置直接相加，因此需要(n/2)*(n/2)=n^2^/4個運算步驟(加法)，因此18次矩陣加法的運算次數就是8n^2^/4。

##### 時間複雜度：

如果用原本的方法，n*n的矩陣程法總共需要n^3^次乘法以及n^2^(n-1)次加法，因此總合起來其時間複雜度為O(n^3^)。

如果用快速的方法，當n是偶數時，f(n) = 7 f(n/2) + 18n^2^/4，符合第三大點的第二個公式，a=7、b=2、c=9/2、d=2，a>b^d^，因此其時間複雜度為O(n^log7^)，log₂7≒2.8。

### 6.The Closest-Pair Problem

##### 觀念：

如果在一個平面有n個點，那找最近兩個點距離的最直接方式就是把每兩個點的距離都算過一遍，但這種方法如果點很多效率就會很低，因為每兩個點都走過需要計算n*(n-1)/2次。

因此有一種利用分而治之法的演算法可以用來計算最短距離。一開始我們先複製成兩組一樣的點對，其中一組點對針對x座標排序，然後第二組針對y座標排序。我們先拿以x座標排序的點對，把全部的點對切成一半，分成兩組小問題運算。當這些點對不斷切割，切到左邊跟右邊都只剩下一個點，就可以暫時先拿這兩個點當作最短距離點對。回到最原始的問題，左邊的小問題經過不斷組合可以算出左邊的最短距離，右邊的也可以算出右邊的最小距離。此時有三種情況，全部的最短距離點對可能是左邊的最短距離點對、右邊的最短距離點對、或是一個點對在左邊一個在右邊，因此我們需要再拿三種可能比較最小點對。


算出d_L及d_R後，我們取d=min{d_L , d_R}，取中間切個的x座標±d之內的所有點進行比較 (因為只有距離中間d以內的點才可能形成左右兩個點的距離小於d)。此時我們拿前面用y座標排序的點對，取其符合x座標距離中間d以內的點，從y座標最小的點開始比較。每個點最多有可能跟其他7個點比較，因為只有在x座標距離中間d以內，y座標距離搜尋點d以內的點才有可能形成最短距離。


如上圖，每個方格內最多只可能有一個點，否則會形成點跟點之間距離小於d的矛盾，因此我們只需要拿用y座標排序過且在此矩形範圍內的點對進行比較即可，如果有算出任何點對距離小於d，即可更新最短距離點對d。對距離中間d範圍內的每個點做完同樣的動作後，即可推出最短距離點對的答案。

##### 遞迴關係式：

f(n) = 2f(n/2) + 7n ；f(n)為n組點對算出最短距離點對所需的比較次數

這個問題每回合可以分成兩個小問題運算，最後再組合推算原始問題的答案，額外的比較次數g(n)≦7n，因為在最差的情況，可能每個點都在x座標距離中間d的範圍內，而可能每個點都需要額外跟另外7個點比較，所以額外的比較次數最多為7n。

##### 時間複雜度：

如果用最直接的方法，總共需要運算n*(n-1)/2次，因此時間複雜度為O(n^2^)。

快速方法的遞迴關係式符合第三大點的第二個公式，a=2、b=2、c=7、d=1，a=b^d^，時間複雜度為O(n log n)。但還要考慮前面先排序的時間複雜度，因為使用merge sort時間複雜度也是O(n log n)，因此這整個演算法的時間複雜就是O(n log n)。