分而治之

凡治众如治寡，分数是也。

解决规模庞大的问题的有效方法之一，就是将其分解为若干规模更小的子问题，再通过递归机制分别求解。这种分解持续进行，直到子问题规模缩减至平凡情况。这也就是所谓的分而治之（divide-and-conquer）策略。

与减而治之策略一样，这样也要求对原问题重新表述，以保证子问题与原问题在接口形式上的一致。由于将问题分解为若干个子问题，故每一递归实例都可能做多次递归，故称作多路递归（multi-way recursion）。通常会将问题一分为二，故称作二分递归（binary recursion）。

需要强调的是，无论是分解为两个还是更大常数个子问题，对算法总体渐进复杂度并无实质影响。

案例1：数组求和之二分版本

算法思路：
以居中的元素将数组一分为二，递归地对子数组分别求和，最后子数组之和相加即为原数组总和。

算法实现：

int sum(int *A, int lo, int hi)
{
    if(lo == hi)
        return A[lo];
    
    int mi = (lo + hi) >> 1;
    return sum(A, lo, mi) + sum(A, mi + 1, hi);
}

算法分析：

1. 时间复杂度：
   与线性递归版本一样，此处每一递归实例中的非递归计算都只需要常数时间，递归实例共计2n - 1个。故二分版本时间复杂度为O(n)，与线性递归版本相同。
2. 空间复杂度：
   到达递归基时，此时占用的空间最大（因为之后便会递归返回数据，并退栈）。因此任一时刻的活跃递归实例总数都不会超过logn + 1。鉴于每个递归实例仅需常数空间，故算法空间复杂度为O(logn)，相对线性递归版本的O(n)，有了很大改进。

但并非所有问题都适宜采用分治策略！实际上除了递归，此类算法的计算消耗主要来自两个方面。首先是子问题划分，即把原问题分解为形式相同、规模更小的多个子问题，比如数组求和二分版本将数组分为前、后两段。其次是子解答合并，即由递归所得子问题的解，得到原问题整体的解，比如由子数组之和累加得到整个数组之和。

为使分治策略真正有效，不仅必须保证以上两方面的计算都能高效地实现，还必须保证子问题之间相互独立（各个子问题可独立求解，而无需借助其它子问题的原始数据或中间结果。）。否则，或者子问题之间必须传递数据，或者子问题之间需要相互调用，无论如何都会导致时间和空间复杂度的无谓增加。以下就以Fibonacci数列的计算为例说明这一点。

案例2：Fibonacci数

fib(n) = n < 2 ? n : fib(n - 1) + fib (n - 2)

1、Fibonacci数之二分递归

算法实现：

int fib(int n)
{
    if(n <= 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

算法分析：
二分递归版本的子问题f(n - 1) 与 fib(n - 2) 实际上并非彼此独立。

1. 时间复杂度：
   二分版本的时间复杂度高达O(2^n)，究其原因在于，计算过程中所出现的递归实例的重复度极高。
2. 空间复杂度：
   O(logn)