作者taitin (小南)
看板Grad-ProbAsk
标题Re: [理工] [资结]-台大98-软体设计 对答
时间Wed Jan 20 18:57:04 2010
※ 引述《FRAXIS (喔喔)》之铭言：
: : (4) E
: 这题的递回关系是不是T(n) = 2T(n-2) + n ?
: 我觉得解起来像是I
an-2a(n-2)=n
α^2-2=0 α=2^0.5 -(2^0.5)
an(h)=c1(2^0.5)^n+c2(-(2^0.5))^n
an(p)=d0+d1n
an=an(h)+an(p)
O(an)=O(2^n)
: : (5) H
: 这题的递回关系是不是T(n) = nT(n^0.5) + n^2 lg n ?
: 看不太出来能够怎麽解..
T(n)=nT(n^0.5) + n^2 lg n
=n^1.5 T(n^0.25) +n*(n^0.5)^2*lg(n^0.5)+n^2 lg n
=n^1.75T(n^0.125)+(n^1.5)*(n^0.25)^2*lg(n^0.25)+n^2lg(n^0.5)+n^2 lg n
=....
(1+0.5+0.25+...) 2
= n + n * [ lgn+lg(n^0.5)+lg(n^0.125)+...]
2 2 (1+0.5+0.25+...)
= n + n [lg(n )]
2 2
= n +2 n lg n
2
=O(n lgn)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.221.133
※ 编辑: taitin 来自: 61.230.221.133 (01/20 19:24)