---
# System prepended metadata
title: 分而治之法 (Divide and Conquer)
---
# 分而治之法 (Divide and Conquer)
## 介紹
分而治之法藉著不斷將原問題分割成尺寸更小但同形態的問題以方便求解，最終再將解組合起來變成最終解。其主要有三個步驟：
1. 分割：將原問題分割成尺寸變小但相同形態的問題
2. 求解：當問題已經被分割到一個超級簡單的尺寸 (用肉眼就可以看出解答) 時，就可以開始求這些小問題的解。
3. 組合：每個小問題的解球出來後，還要經過一些組合才能得到更大的解。通常這步是最難的。
由於都是解同形態的問題，因此我們通常會使用遞迴函數來求解。了解完分而治之法後，你會發現這是一個由數學歸納法推出來的演算法。在數學歸納法我們常會假設演算法 $k$ 成立，然後去推得 $k+1$ 也成立。而在分而治之法， $k+1$ 就是我們原問題的尺寸， $k$ 就是代表我們將問題分割後的尺寸。雖然有點倒過來看，不過原理是一樣的。因此要發展一個分而治之法，通常都是先用數學歸納法證明，接著再從證明寫出演算法．
### 複雜度
分而治之法通常是由遞迴函數來實現，因此時間複雜度通常會寫成跟自己的前一階有關，寫完與前一階的關係式後再做後續的推導。通常會有兩種解法：
1. 展開遞迴：我們說時間複雜度通常會寫成與自己的前一階有關的函數，接著我們就把前一階再展開成前前，直到 basic case ，然後把它加總起來就是答案。
2. 假設法：假設時間複雜度就是某一個值，然後用數學歸納法證明真的是這個值。不過可能你要先很熟練分而治之法才有辦法假設得準。
### 範本
如果你要寫一個分而治之法卻不知道怎麼下手，建議從以下範本出發：
## 缺塊磁磚問題 （詳見影片）
## Binary Search
### 問題描述
假設給定一個排序好的數列，共 $n$ 個值，如何找出某個指定的值。
### 解法
一般來說每個數都找當然也可以，但這樣時間複雜度就是 $O(n)$ ，用分而治之法可以達到 $O(nlog(n))$。簡單來說就是每次都看一下中間值的大小，然後看要的值跟中間值的大小，若比中間值小就往左繼續搜，若比中間值大就往右繼續搜，直到找出來為止。
## Merge sort
### 問題描述：排序
### 解法
Merge sort 其實可以完全套用我們剛剛給的範本，先將東西切到最小並排序，然後進行合併：
詳細演算法如下：
範例流程如下：
### 時間複雜度
最後，我們要推導演算法的時間複雜度。首先，我們假設 size $n$ 的演算法要花 $T(n)$ 的時間來執行。分割跟判斷只要 $O(1)$ 時間，下一階遞迴函數是花費兩個 $T(n/2)$ 的時間。最終在組合時我們需要兩兩去做比較，可以發現其實我們要比較 $n-1$ 次才能比得完，因此會花費 $O(n)$ 的時間。$O(n)+O(1)=O(n)=cn$，其中 $c$ 是任意常數，經過上述講解，我們可以推得時間複雜度如下：
有幾點可以注意：
1. 天花板跟地板函數都可以忽略，不影響計算結果。
2. 有時可以假設更糟的 case 使推導更順利。像是這個範例需要 $n$ 為 2 的次冪數，所以 45 我們可以設成 64，讓推導更直觀。
首先，我們用 unrolling 可以推得以下結果：
接著，我們用假設法可以推得以下結果：
## Counting Inversion
### 問題描述
Counting Inversion 是在算兩個 size 相同的排序的差異性有多大。假設給定 10 首歌，兩個人分別為這 10 首歌排名，Counting Inversion 就是這兩個排名的差異性。
為了簡化題目，我們會先將所有歌曲按照第一個人的喜好排序。因此第一個人的排名結果就是 1，2，3，...，而第二個人就是亂數，舉例如下圖：
在圖中，只要我們發現第二個人某首歌的排名順序較後面的歌的排名低，則稱為一個 inversion。舉例，第二個人 (you) 的第 A 首歌的排名是 2，而後面第 C 首歌是排名是 1，那就會有一個 inversion。而我們最終就是希望可以找出 inversion 的數量，也就是Counting Inversion。
### 解法
當然，最簡單的方式就是把每一首歌的排名都跟每一首歌的排名比過，但這需要 $O(n^2)$ 的時間複雜度。我們希望可以在更短的時間就求出解，因此我們使用 Divide-and-conquer。
一樣，我們先用把他切小塊，待可以簡單算出兩小塊的 inversion 後，我們再把它組回來。流程跟圖解如下：
其中最難的一步還是計算 inversion (組合)，計算 inversion 時若兩個小步要計算還是要一個一個比，那還是需要花 $O(n^2)$ 的複雜度。因此我們在做計算 inversion 時需要一個小技巧，也就是順便使用 Merge sort 進行排序，這樣計算兩組 size 為 $n/2$ 的序列的 inversion 就只需要比較 $n/2$ 次，也就是只需要 $O(n)$。假設如下的範例，我固定用右邊的序列跟左邊的序列比有多少個 inversion，第一次用 $3$ 去比，那比完會得到有 $4$ 個，但我們可以先記住 $3$ 比到第三個值 ($4$) 才發生 inversion，因此我們下一個值 ($6$) 就可以從第三個值開始比，就不用從頭比一次，總共只會比 $6$ 次。既然計算 inversion 只需要 $O(n)$ 的時間，而 merge sort 的時間也只需要 $O(n)$，那總共就是只需要 $O(n)$ 的時間。從 Merge sort 的範例我們知道只要 Divide-and-conquer 在組合這一步的時間複雜度是 $O(n)$，那總共演算法的時間複雜度就是 $O(lg(n))$。
詳細演算法如下：
## Closest pair of points
### 問題描述
如果給定 $n$ 個二維直角坐標平面的點，如何求出歐式距離最近的兩點？
### 解法
同樣的，我們當然可以使用暴力解，花 $O(n^2)$ 的時間複雜度來計算每個點的距離，但我們用 Ｄivide-and-conquer 可以只花 $O(lg(2))$ 的時間複雜度。
解法的第一步，我們先找出所有的點在 x 軸上的中心點 (若是偶數點則找最離中心最近的左邊那點或右邊那點均可，只是接下來要統一)。接著以這個中心點切成兩半，找出左半邊和右半邊歐式距離最短的兩點，還有中心點附近歐式距離最短的兩點。比較這三組點，最短的即為我們要找的歐式距離最短的兩點。
較難的地方在於中心點附近如何定義，我們首先找到左半邊跟右半邊的最小歐式距離的兩個距離，接者將較小的那個定義為 $\delta$。接著我們定義中心點左右各延伸 $\delta$ 的範圍為中心點附近的範圍。接著我們對在這個範圍內的點，從 y 軸最高的點往下找，每個點將其座落在一個 $2\delta \times 2\delta$ 的範圍內，又以 $\delta/2$ 分成 16 等份，此時點必須落在最上面那一層。這時我們可以保證，若中間有兩個點他們的距離小於兩半部的最小距離 $\delta$，則某點必定落在某點的 16 格範圍內，且他們不可能在同一邊 (中心點的左邊或右邊)。理由大家可以自己畫圖看看或看影片裡的證明。
詳細演算法如下：
### 筆記
* merge sort 記憶體花費稍較 heap sort 大
## 參考
[交大電機工程學系江蕙如老師演算法課程 OCW](https://ocw.nycu.edu.tw/?course_page=all-course%2Fcollege-of-electrical-and-computer-engineering%2F%E6%BC%94%E7%AE%97%E6%B3%95-algorithms-%E9%9B%BB%E6%A9%9F%E5%B7%A5%E7%A8%8B%E5%AD%B8%E7%B3%BB-%E6%B1%9F%E8%95%99%E5%A6%82%E8%80%81%E5%B8%AB)
