递归式求解的三种方法

递归式的时间复杂度一般都不太好理解，求证，算法导论里给出了三种求解递归式时间复杂度的方法：

1、代换法 （凭直觉，经验）

实际使用的是归纳法，即根据直觉经验判断结果应该是什么，然后再归纳求解。

先带入常量c，然后归纳得出这样的c存在

Ex1: T(n) = T(n-1) + n, 我们先猜测解是O(n^2)
假定对于任意的m<n, T(m) <= cm^2,带入递归式
T(n) <= c(n-1)^2 + n
= cn^2 - 2cn + c + n
= cn^2 - ((2c-1)n - c)
<= cn^2
可见只要c>1,n>0,而n本就要求大于0，故((2c-1)n - c)>0，故T(n)<=O(n^2)，得证
Ex2：T(n) = 2T(n/2)+n, 我们先猜测解是O(nlgn)
假定对于任意的m<n, T(m)<=cmlgm, 带入递归式可得
T(n) <= 2c(n/2)lg(n/2)+n
   
 = cnlg(n/2)+n
   
<= cnlgn-cnlg2+n
      = cnlgn-(c-1)n
可见只要c>1，(c-1)n > 0, 故T(n)<=cnlgn,所以我们的猜测是正确的，所以得证

但这不是首选的方法，因为猜测的形式很难，需要积累很多的求解的经验

2、递归树法

递归树法不是那么精确，取决于你画递归树的精确度。用递归树来猜测上界，然后用上面的代换法来证明正确性

Ex1: T(n) = T(n-1) + O(n)
T(1) = 1
n
n
/
T(n-1)
n-1
/
T(n-2)
n-2
...
.
/
.
T(1)
1
树高度n,1+2+...+n=n(n-1)/2,即O(n^2)
Ex2：T(n) = 2T(n/2)+O(n)
T(1) = 1
n
n
/

T(n/2)
T(n/2)
n/2+n/2=n
/

/

T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/4+...=n
...
/

n/8+...=n
T(1)
T(1)
1+1+...=n
树高度log2^n，即log2^n个n即nlog2^n，即O(nlog2^n)
Ex3：T(n) = 3T(n/2)+O(n)
T(1) = 1, 3T(n/2)下级分3个
n
n
|
|
|
T(n/2)
T(n/2)
T(n/2)
(3/2)n
|
|
|
|
|
|
...
T(n/4) T(n/4) T(n/4)
T(n/4) T(n/4) T(n/4)
(3/2)^2 n
...
/
T(1)
因为2倍数递减，所以树高度log2^n,(1+3/2+(3/2)^2+(3/2)^3...)*n=(1 + (3/2)(1-(3/2)^log2^n)/(1-(3/2)))*n，即O(nlog2^3)即O(n^1.585)
注:等比数列前n项和公式为：Sn=首项*（1-公比的n次方）/（1-公比）

3. 主方法（首推）

主方法使用的情况是递归式满足T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)，在这种情况下主方法假设子问题具有相同的大小，主方法是一个用来解递归式渐进时间复杂度的黑盒工具。

下面是简洁描述版本

• a：子问题数量
• b：子问题大小的所见系数
• d：递归过程之外的运行时间对问题规模n的指数系数
• a, b, d独立于n

Case1中的log函数没写base，因为这里得base对时间复杂度的影响仅仅在常系数下，而Case3中的log函数在指数上，所以不能忽略

Ex：

T(n)=3T(n/4)+n2：
a=3 b=4 d=2, 3<16,a<b^d, case2, 得O(n^d)=O(n^2)
T(n)=2T(n/4)+√n
a=2 b=4 d=1/2, 2=2, a=b^d, case1, 得O(n^dlogn)=O(n½logn)
T(n)=4T(n/4)+√n
a=4 b=4 d=1/2, 4>2, a>b^d, case3,
得O(n^logb^a)=O(n)
T(n)=2T(n/2)+nlgn
由表达式得知，n^logb^a=n^log2^2, 由于 f(n)/n^logb^a=nlgn/n=lgn,
对于 任意的 ω, 都不存在 lgn>n^ω,
故此不可被主方法求解。

引例：

http://raytaylorlin.com/Tech/algorithm/master-method/

http://blog.csdn.net/weixin_36497128/article/details/52914255

http://haiyangxu.github.io/posts/2014/2014-05-03-mastermethod.html