分治法

在電腦科學中，分治法（Divide and conquer）是建基於多項分支遞歸的一種很重要的演算法範式。字面上的解釋是「分而治之」，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併。

這個技巧是很多高效演算法的基礎，如排序算法（歸併排序、快速排序）、大數乘法（Karatsuba演算法）、Q1209543、語法解析（如Q15419395）、Q21055608，以及離散傅立葉變換（FFT）。

另一方面，理解及設計分治法演算法的能力需要一定時間去掌握。正如以歸納法去證明一個理論，為了使遞歸能夠推行，很多時候需要用一個較為概括或複雜的問題去取代原有問題。而且並沒有一個系統性的方法去適當地概括問題。

分治演算法通常以數學歸納法來驗證。而它的計算成本則多數以解遞迴關係式來判定。

## 分而治之

分治法程式設計範式常用於求解問題的最優解。其基本思想是：將一個給定問題分解為兩個或多個更簡單的相似子問題，依次求解，再組合各子問題的解以解決原問題；足夠簡單的問題則直接求解。例如，對 n 個自然數組成的列表進行排序，可將其拆分為各含約 n/2 個數的兩個列表，分別排序後再適當交錯合併，即得排序結果（見示意圖）。此方法即稱為歸並排序算法。

分治法這個名稱有時亦會用於將問題簡化為只有一個細問題的演算法，例如用於在已排序的列中尋找其中一項的折半搜索算法（或是在數值分析中類似的勘根演算法）。這些演算法比一般的分治演算法更能有效地執行。其中，假如演算法使用尾部遞歸的話，便能轉換成簡單的迴圈。但在這廣義之下，所有使用遞歸或迴圈的算法均被視作「分治演算法」。因此，有些作者考慮「分治法」這個名稱應只用於每個有最少兩個子問題的演算法。而只有一個子問題的曾被建議使用減治法這個名稱。

分治法的一個重要應用在於最優化：若在每個步驟中能以常數因子縮減（「剪枝」）搜索空間，則整體演算法與剪枝步驟具有相同的漸近複雜度，常數取決於剪枝因子（通過對幾何級數求和可得）；此方法稱為剪枝搜尋。

## 早期歷史上的先例

早期的此類演算法主要是減治演算法——原始問題被逐步拆分為單個子問題，實際上可以以迭代方式求解。

折半搜索算法——一個將原來問題連逐地拆細成大約一半大小的單一子問題的分治演算法——擁有一段悠長歴史。雖然演算法在電腦上的清楚描述出現在1946年約翰莫齊利（John Mauchly）的一篇文章裡，然而利用已排序的物件序列去加快搜尋的構想早已在公元前200年的巴比倫尼亞出現。另一個單一子問題的分治演算法是找出2個數的最大公因數的輾轉相除法（透過將數字化小至使子問題變得簡單），於公元前數世紀已經出現。

一個早期有多個子問題的分治演算法是高斯在1805年描述關於快速傅立葉變換的演算法，儘管他沒有量化地分析它的操作數目，而快速傅立葉變換直至在一世紀之後被重新發現之前亦沒有廣泛流傳。這個演算法現在稱為庫利－圖基快速傅立葉變換演算法。

至於專門用於電腦之上而且正確地分析的分治演算法早期例子，則可以數到約翰·馮·諾伊曼於1945年發明的歸並排序。

另一個顯著的例子是Anatolii Alexeevitch Karatsuba於1960年發明在$O(n^{\log_2 3})$步驟內將兩個n位數相乘的Karatsuba演算法。它反證了安德雷·柯爾莫哥洛夫於1956年認為這個乘法需要$\Omega(n^2)$步驟的猜想。

高德納舉了一個最初並沒有涉及電腦的分治演算法例子，就是一般郵局用於分發信件的方法：信件在主要郵局根據不同的地理範圍而分到不同的袋裡，每個袋亦在運送到地區郵局時分到更小的袋裡，如是者直至信件被派發為止。這個方法與早於1929年的打孔卡排序機所用的基數排序相類同。

## 優勢

### 解決困難問題

分治演算法是一個解決複雜問題的好工具，它可以把問題分解成若干個子問題，把子問題逐個解決，再組合到一起形成大問題的答案。比如，漢諾塔問題如果採用分治演算法，可以把高度為n的塔的問題轉換成高度為n-1的塔來解決，如此重複，直至問題化簡到可以很容易的處理為止。

### 演算法效率

人們發現有很多效率很高的分治演算法，比如，Karatsuba快速乘法算法、快速排序算法和並行演算法、矩陣乘法的施特拉森演演算法、快速傅立葉變換等。

在以上所有示例中，分治法使得解的漸近代價得到改善。例如，若（a）基本情況的規模有常數上界，分解問題與合併部分解所需的工作量與問題規模 $n$ 成正比，且（b）每個階段有數量有界的 $p$ 個規模約為 $\frac{n}{p}$ 的子問題，則分治演算法的代價為 $O(n\log_{p}n)$。

對於其他類型的分治方法，運行時間亦可加以推廣。例如，設（a）分解問題與合併部分解耗時 $cn$，其中 $n$ 為輸入規模，$c$ 為某常數；（b）當 $n < 2$ 時，演算法耗時有上界 $c$；（c）共有 $q$ 個子問題，每個規模約為 $\frac{n}{2}$，則運行時間如下：

- 若子問題數目 $q > 2$，則分治演算法的運行時間上界為 $O(n^{\log_{2}q})$。
- 若子問題數目恰好為一，則分治演算法的運行時間上界為 $O(n)$。

若分解問題與合併部分解耗時 $cn^2$，且共有2個規模各為 $\frac{n}{2}$ 的子問題，則分治演算法的運行時間上界為 $O(n^2)$。

### 同步性

分治算法天然適合在多處理器機器上執行，尤其是共享記憶體系統——在此類系統中，不同子問題可在不同處理器上執行，處理器之間的數據通信無需提前規劃。

### 記憶體存取

分治算法天然傾向於高效利用記憶體快取。原因在於：一旦子問題規模足夠小，它及其所有子問題原則上均可在快取內求解，而無需訪問較慢的主記憶體。以這種方式設計以利用快取的算法稱為Q5015938，因為它不將快取大小作為顯式參數。此外，分治演算法可被設計為重要演算法（如排序、FFT及矩陣乘法）的最優快取無關演算法——在漸近意義上，無論快取大小如何，均能以可能最優的方式使用快取。相比之下，利用快取的傳統方法是「分塊」（如Q6675847中的做法），即將問題顯式地分割為適當大小的塊——此方法同樣可最優地使用快取，但僅在演算法針對特定機器的快取大小調優時才有效。

同樣的優勢亦存在於其他分層存儲系統中，例如NUMA或虛擬記憶體，以及多級快取：一旦子問題規模足夠小，即可在存儲層次結構的某一層內求解，而無需訪問更高（更慢）的層次。

### 修正控制

在含捨入運算的計算中（例如使用浮點數時），分治演算法可能比表面等價的迭代方法產生更精確的結果。例如，對 N 個數求和，既可用逐一累加的簡單迴圈，也可用稱為Q17104961的分治演算法——將數據集一分為二，遞歸地計算兩半之和，再相加。雖然後者執行的加法次數與前者相同，並需承擔遞歸調用的額外開銷，但通常精度更高。

## 實現

### 循環遞歸

分治算法天然以遞歸過程實現。在此情況下，通往當前求解問題的各部分子問題會自動儲存在過程呼叫堆疊中。遞歸函數是指在其定義中呼叫自身的函數。

在每一層遞歸上都有三個步驟：

- 分解：將原問題分解為若干個規模較小，相對獨立，與原問題形式相同的子問題。
- 解決：若子問題規模較小且易於解決時，則直接解。否則，遞歸地解決各子問題。
- 合併：將各子問題的解合併為原問題的解。

### 顯堆棧

分治演算法亦可以非遞歸程序實現，將各部分子問題儲存在某種顯式數據結構中，如堆疊、佇列或優先佇列。此方法在選擇下一個待求解子問題時提供了更大的自由度，這一特性在某些應用中十分重要——例如廣度優先遞歸和用於函數最優化的分支定界法。對於不支持遞歸過程的程式語言，此方法亦是標準解決方案。

### 堆疊大小

在分治演算法的遞歸實現中，必須確保為遞歸堆疊分配了足夠的記憶體，否則執行可能因堆疊溢位而失敗。高效率的分治演算法通常具有較小的遞歸深度。例如，快速排序算法可以實現為對 $n$ 個元素排序時嵌套遞歸呼叫次數不超過 $\log_2 n$ 次。

使用遞歸過程時，堆疊溢位可能難以預防——許多編譯器將遞歸堆疊視為連續記憶體塊，且有些編譯器會為其預留固定大小的空間。此外，編譯器可能在遞歸堆疊上儲存多於嚴格所需的資訊，包括返回地址、未更改的參數及過程的局部變量。因此，可通過限制遞歸過程中的參數和局部變量數目、或以顯式堆疊數據結構替代遞歸，來降低堆疊溢位的風險。

### 基本情況的選擇

在任何遞歸演算法中，基本情況——即直接求解以終止遞歸的小子問題——的選擇具有相當大的自由度。

選擇盡可能小或盡可能簡單的基本情況更為優雅，且通常帶來更簡潔的程序，因為需要考慮的情況更少、更易求解。例如，快速傅立葉變換演算法可在輸入為單個樣本時停止遞歸，快速排序算法可在輸入為空列表時停止；兩者均只有一個基本情況，且無需任何處理。

另一方面，若在規模相對較大的基本情況處停止遞歸並以非遞歸方式求解，效率往往可以提升，從而形成Q17092099。這一策略避免了幾乎不做任何工作的遞歸呼叫的開銷，也可能允許使用針對這些基本情況比顯式遞歸更高效的專用非遞歸演算法。一種簡單混合遞歸演算法的通用方法是短路基本情況，又稱臂長遞歸：在函數呼叫前先檢查下一步是否會達到基本情況，以避免不必要的函數呼叫。例如，在樹結構中，先檢查子節點是否為空再遞歸，比遞歸至子節點後再檢查是否為空，在某些二叉樹演算法中可減少約一半的函數呼叫。由於分治演算法最終會將每個問題或子問題化為大量基本情況，這些情況通常主導整體演算法的代價，尤其是在分割/合併開銷較低時。注意，這些考量與遞歸是由編譯器實現還是由顯式堆疊實現無關。

因此，許多快速排序庫實現會在待排序元素數目足夠少時，切換至基於簡單迴圈的插入排序（或類似）演算法。值得注意的是，若空列表是唯一的基本情況，對含 $n$ 個元素的列表排序最多需要 $n$ 次僅返回而不做任何工作的快速排序呼叫；將基本情況擴大至規模不超過2的列表，可消除大多數此類空呼叫；更一般地，採用大於2的基本情況規模通常可減少函數呼叫開銷或堆疊操作所佔的時間比例。

另一種方法是採用較大的基本情況，但仍使用分治演算法，並針對一組預定的固定規模將演算法完全展開為不含遞歸、迴圈或條件判斷的代碼（與部分求值技術相關）。例如，某些高效FFT實現採用此方法，其基本情況是針對一組固定規模的分治FFT演算法的展開實現。源碼生成方法可用於高效實現此策略所需的大量獨立基本情況。

此思想的推廣版本稱為遞歸「展開」或「粗化」，已有多種自動化擴大基本情況過程的技術被提出。

### 重疊子問題的動態規劃

對於某些問題，分支遞歸可能會多次求解同一子問題。在此情況下，識別並保存這些重疊子問題的解可能是值得的，這一技術通常稱為記憶化。將此思想推至極限，可引導出自底向上的分治演算法，即動態規劃。

## 示例

分治法在高級語言中主要的一個思想是遞歸，LISP語言中的體現出了極豐富的分治法。

以下是歸併排序C語言的示例代碼，輸入參數中，需要排序的陣列為array,起始索引為first，終止索引為last。調用完成後，array中從first到last處於升序排列。

```c
 void merge_sort(int array[], unsigned int first, unsigned int last)
 {
 	int mid = 0;
 	if(first<last)
 	{
 		mid = (first+last)/2;
 		merge_sort(array, first, mid);
 		merge_sort(array, mid+1,last);
 		merge(array,first,mid,last);
 	}
 }
```

在程式中可以看出分治法的應用：在merge_sort中，將原來針對索引first到last的陣列排序的問題，分為二份較小的問題

- 先針對索引first到mid的陣列排序。
- 再針對索引mid+1到last的陣列排序。

最後再進行二個陣列的合併。