推 boy5548:lg(n/2)!=(n/2)lg(n/2)代入就可以了 02/10 13:19
※ 引述《boy5548 (小YO)》之銘言：
: 有題遞回式 T(n)=T(n-2)+2lgn
: 我解法如下 =T(n-4)+2(lg(n-2)+lgn)
: =T(n-6)+2(lg(n-4)+lg(n-2)+lgn)
: =T(n-8)+2(lg(n-6)+lg(n-4)+lg(n-2)+lgn)
: =...
: =T(n-n)+2(1+2+...+lgn)
: =T(0)+2(lgn(lgn+1)/2)
: =T(0)+lgnlgn+lgn
: Time:Θ(lgnlgn)
: 因為手邊沒解答 請各位檢查一下正確性 謝謝:)
=T(n-4)+2(lg(n-2)+lgn)
=T(n-6)+2(lg(n-4)+lg(n-2)+lgn)
=T(n-8)+2(lg(n-6)+lg(n-4)+lg(n-2)+lgn)
=...
=T(n-n)+2(lg2+lg4+...+lgn)
=T(0)+2( lg 2(1*2*...*n/2 ))
=T(0)+2( lg2+lg(1*2*...*n/2) )
=T(0)+2( lg2+lg(n/2)! )
=T(0)+2+2lg(n/2)!
Time:Θ(nlgn)
請問我這樣做有哪裡有錯嗎@@
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.250.206.167