分治法
分治法是种经典的算法设计策略，这种策略简单来说就是先把原问题分成规模更小的子问题，再把子问题划分成更小的子问题…一直划分到子问题十分容易解决，然后就能倒过来解决原问题。数学中数列项的递推式就能看做是基于分治策略的算法，数学中的递推式很多时候都比通项式更容易找到和理解，分治算法相对于一些其他的算法很多时候也是这样。虽然分治策略本身不限定算法的物理实现形式，但通常默认分治算法是递归函数程序。
由于分支策略只是一个大的设计框架，所以不同问题的分治算法间的区别可以很大，且同一问题也可能有多种分治算法。但所有分治算法都是遵循如下3大步骤的(或者说能按这几大步骤设计)：
1) 分解子问题：需要拆分出几个子问题，这些子问题的输入应该怎么求得；
2) 解决子问题：解决上述这些子问题，并得到子问题的解；
3) 合并子问题：整理上述这些子问题的解，从而得到原问题的解；
存在分治算法的问题需要满足如下条件：
1) 问题(或是“变形”后的问题)的解能通过形式相同、规模更小的若干子问题的解得到；
2) 子问题小到一定规模后，能很容易得到其解；
上述(1)是最关键的，一般称满足(1)的问题具有最优子结构性质。比如求第\(i\)个斐波那契数\(Fib(i)\)的分治算法，斐波那契数的定义直接给出了最优子结构，而\(Fib(0),Fib(1)\)也直接由定义给出，满足上述(2)。
主定理(Master Theorem)
对于简单的递归程序，可以像分析迭代程序一样，直接得出时间复杂度。但一般的递归程序由于存在递推关系所以不好直接分析，需要求解“递归函数的代价=所有子递归的代价+子递归外其他操作的代价”形式的递推方程。Jon Bentlery，Dorothea Haken和James B. Saxe在1980年提出主定理，可看作是一类时间复杂度递推方程的“通解”，其内容如下：
a) 主定理：设\(T(n) = aT(\frac{n}{b}) + f(n)\)是递推方程，\(a \geq 1, b > 0\)为常数，\(f\)是未知正函数，\(T\)的定义域是非负整数。这里\(T(\frac{n}{b})\)是个省略写法，表示\(\frac{n}{b}\)在任何时候取\(\lceil \frac{n}{b} \rceil\)或\(\lfloor \frac{n}{b} \rfloor\)都不影响结论。下面是3类\(f(n)\)下\(T\)的渐进解：
a.1) \(f(n)=O(n^{\log_b{(a – \varepsilon)}})\)，其中常数\(\varepsilon>0\)。解为\(\Theta(n^{\log_b{a}})\)；
a.2) \(f(n)=\Theta(n^{\log_b{a}})\)。解为\(\Theta(n^{\log_b{a}} \cdot \lg{n})\)；
a.3) \(f(n)=\Omega(n^{\log_b{(a + \varepsilon)}})\)，其中常数\(\varepsilon>0\)，且存在常数\(c\leq 1\)使\(n\)足够大时\(af(\frac{n}{b})\leq cf(n)\)。解为\(\Theta(f(n))\)；
将主定理用于求递归函数时间复杂度时，\(T(n)\)表示问题规模\(n\)时的时间复杂度，\(a\)表示子递归的数目，\(\frac{n}{b}\)表示每个子问题的规模(也就是所有子问题规模要相同，最多只能有上下取整差异)。\(f(n)\)则表示除子递归外，其他所有操作的代价。
需注意上面根据\(f(n)\)的3个范围分别进行了讨论，但这种划分是有“空隙”的，存在不属于上述3个范围的情况，比如当\(f(n)\)是\(\Theta(n\lg{n})\)，\(a=b=2\)时。求导数可知\(n\lg{n}\)的增长速度快于\(n\)，但慢于任何\(n\)的大于1次幂。这种情况会导致其刚好卡在(a.2)和(a.3)的“空隙”之间，无法用主定理求解。由于\(f(n)\)为\(\Theta(n\lg{n})\)的程序很常见，给出对这种情况的补充：
b) 若\(f(n)=\Theta(n^{\log_b{a}}\cdot\lg^k(n))\)，其中\(k\)非负，\(T(n)=\Theta(n^{\log_b{a}}\cdot\lg^{k+1}(n))\)；