本节系列证明都可见4.5节需要说明的有4.3-8,4.3-9两题

4.3-8(本题有误)

T(n)=4T(n/2)+n根据4.5理论,结果为Θ(nlgn)

4.3-9

m = lgn

T(2) = 3T(2) + m

S(m) = T(2)

S(m) = 3S(m/2) + m

S(m) = Θ(m)

T(n) = S(m) =Θ(m )= θ((lgn))

05-08 15:14