→ donaldknuth:感謝回答~這樣寫反而比較直覺咧！ 02/09 14:06
推 cakeboy:這題用master法 可以用出來 02/09 22:37
※ 引述《donaldknuth (RoN)》之銘言：
: http://goo.gl/BeiY9
: 第六題，請問該怎麼證明完全，謝謝！
: T(n) = 2T(n/2)+nlgn
: = 2．[2T(n/4) + (n/2)lg(n/2) ] + nlgn
: = 4T(n/4)+n(lgn-1)+nlgn
= 4T(n/4)+2nlgn-n
= 4(2T(n/8)+(n/4)lg(n/4))+2nlgn-n
= 8T(n/8)+n(lgn-2)+2nlgn-n
= 8T(n/8)+3nlgn-(1+2)n
= ...
= nT(1)+lgn˙nlgn-(1+2+...+(lgn-1))n
= nT(1)+nlgnlgn-(lgn(lgn-1)/2)n
Time:Θ(nlgnlgn)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.120.51