求解递推关系有许多方法，这里我们简要考虑三种。
第一种是估计技巧：
猜测递推关系的上下界，用
归纳法证明这些界，并按需要收紧。
第二种方法是展开递推，把它转化成
求和，然后使用求和技巧。
第三种方法是在递推具有合适形式时，利用
已被证明的定理。
特别是，像归并排序这样典型的分治算法
产生的递推符合一种模式，对这种模式我们
有现成的解。
5.1.1. 估计上下界
求解递推的第一种方法是猜测
答案，然后尝试证明它正确。
如果给出了正确的上下界估计，
一个简单的归纳证明就会验证这个事实。
如果证明成功，那么尝试收紧界。
如果归纳证明失败，那么放宽界再试一次。
一旦上下界相符，你就完成了。
当你只寻求渐近复杂度时，
这是一种有用的技巧。
当你寻求精确的闭式解（也就是说，你寻求表达式中的
常数）时，这种方法可能工作量太大。
5.1.2. 展开递推
如果你只需要答案的近似值，估计界是有效的。
要找到精确解则需要更精确的技巧。
一种方法被称为 展开递推。
在这种方法中，方程右边较小的项
依次被它们的定义替换。
这就是展开步骤。
这些项再次被展开，依此类推，直到得到一个
不再含递推的完整级数。
这产生一个
求和
，然后就可以使用求解求和的方法。
5.1.3. 分治递推
求解递推的第三种方法是利用
已知定理，这些定理为一类递推提供解。
特别有实际用途的是一个给出
分治递推 类答案的定理。
它们的形式为
\[{\bf T}(n) = a{\bf T}(n/b) + cn^k; \quad {\bf T}(1) = c\]
其中 \(a\)、\(b\)、\(c\) 和 \(k\) 是常数。
一般来说，这个递推描述一个规模为 \(n\) 的问题
被划分成 \(a\) 个规模为 \(n/b\) 的子问题，
而 \(cn^k\) 是组合
部分解所需的工作量。
归并排序是分治算法的一个例子，其递推
符合这种形式。
二分查找也是。
我们用展开递推的方法，假设 \(n = b^m\)，
为任何分治递推推导出一般解。
\[\begin{split}\begin{eqnarray*}
{\bf T}(n) & = & a{\bf T}(n/b) + cn^k\\
& = & a(a{\bf T}(n/b^2) + c(n/b)^k) + cn^k\\
& = & a(a[a{\bf T}(n/b^3) + c(n/b^2)^k] + c(n/b)^k) + cn^k\\
& = & a^m{\bf T}(1) + a^{m-1}c(n/b^{m-1})^k + \cdots + ac(n/b)^k + cn^k\\
& = & a^mc + a^{m-1}c(n/b^{m-1})^k + \cdots + ac(n/b)^k + cn^k\\
& = & c\sum_{i=0}^{m} a^{m-i} b^{ik}\\
& = &ca^m\sum_{i=0}^{m} (b^k/a)^i.
\end{eqnarray*}\end{split}\]
下面是此同一推导的更直观的呈现。
所以，我们得到这样的结果：
\[{\bf T}(n) = ca^m\sum_{i=0}^{m} (b^k/a)^i.\]
在这一点上，注意到这一点是有用的：
\[\begin{eqnarray}
\label{ThmEquiv}
a^m = a^{\log_bn} = n^{\log_ba}.
\end{eqnarray}\]
这给出
\[{\bf T}(n) = c n^{\log_ba} \sum_{i=0}^{m} (b^k/a)^i.\]
这个方程的求和部分是一个等比数列，其和
取决于比值 \(r = b^k/a\)。
有三种情形。
\(r<1\)。
由模块
求和
的方程 (4) 有
\[\sum_{i=0}^{m} r^i < 1/(1-r),\ {\rm a~constant.}\]
因此，
\[{\bf T}(n) = \Theta(a^m) = \Theta(n^{log_ba}).\]
\(r=1\)。
因为 \(r = b^k/a\)，我们知道 \(a = b^k\)。
由对数的定义立刻可以推出
\(k = \log_b a\)。
还要注意，既然我们定义了 \(n = b^m\)，
那么 \(m = \log_b n\)。
因此，
\[\sum_{i=0}^{m} r^i = m + 1 = \log_bn + 1.\]
因为 \(a^m = n^{\log_b a} = n^k\)，我们有
\[{\bf T}(n) = \Theta(n^{\log_ba}\log_b n) = \Theta(n^k\log_b n).\]
\(r>1\)。
由模块
求和
的方程 (5) 有
\[\sum_{i=0}^{m} r^i = \frac{r^{m+1} - 1}{r - 1} = \Theta(r^m).\]
因此，
\[{\bf T}(n) = \Theta(a^mr^m)
= \Theta(a^m(b^k/a)^m)
= \Theta(b^{km})
= \Theta(n^k).\]
我们可以把上述推导总结为下面的定理，
有时被称为 主定理。
只要适用，就可以直接应用这个定理，而不必
重新推导递推的解。
5.1.4. 快速排序的平均情况分析
在模块
快速排序
中，我们确定快速排序的平均情况分析具有下面的递推：
\[{\bf T}(n) = cn + \frac{1}{n}\sum_{k=0}^{n-1} [{\bf T}(k) +
{\bf T}(n -1 - k)], \qquad {\bf T}(0) = {\bf T}(1) = c.\]
\(cn\) 项是 findpivot 和
partition 步骤的一个上界。
这个方程源于假设分区元素
出现在任何位置 \(k\) 的可能性相等。
通过观察两个递推项 \({\bf T}(k)\) 和 \({\bf T}(n - 1 - k)\)
是等价的，可以简化它，因为一个只是从 \(T(0)\) 往上数到
\(T(n-1)\)，另一个从 \(T(n-1)\) 往下数到
\(T(0)\)。
这给出
\[{\bf T}(n) = cn + \frac{2}{n}\sum_{k=0}^{n-1} {\bf T}(k).\]
这种形式被称为 全历史递推。
求解这种递推的关键是消去求和
项。
求和的平移法提供了一种办法。
两边乘以 \(n\)，并从
\(n{\bf T}(n+1)\) 的公式中减去结果：
\[\begin{split}\begin{eqnarray*}
n{\bf T}(n) & = & cn^2 + 2 \sum_{k=1}^{n-1} {\bf T}(k)\\
(n+1){\bf T}(n+1) & = & c(n+1)^2 + 2 \sum_{k=1}^{n} {\bf T}(k).
\end{eqnarray*}\end{split}\]
两边减去 \(n{\bf T}(n)\) 得到：
\[\begin{split}\begin{eqnarray*}
(n+1){\bf T}(n+1) - n{\bf T}(n) & = & c(n+1)^2 - cn^2 + 2{\bf T}(n)\\
(n+1){\bf T}(n+1) - n{\bf T}(n) & = & c(2n+1) + 2{\bf T}(n)\\
(n+1){\bf T}(n+1) & = & c(2n+1) + (n+2){\bf T}(n)\\
{\bf T}(n+1) & = & \frac{c(2n+1)}{n+1} + \frac{n+2}{n+1}{\bf T}(n).
\end{eqnarray*}\end{split}\]
在这一点上，我们已经消除了求和，现在可以
用我们求解递推的常规方法得到闭式
解。
注意 \(\frac{c(2n+1)}{n+1} < 2c\)，所以我们可以简化
结果。
展开递推，我们得到
\[\begin{split}\begin{eqnarray*}
{\bf T}(n+1) & \leq & 2c + \frac{n+2}{n+1} {\bf T}(n)\\
& = & 2c + \frac{n+2}{n+1}\left (2c +
\frac{n+1}{n}{\bf T}(n-1)\right )\\
& = & 2c + \frac{n+2}{n+1}\left (2c + \frac{n+1}{n}\left
(2c + \frac{n}{n-1}{\bf T}(n-2)\right )\right )\\
& = & 2c + \frac{n+2}{n+1}\left (2c + \cdots +
\frac{4}{3}(2c + \frac{3}{2}{\bf T}(1))\right )\\
& = & 2c\left (1 + \frac{n+2}{n+1}
+ \frac{n+2}{n+1}\frac{n+1}{n} + \cdots
+ \frac{n+2}{n+1}\frac{n+1}{n}\cdots\frac{3}{2}\right )\\
& = & 2c\left (1 + (n+2)\left (\frac{1}{n+1}
+ \frac{1}{n} + \cdots + \frac{1}{2}\right )\right )\\
& = & 2c + 2c(n+2)\left ({\cal H}_{n+1} - 1\right )\\
\end{eqnarray*}\end{split}\]
其中 \({\cal H}_{n+1}\) 是调和级数。
由模块
求和
的方程 (10)，
\({\cal H}_{n+1} = \Theta(\log n)\)，
所以最终解是 \(\Theta(n \log n)\)。
