# 分治算法 > 原文： [https://www.programiz.com/dsa/divide-and-conquer](https://www.programiz.com/dsa/divide-and-conquer) #### 在本教程中，您將學習分治算法的工作原理。 此外，您將發現分治方法與其他解決遞歸問題的方法之間的比較。 **分治算法**是一種通過以下方法解決較大問題的策略 1. 將問題分解為較小的子問題 2. 解決子問題，以及 3. 合并它們以獲得所需的輸出。 要使用分治算法，請使用**遞歸**。 了解不同編程語言中的遞歸： * [Java 中的遞歸](https://www.programiz.com/java-programming/recursion) * [Python 中的遞歸](https://www.programiz.com/python-programming/recursion) * [C++ 中的遞歸](https://www.programiz.com/cpp-programming/recursion) * * * ## 分治算法如何工作？ 涉及的步驟如下： 1. **劃分**：使用遞歸將給定問題劃分為子問題。 2. **解決**：遞歸解決較小的子問題。 如果子問題足夠小，則直接解決。 3. **組合**：組合子問題的解決方案，這是遞歸過程的一部分，以獲取實際問題的解決方案。 讓我們借助示例來理解這個概念。 在這里，我們將使用分治的方法對數組進行排序（即[歸并排序](https://www.programiz.com/dsa/merge-sort)）。 1. 假設給定數組為：  歸并排序數組 2. **將數組分為兩半。**  將數組分為兩個子部分。 再次將每個子部分遞歸地分為兩半，直到得到單個元素。  將數組分成較小的子部分 3. 現在，以排序的方式組合各個元素。 在這里，**解決**和**組合**步驟并排進行。  合并子部分 * * * ## 復雜度 分治法的復雜度是使用[主定理](https://www.programiz.com/dsa/master-theorem)計算的。 ``` T(n) = aT(n/b) + f(n), where, n = size of input a = number of subproblems in the recursion n/b = size of each subproblem. All subproblems are assumed to have the same size. f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions ``` 讓我們舉一個例子來發現遞歸問題的時間復雜度。 對于歸并排序，等式可以寫成： ``` T(n) = aT(n/b) + f(n) = 2T(n/2) + O(n) Where, a = 2 (each time, a problem is divided into 2 subproblems) n/b = n/2 (size of each sub problem is half of the input) f(n) = time taken to divide the problem and merging the subproblems T(n/2) = O(n log n) (To understand this, please refer to the master theorem.) Now, T(n) = 2T(n log n) + O(n) ≈ O(n log n) ``` * * * ## 分治 vs 動態方法 分治的方法將問題分為較小的子問題，這些子問題可以遞歸進一步解決。 每個子問題的結果都不存儲以供將來參考，而在動態方法中，每個子問題的結果均存儲以供將來參考。 當同一子問題無法多次解決時，請使用分治的方法。 當將來要多次使用子問題的結果時，請使用動態方法。 讓我們通過一個例子來理解這一點。 假設我們試圖找到斐波那契數列。 然后， **分治的方法**： ``` fib(n) If n < 2, return 1 Else , return f(n - 1) + f(n -2) ``` **動態方法**： ``` mem = [ ] fib(n) If n in mem: return mem[n] else, If n < 2, f = 1 else , f = f(n - 1) + f(n -2) mem[n] = f return f ``` 在動態方法中，`mem`存儲每個子問題的結果。 * * * ## 分治算法的優勢 * 使用樸素方法將兩個矩陣相乘的復雜度為`O(n^3)`，而使用分治法（即 Strassen 矩陣乘法）的復雜度為`O(n^2.8074)`。 這種方法還簡化了諸如河內塔之類的其他問題。 * 這種方法適用于多處理系統。 * 它有效地利用了內存緩存。 * * * ## 分治法 * [二分搜索](https://www.programiz.com/dsa/binary-search) * [歸并排序](https://www.programiz.com/dsa/merge-sort) * [快速排序](https://www.programiz.com/dsa/quick-sort) * Strassen 的矩陣乘法 * 唐津算法