Pseudocode(伪代码)

Soving Recurrences(解递归)

1.Recursion tree

解递归树

解T(n)=2T(n/2)+cn,其中c>0为常数。递归展开到T(n0),会导致推导的麻烦。所以解递归展开到T(1),然后再从前n0个T(n)的值确定渐进分析的常数。

继续展开得到

完全展开

Total=Θ(nlgn)。

很多递归式用递归树解不出来,但递归树能提供直觉,帮助我们用归纳法求解(Guess归纳假设)

较一般的递归式:T(n)=aT(n/b)+cn

a,b是大于1的整数,递归树方法仍可使用。

2.Substitution method

The most general method:

1.Guess the form of the solution;

2.Vertify by induction;

3.Solve for constants。

3.Master method

T(n)=aT(n/b)+f(n)。式中a>=1,b>=1,为整数,f(n)>0

以下loga均指以b为底a的对数

Case 1:f(n)<pow(n,loga)

f(n)=O(pow(n,loga-ε)),ε>0,为某一常数。f(n)的增长渐进地慢于pow(n,loga)(慢pow(n,ε)倍)

∴Solution:T(n)=Θ(pow(n,loga))。

Case 2:

f(n)=Θ(pow(n,loga)*pow(lgn,k)) k>=0为某一常数

f(n)和pow(n,loga)几乎有相同的渐进增长率。

∴Solution:T(n)=Θ(pow(n,loga)*pow(lgn,k+1))。

Case 3:f(n)>pow(n,loga)

f(n)=Ω(pow(n,loga+ε)),ε>0,为某一常数。f(n)的增长渐进地快于pow(n,loga)(快pow(n,ε)倍)

其中,f(n)满足:af(n/b)<=cf(n),0<c<1为常数

∴Solution:T(n)=Θ(f(n))。

总结:

等式右边,哪项变化得快,T(n)就属于哪项的数量级。