在分支策略中，我们递归地求解一个问题，在每层递归中应用入下三个步骤：

• 分解步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
• 解决步骤递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解。
• 合并步骤将子问题的解组合成原问题的解。

当子问题足够大，需要递归求解时，我们称之为递归情况。当子问题变得足够小，不再需要递归时，我们说递归已经“触底”，进入了基本情况。

求解可得T(n)=Θ(n lg n)。

本章介绍了三种求解递归式的方法，即得出算法的“Θ”或“O”渐近界的方法：

• 代入法 我们猜测一个界，然后用数学归纳法证明这个界是正确的。

• 递归树法 将递归式转换为一棵树，其节点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。

• 主方法 可求解形如下面公式的递归式的界：
  

  其中a≥1，b＞1，f(n)是一个给定的函数。它刻画了这样一个分治算法：生成a个子问题，每个子问题的规模是原问题规模的1/b，分解和合并步骤总共花费时间为f(n)。

最大子数组问题

我们很容易想到一个运行时间为Θ(n²)的算法，但是有没有更高效的方法呢？

使用分治策略的求解方法

假定我们要寻找子数组A[low..high]的最大子数组，使用分治技术意味着我们需要思考能否在更小规模的子数组上寻找最大子数组、能否通过合并这些子问题的解来得到我们想要的解。那么我们很容易就会想到，把A[low..high]均分为两个子数组A[low..mid]和A[mid+1..high]，然后求出这两个子数组中的最大子数组。是不是其中最大的那个，就是原数组A[low..high]的最大子数组呢？显然，我们漏掉了一种情况，就是A[low..high]的最大子数组可能恰好跨越了中点mid。所以现在我们清楚了，A[low..high]的任何连续子数组A[i..j]所处的位置必然是以下三种情况之一：

• 完全位于子数组A[low..mid]中
• 完全位于子数组A[mid+1..high]中
• 跨越中点

我们可以很容易地在线性时间（Θ(n)）内求出跨越中点的最大子数组：任何跨越中点的子数组都由两个子数组A[i..mid]和A[mid+1..j]组成，因此我们只需要找出形如A[i..mid]和A[mid+1..j]的最大子数组然后将其合并即可。

所以我们可以这样描述完整的算法：若数组规模为1，则最大子数组就是子数组本身，否则将数组一分为二，分别在两个子数组上调用此算法，得到两个子数组的最大子数组，再将其中更大的结果与跨越中点的最大子数组进行比较，得到最终的结果。

分治算法的分析

我们很容易就能得到这个算法运行时间T(n)的递归式：