目錄

1.定義

2.例子

3.注意

---

1.定義

分治法（Divide and Conquer）是一種解決問題的算法設計策略，它將一個大問題分解成若干個規模較小且結構與原問題相似的子問題，然后遞歸地解決這些子問題，最后將子問題的解合并起來得到原問題的解。

分治法的一般步驟包括：

1. 分解（Divide）：將原問題分解成若干個規模較小的子問題，這些子問題與原問題的結構相同，并且可以相互獨立地解決。

2. 征服（Conquer）：遞歸地解決這些子問題。如果子問題的規模足夠小，可以直接求解而不再進行分解。

3. 合并（Combine）：將子問題的解合并起來，得到原問題的解。

分治法通常適用于以下類型的問題：

1. 可以被分解為若干個相互獨立且結構相似的子問題。
2. 子問題的解可以合并為原問題的解。
3. 遞歸求解子問題的效率高。

分治法在算法設計中有著廣泛的應用，例如快速排序、歸并排序、大整數乘法等問題都可以通過分治法來解決。這種算法設計策略能夠有效地降低問題的復雜度，提高算法的效率。

2.例子

以歸并排序為例。假設實現歸并排序的函數名為?sort。明確該函數的作用，對傳入的一個數組排序。這個問題顯然可以分解：給一個數組分成左右兩個部分，然后對該數組排序即為給該數組的左右兩半分別排序，最后再合并成一個數組。

void sort(一個數組) {if (可以很容易處理的條件) return;sort(左半個數組);sort(右半個數組);merge(左半個數組, 右半個數組);
}

傳給它半個數組，那么處理完后這半個數組就已經被排好了。分治算法的套路是分解 -> 解決（觸底）-> 合并（回溯），先左右分解，再處理合并，回溯就是在退棧，即相當于二叉樹的后序遍歷。merge?函數的實現方式與兩個有序鏈表的合并一致。

3.注意

如果各子問題是不獨立的，則分治法要重復地解公共的子問題，也就做了許多不必要的工作。此時雖然也可用分治法，但一般用?動態規劃?較好。