解决算法分析中递归问题的方法

六月 21, 2006

当一个算法(如二分查找)中包含对自己的递归调用时，关于这个算法时间复杂性的分析最终都转化为一个递归方程的求解问题，而这样的算法不在少数。实际上这是数学领域的问题，但是计算机科学又怎么能脱离数学而存在呢？^_^ 数学是好东西呀，可惜自己在这方面造诣颇浅，今生之遗憾亚。^_^

还好，解决递归方程涉及的数学知识我还是能应付的了的^_^。在MIT算法导论中介绍了3种方法，我们这里就说说这三种方法！这些是基础，如果以后要深入研究算法的话，这些知识是必须要精通的；如果并不想在算法方面有所深入的话，多学些知识也没错。我本身也是在学习，像这类的知识一般都比较死性，有些记住了，就可以掌握了。

1、Substitution Method
这是一种使用数学归纳法推导证明的方法，其步骤为先假设一个解，然后带入到递归方程中，利用数学归纳法推导，以验证假设的解是否合理。我们拿ITA(Introduction to Algorithm)中的例子说明吧，比较保险^_^。
[Ex1.]
T(n) = 4T(n/2) + n，解这个递归等式，分析T(n)的渐近性。

解：(这里我们只来找上界)
我们假设T(1) = θ(1)，猜测一个解T(n) = O(n^3)，根据O符号的定义，我们得到对k < n, 有T(k) <= ck^3，把这个解代入到T(n) = 4T(n/2) + n，并进行推导得出：
T(n) = 4T(n/2) + n
     <= 4c((n/2)^3) + n
     = (c/2)n^3 + n
     = cn^3 – ((c/2)n^3 – n)
当c >= 2, n >= 1时，((c/2)n^3 – n) >= 0，这时T(n) <= cn^3，即T(n) = O(n^3)；

我们再回过头来看看当n = 1时这个解是否成立，即证明一下T(1) = θ(1)。对于1 <= n < n0, θ(1) <= cn^3 (c足够大)，即该推导出的解也满足初始条件，所以O(n^3)是T(n)的一个上界。但是O(n^3)是否是严紧的上界呢，我们不妨缩小上界范围再推导一次，这次我们猜测解为T(n) = O(n^2)，根据O符号的定义，我们得到对k < n, 有T(k) <= ck^2，把这个解代入到T(n) = 4T(n/2) + n，并进行推导得出：
T(n) = 4T(n/2) + n
     <= 4c((n/2)^2) + n
     = cn^2 + n
     = cn^2 – (-n)
不能严格符合T(n) <= cn^2的定义，所以推导失败。但是失败是不是说明，T(n) = O(n^2)一定不成立呢？我们再做一次最后的努力，当出现上面的这种情况时，我们假设解仍为：T(n) = O(n^2)，只是我们选择对k < n, 有T(k) <= ak^2 – bk，我们选择减去一个低阶的项，这不会影响到n足够大时的渐进性的，这里是一个常用的技巧。
T(n) = 4T(n/2) + n
     <= 4(a(n/2)^2 – b(n/2)) + n
     = an^2 – bn – (bn – n)
     <= an^2 – bn (当b >= 1时)

这样我们找到了严紧解T(n) = O(n^2)。

2、Iteration method(Recursion-tree method)
这个方法的思想是："迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计"。而我们可以借助’树’的形式来帮助迭代展开的过程。

[Ex2.]
T(n) = T(n/4) + T(n/2)+ n^2；解这个递归等式，分析T(n)的渐近性。

解：
T(n) = n^2 + T(n/4) + T(n/2)
     = n^2 + {(n/4)^2 + T(n/16) + T(n/8)} + {(n/2)^2 + T(n/8) + T(n/4)}
     = …
     = n^2 {1 + 5/16 + (5/16)^2 + (5/16)^3 + … }
     = θ(n^2)

3、Master Method
这是一种典型的套用公式的方法，解决形如’T(n) = aT(n/b) + f(n)’递归方程形的解的方法。这种递归方程是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程’T(n) = aT(n/b) + f(n)’。

在f(n)的三类情况下，我们有T(n)的渐近估计式有三类情况：(log(b, a)表示以b为底的对数)
(1) 若对于某常数ε>0，有f(n) = O(n^log(b, a-ε))，即f(n)以慢于n^(log(b, a))的速率渐进增长，则T(n) = θ(n^(log(b, a))；

(2) 若有f(n) = θ(n^log(b, a) * (lgn)^k)，即f(n)以相似于n^(log(b, a))增长的速率渐进增长，则T(n) = θ(n^(log(b, a) * (lgn)^(k+1))，k为一常数，k >= 0；

(3) 若对于某常数ε>0，有f(n) = Ω(n^log(b, a+ε))，即f(n)以快于n^(log(b, a))的速率渐进增长，且对于某常数c > 1和所有充分大的正整数n有af(n/b) <= cf(n)，则T(n) = θ(f(n))。

举例来说吧：

[Ex3.]
T(n) = 4T(n/2) + n，解这个递归等式，分析T(n)的渐近性。

解：对T(n) = 4T(n/2) + n我们得到a = 4, b = 2, f(n) = n, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2，而f(n) = n = O(n^(2-ε))，此时ε= 1，根据Case (1)，我们得到T(n) = θ(n^2)。

[Ex4.]
T(n) = 4T(n/2) + n^2，解这个递归等式，分析T(n)的渐近性。

解：对T(n) = 4T(n/2) + n^2，我们得到a = 4, b = 2, f(n) = n^2, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2, f(n) = n^2 = θ(n^2 * (lgn)^0)，即k = 0，这样按照Case (2)，我们得到T(n) = θ(n^2 * (lgn)^(k+1)) = θ(n^2 * (lgn))。

[Ex5.]
T(n) = 4T(n/2) + n^3，解这个递归等式，分析T(n)的渐近性。

解：对T(n) = 4T(n/2) + n^3，我们得到a = 4, b = 2, f(n) = n^3, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2, f(n) = n^3 = Ω(n^(2+ε)，此时ε= 1，且4f(n/2) = (n^3)/2 <= cn^3(c >= 1/2)，所以得到T(n) = θ(n^3)。

对于大部分人来说’Master Method’应该是最常用的，这几个Case可要牢牢记在心上才行哟。