分治法

分治法先说明怎样把原问题化为同类较小问题，再递归处理它们，最后把子答案接成完整答案。长度很小的基本情形直接处理，为递归提供终止点；若每次都没有缩小问题，写成递归也不能使计算前进。

归并排序是清楚的例子：先将数组分成两半，分别排好，再用线性扫描合并。子调用只承诺自己的区域有序，合并步骤负责把这份局部保证扩展到整个区域；正确性因而同时需要子问题和组合规则。

参考：[1]

若每次分成两个等大部分，组合工作与当前长度成正比，归并排序得到T(n)=2T(n/2)+O(n)一类递推。在单位比较模型下，每层总工作为O(n)，对数级层数累积为O(n log n)，而不是把每条递归分支各算成一次完整排序。

快速排序也递归处理划分两侧，但子问题大小由枢轴划分结果决定。极不均衡时，递推会与均分情形不同。分治法并不自带对数层数；应分析实际划分规则，而不是只观察代码包含两次递归调用。

参考：[1] [2]

子问题若相互独立，分治可把各自求解过程清楚分开；若不同分支不断产生同一个状态，独立展开就会浪费工作。直接递归求斐波那契数会反复求相同下标，动态规划则用结果复用改变这一成本结构。

拆分、复制和组合也都要计入资源。数组归并需要辅助存储，递归执行需要保存调用状态；任务能够分别描述，并不代表并行运行时没有通信与调度开销。方法提供组织问题的结构，具体收益仍由完整成本模型决定。

参考：[3] [1]