第二章：分治
- 2020 年 11 月 24 日
- 筆記
- 算法设计与分析MOOC（北航）
2.1归并排序
问题特点：局部有序
快速合并：比较两有序数组当前最小元素，将较小者逐一合入新数组
输入规模越大，两两合并更有效。
但是数组可能没有局部有序特性，需要进行构建：两两合并
这个方法的本质就是归并排序算法。
归：递归
并：合并
2.2递归式求解
（1）递归树法：直观，不好求
（2）代入法：猜测，用数学归纳法证明。好求，不好猜
（3）主定理法：
2.3最大子数组问题
QNews
2.1归并排序
问题特点：局部有序
快速合并：比较两有序数组当前最小元素，将较小者逐一合入新数组
输入规模越大，两两合并更有效。
但是数组可能没有局部有序特性，需要进行构建：两两合并
这个方法的本质就是归并排序算法。
归：递归
并：合并
2.2递归式求解
（1）递归树法：直观，不好求
（2）代入法：猜测，用数学归纳法证明。好求，不好猜
（3）主定理法：
2.3最大子数组问题