分治法

分治法
算法范式、​解决问题的方式
上级分类	算法、​递归

在计算机科学中，分治法（英語：Divide and conquer）是建基於多項分支遞歸的一种很重要的算法範式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序）、大數乘法（Karatsuba算法）、最近點對搜尋、語法解析（如由上而下解析器）、SAT求解，以及离散傅里叶变换（FFT）。

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

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

分而治之

對列表（38, 27, 43, 3, 9, 82, 10）進行升序排列的分治法示意圖。上半部分：拆分為子列表；中部：單元素列表已為有序；下半部分：合併已排序的子列表。

分治法程式設計範式常用於求解問題的最優解。其基本思想是：將一個給定問題分解為兩個或多個更簡單的相似子問題，依次求解，再組合各子問題的解以解決原問題；足夠簡單的問題則直接求解。例如，對 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})$。

同步性

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

記憶體存取

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

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

修正控制

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

实现

循环递归

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

在每一层递归上都有三个步骤：

1. 分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
2. 解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
3. 合并：将各子问题的解合并为原问题的解。

显堆栈

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

堆疊大小

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

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

基本情況的選擇

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

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

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

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

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

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

重疊子問題的動態規劃

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

示例

分治法在高级语言中主要的一个思想是递归，LISP语言中的体现出了极丰富的分治法。

以下是归并排序C语言的示例代码，输入参数中，需要排序的数组为array[],起始索引为first，终止索引为last。调用完成后，array[]中从first到last处于升序排列。

 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的數組排序。

最後再進行二個數組的合併。

参见

• 主定理
• 數學歸納法
• MapReduce
• 启发式算法