※ 引述《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)