算法设计范式
分治法
分治法是一套三拍子的策略：把问题划分（divide）成同类的更小片段，征服（conquer）每个片段（通常靠递归），再把各片段的答案合并（combine）成整体的答案。其直觉是：一个你一眼看不透的大问题，往往能拆成两半，每一半都只是原问题的缩小版——而一旦两半都解决了，把它们缝起来就很容易。它是递归天生的搭档：「征服」这一步几乎总是对更小输入的一次递归调用，而基准情形就是小到可以直接求解的那一片。
两个经典例子能说明它的形状。归并排序把数组划分成两半，递归地各自排好序，再把两段已排序的部分合并成一个有序的整体——这个合并正是巧妙的「合并」步。二分查找把搜索区间对半划分，扔掉不可能含目标的那一半，对可能含目标的那一半递归；这里根本没有合并步，只有不留情面的对半砍。两者的速度都源自同一处：每一层划分都把工作量砍小，所以层数大约只有 log n。
分治算法的代价由一个递推关系刻画——例如归并排序的 T(n) = 2T(n/2) + O(n)，读作「要排好 n 个元素，先排两半、再花线性时间合并」。主定理几乎一眼就能把这类递推化成 Big-O 答案（归并排序解出来是 O(n log n)）。一句提醒：只有当子问题真的更小、且合并步足够便宜时，划分才有帮助。如果合并和从头解一样昂贵，你就什么也没省下。
void mergeSort(vector<int>& a, int lo, int hi) {
if (lo >= hi) return; // base: 0 or 1 element
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid); // divide + conquer left
mergeSort(a, mid + 1, hi); // divide + conquer right
merge(a, lo, mid, hi); // combine the two sorted halves
}递推 T(n) = 2T(n/2) + O(n) 经主定理给出 O(n log n)。
分治法不同于动态规划。两者都把问题拆成子问题，但经典分治的子问题是相互独立的（归并排序的两半永远不重叠），而动态规划的存在恰恰是为了应对那些会重叠、否则就要被重算的子问题。
又称
另见