附录：主定理
对于 `T(n) = aT(n/b) + f(n)`：
CASE 1：`f(n) = \O(n^(log_ba-\epsilon))`，常数 `\epsilon > 0`，`T(n) = \Theta(n^(log_ba))`。
CASE 2：`f(n) = \Theta(n^(log_ba)\lg^kn)`，常数 `k \geq 0`，`T(n) = \Theta(n^(log_ba)\lg^(k+1)n)`。
CASE 3：`f(n) = \Omega(n^(log_ba+\epsilon))`，常数 `\epsilon > 0`，`T(n) = \Theta(f(n))`。
在上一文中我们花费了大量的篇幅用于描述分析算法时所需用到的数学工具。在这篇文章中，我们将逐步探索如何设计算法，即从 算法分析 到 算法设计 的过程。今天我们关注的是 分治法。
首先我们给出分治法的设计范式 (Design Paradigm)，然后我们结合具体的算法来对这个设计范式做更深入的理解。
具体来说，分治法的设计思路可以分为三步：
1. 分解 (Divide)：将问题分解为子问题
2. “治” (Conquer)：递归地解决每一个子问题
3. 合并 (Combine)：将子问题的解合并
首先我们回顾一下我们在第一篇文章已经阐述过的归并排序的步骤：
1. 分解 (Divide)：将数组拆分为两个部分
2. “治” (Conquer)：递归地将两个子数组进行排序
3. 合并 (Combine)：合并两个排序数组（线性时间）
我们可以得出归并排序的时间复杂度为：