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