什麼是分治算法？¶
在我們生活中，常常會遇到複雜的問題，直接解決可能很困難。這時候，“分而治之”的思想就派上用場了——把大問題拆成小問題，解決小問題後再合併成大問題的答案。這種思想就是分治算法的核心。
簡單來說，分治算法就是通過“分解（Divide）、解決（Conquer）、合併（Combine）”三個步驟解決問題：
1. 分解：把原問題拆成多個規模較小、結構相同的子問題。
2. 解決：遞歸地解決每個子問題。如果子問題足夠小（比如只剩一個元素），就直接計算結果。
3. 合併：把所有子問題的解合併成原問題的解。
爲什麼要用分治算法？¶
舉個例子：你有一個裝滿蘋果的大箱子，要數總共有多少個。直接數可能麻煩，分治的思路是：把箱子裏的蘋果分成兩堆，分別數出每堆的數量，再把兩堆數量相加。這樣，原本複雜的“數總數”就變成了“數兩堆小數”的簡單問題。
分治算法的優勢在於：將複雜問題簡化爲可遞歸解決的子問題，尤其適合處理遞歸結構的問題（比如數組、樹、圖等）。
分治算法的步驟拆解¶
以計算數組總和爲例，分治的具體步驟如下：
1. 分解：將數組從中間分成左右兩部分（比如數組 [a1, a2, ..., an] 分成 [a1, ..., am] 和 [am+1, ..., an]）。
2. 解決：遞歸計算左右兩部分的和（如果數組只剩一個元素，直接返回該元素）。
3. 合併：把左右兩部分的和相加，得到原數組的總和。
這個過程中，遞歸是關鍵——子問題的解決依賴於更小的子問題，直到子問題足夠簡單。
歸併排序：分治的典型應用¶
歸併排序是分治算法最經典的應用之一，它的核心是先排序子數組，再合併有序數組。我們用一個簡單例子來理解它的過程：
例子：排序數組 [3, 1, 4, 2]
-
分解：把數組從中間分成兩半：
[3, 1]和[4, 2]。繼續分解，直到每個子數組只剩一個元素：[3]、[1]、[4]、[2]。 -
解決：單個元素本身就是有序的，所以此時子數組已經有序。
-
合併：從最小的子數組開始合併，逐步向上。
- 合併[3]和[1]：比較兩個元素，小的在前，得到[1, 3]。
- 合併[4]和[2]：比較後得到[2, 4]。
- 合併[1, 3]和[2, 4]：用兩個指針遍歷兩個有序數組，依次取較小的元素。最終合併爲[1, 2, 3, 4]。
歸併排序的關鍵：合併有序數組¶
合併步驟是歸併排序的核心，需要用雙指針法實現：
- 準備兩個指針 i 和 j，分別指向兩個有序子數組的開頭。
- 比較 i 和 j 指向的元素，取較小的元素放入臨時數組，並移動對應指針。
- 當一個子數組遍歷完畢，將另一個子數組的剩餘元素直接放入臨時數組。
例如，合併 [1, 3] 和 [2, 4]：
- i=0（指向1），j=0（指向2）→ 取1，i=1。
- i=1（指向3），j=0（指向2）→ 取2，j=1。
- i=1（指向3），j=1（指向4）→ 取3，i=2（子數組1遍歷完畢）。
- 將子數組2的剩餘元素（4）放入，得到 [1, 2, 3, 4]。
歸併排序的時間複雜度¶
歸併排序的時間複雜度是 O(n log n)：
- 分解：每次將數組分成兩半，遞歸深度爲 log n（類似二分查找）。
- 合併：每一層的合併操作需要遍歷所有元素，總共有 n 個元素，所以每一層時間爲 O(n)。
- 總時間：O(n) * O(log n) = O(n log n)。
空間複雜度爲 O(n)，因爲合併過程需要額外的臨時數組存儲中間結果。
總結¶
分治算法的核心是“分而治之”，通過分解、解決、合併三個步驟，將複雜問題轉化爲簡單子問題的遞歸求解。歸併排序作爲分治的典型案例，通過“先分後合”的方式實現高效排序，其 O(n log n) 的時間複雜度使其在大數據量排序中表現優異。
如果你理解了分治的思想，就能更好地掌握遞歸、排序、查找等算法的設計思路，爲後續學習更復雜的算法打下基礎。