递归式

74 阅读 0 评论 49 点赞

我是靠谱客的博主复杂大叔，最近开发中收集的这篇文章主要介绍递归式，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

常常需要对递归式的效率进行分析。然而遗憾的是，并没有通用的规律可循。所以解递归式就变成了猜谜游戏。比如:
求递归式T(n) = 2 * T( floor(n/2) ) + n，猜测T(n) <= c * n * lgn (一个好的猜测多么重要)。接下来用数学归纳法假设T(n) <= c * n * lgn 对于floor(n/2)成立，即有：
T( floor(n/2) ) <= c * floor(n/2） * lg(floor(n/2))
那么把上式带入要求证的方程中：
T(n) <= 2 * c * floor(n/2) * lg(floor(n/2)) + n <= c * n * lg(n/2) + n
= c * n * lgn - c * n * lg2 + n = c * n * lgn - c * n + n
<= c * n * lgn
此式对于n >= 0, c >= 1是成立的。

修正我们的猜测
对于T(n) = T(floor(n/2)) + T(ceil(n/2)) + 1，直觉猜测是T(n) <= c * n，但是我们在使用数学归纳法时却发现
T(n) <= c * floor(n/2) + c * ceil(n/2) + 1 = c * n + 1
该死的 + 1，使我们不能得到数学归纳法的准确形式。为了去除讨厌的常数项，修正我们的假设为 T(n) <= c * n - b，再次带入：
T(n) <= c * n - 2 * b + 1 <= c * n - b 即可。

巧妙的代换
证明：T(n) = 2 * T(floor(sqrt(n))) + lgn
为了出去讨厌的根号，设 m = lgn，于是转化为
T(2^m) = 2 * T(floor(m)) + m
再设S(m) = T(2^m)，有
S(m) = 2 * T(floor(m)) + m
新递归式的界为 S(m) = O( m * lgm )
再带回原值，有
T(n) = S(m) = O( lgn * lglgn)，证毕
证明: T(n) = 2 * T(floor(n/2)+17)+n 解为O(n * lgn)
假设对于 T(floor(n/2)+17)成立
代换为T(n) <= 2 * (c * floor(n/2) + 17) * lg(floor(n/2) + 17) + n
去掉floor
T(n) <= 2 * (c * n/2 + 17) * lg( n/2 + 17) + n
为了凑出一个负号，令
n / 2 + 17 = 3 / 4 * n => n = 68
即当n > 68时，有
T(n) < 2 * (c * n/2 + 17) * lg( 3 / 4 * n ) + n
展开，有
T(n) <= c * n * lgn, 证毕

主方法
猜的次数多了，慢慢摸到了规律。利用主方法，可以一眼猜出递归式的解。
对于形如T(n) = a * T( n/b ) + f(n)的递归式，计算 x = n^(logb（a))。并设y = n^(logb（a) - e), e为大于0的常数。设z = n^(logb（a) + e)。
若f(n) = O(y), 则T(n) = Θ(x);
若f(n) = Θ(x), 则T(n) = Θ( x * lgn );
若f(n) = Ω(z), 且a * f(n/b) <= c * f(n), 则T(n) = Θ(f(n)), c > 0, n足够大。
例子懒得举了。

参考文献：
Thomas H. Cormen, Charles E. Leiserson, Introduction to Algorithms, 2ed