12.5   小結

• 分治是一種常見的演算法設計策略，包括分（劃分）和治（合併）兩個階段，通常基於遞迴實現。
• 判斷是否是分治演算法問題的依據包括：問題能否分解、子問題是否獨立、子問題能否合併。
• 合併排序是分治策略的典型應用，其遞迴地將陣列劃分為等長的兩個子陣列，直到只剩一個元素時開始逐層合併，從而完成排序。
• 引入分治策略往往可以提升演算法效率。一方面，分治策略減少了操作數量；另一方面，分治後有利於系統的並行最佳化。
• 分治既可以解決許多演算法問題，也廣泛應用於資料結構與演算法設計中，處處可見其身影。
• 相較於暴力搜尋，自適應搜尋效率更高。時間複雜度為 \(O(\log n)\) 的搜尋演算法通常是基於分治策略實現的。
• 二分搜尋是分治策略的另一個典型應用，它不包含將子問題的解進行合併的步驟。我們可以透過遞迴分治實現二分搜尋。
• 在構建二元樹的問題中，構建樹（原問題）可以劃分為構建左子樹和右子樹（子問題），這可以透過劃分前序走訪和中序走訪的索引區間來實現。
• 在河內塔問題中，一個規模為 \(n\) 的問題可以劃分為兩個規模為 \(n-1\) 的子問題和一個規模為 \(1\) 的子問題。按順序解決這三個子問題後，原問題隨之得到解決。