CLRS 4.3用代入法求解递归式

4.3-1
猜测 ∃c>0 有 T(n)≤cn2 。

T(n)=T(n−1)+n≤c(n−1)2+n=cn2+(1−2c)n+c ，选 c=1 有：

T(n)≤n2−n+1≤n2 for n≥1

4.3-2
猜测 T(n)≤clg(n−d) ：

T(n)≤clg(⌈n2⌉−d)+1≤clg(n2−d+1)+1=clg(n−2d+2)−c+1≤clg(n−d)

其中 c≥1,d≥2 。

4.3-3
上界证明书上有，在此省略。
下界证明：
猜测 T(n)≥c(n+2)lg(n+2) ：

T(n)≥2c(⌊n/2⌋+2)(lg(⌊n/2⌋+2)+n≥2c(n/2−1+2)(lg(n/2−1+2)+n=2cn+22lgn+22+n=c(n+2)lg(n+2)−c(n+2)lg2+n=c(n+2)lg(n+2)+(1−c)n−2c≥c(n+2)lg(n+2)

其中 n≥2c/(1−c),0<c<1
所以 T(n)=Θ(nlgn)

4.3-4
猜测 T(n)≤cnlgn+d ，代入递推式可得

T(n)≤2c⌊n2⌋lg⌊n2⌋+2d+n≤cnlgn2+n+2d=cnlgn−(c−1)n+2d≤cnlgn+d

要让等式成立，就需要 d−(c−1)n≤0 ，显然要 c≥1 ，要保证 T(1)=1≤c⋅1⋅lg1+d=d ，所以 d≥1,c≥d+1 。

4.3-5
递归式： T(n)=T(⌊n/2⌋)+T(⌈n/2⌉)+Θ(n)
证明上界和下界类似，在此就只证明下界。
猜测 T(n)≥c(n+d)lg(n+d)

T(n)≥c(⌊n2⌋+d)lg(⌊n2⌋+d)+c(⌈n2⌉+d)lg(⌈n2⌉+d)+dn≥c(n2−1+d)lg(n2−1+d)+c(n2+d)lg(n2+d)+dn≥2c(n2−1+d)lg(n2−1+d)+dn=c(n+d+d−2)lg(n+2d−2)−c(2d−2)+(d−c)n

要使 c(n+d+d−2)lg(n+2d−2)−c(2d−2)+(d−c)n≥c(n+d)lg(n+d) ，只需 d≥2,0<c≤d 即可。

4.3-6
猜测 T(n)≤c(n−d)lg(n−d)

T(n)≤2c(⌊n2⌋+17−d)lg(⌊n2⌋+17−d)+n≤2c(n2+18−d)lg(n2+18−d)+n=2c(n2+18−d)(lg(n+36−2d)−1)+n=cnlg(n+36−2d)−(c−1)n−2c(d−18)lg(n+36−2d)−2c(d−18)

要使 cnlg(n+36−2d)−(c−1)n−2c(d−18)lg(n+36−2d)−2c(d−18)≤cnlg(n−d)

则需要 36−d≤0,c−1≥0,d−18≥0⇒c≥1,d≥36

4.3-7
猜测 T(n)≤cnlog34

T(n)≤4c(n3)log34+n=cnlog34+n

证明失败。
猜测 T(n)≤cnlog34−dn

T(n)≤4c(n3)log34−43dn+n=cnlog34−dn−(13d−1)n

要使 cnlog34−dn−(13d−1)n≤cnlog34−dn
显然 13d−1≥0 即可，所以有 c≥0,d≥3

4.3-8
猜测 T(n)≤cn2

T(n)≤4c(n/2)2+n≤cn2+n

证明失败。
猜测 T(n)≤cn2−dn

T(n)≤4c(n2)2−4dn2+n=cn2−dn−(d−1)n≤cn2−dn

显然 c≥0,d≥1 即可。

4.3-9
T(n)=3T(n−−√)+lgn ，令 m=lgn 有： T(2m)=3T(2m/2)+m 。
令 p=2m 有 S(p)=3S(p/2)+p
猜测 S(p)≤cplg3+dp ：

S(p)≤3(c(p/2)lg3+d(p/2))+p≤cplg3+(32d+1)p≤cplg3+dp

其中 d≤−2 。
同理可证明 S(p)≥cplg3+dp （证明略）

S(p)T(n)=Θ(plg3)=Θ(lglg3n)