→ donaldknuth:感謝回答~如果想依題目寫成tight bound要再多補充什麼 02/09 14:03
※ 引述《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+lg(n/2) )
: .
: .
: .
: = nT(1)+n( lgn+lg(n/2)+lg(n/4)...+lg1) )
^^^^^^^^^^^^^^^^^^^^^^^^^^
令n=2^k
所以畫線地方=k+(k-1)+....+1+0=k*(k+1)/2
=logn*(logn+1)/2
so T(n)=O(n*logn*logn)
應該是這樣吧
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.124.55.244
※ 編輯: chencccc 來自: 122.124.55.244 (02/09 13:03)