第二章：分治
- 2020 年 11 月 24 日
- 筆記
- 算法設計與分析MOOC（北航）
2.1歸併排序
問題特點：局部有序
快速合併：比較兩有序數組當前最小元素，將較小者逐一合入新數組
輸入規模越大，兩兩合併更有效。
但是數組可能沒有局部有序特性，需要進行構建：兩兩合併
這個方法的本質就是歸併排序算法。
歸：遞歸
並：合併
2.2遞歸式求解
（1）遞歸樹法：直觀，不好求
（2）代入法：猜測，用數學歸納法證明。好求，不好猜
（3）主定理法：
2.3最大子數組問題
QNews
2.1歸併排序
問題特點：局部有序
快速合併：比較兩有序數組當前最小元素，將較小者逐一合入新數組
輸入規模越大，兩兩合併更有效。
但是數組可能沒有局部有序特性，需要進行構建：兩兩合併
這個方法的本質就是歸併排序算法。
歸：遞歸
並：合併
2.2遞歸式求解
（1）遞歸樹法：直觀，不好求
（2）代入法：猜測，用數學歸納法證明。好求，不好猜
（3）主定理法：
2.3最大子數組問題