作者wjungle (俺)
看板Grad-ProbAsk
標題Re: [理工] [資結] 遞迴式
時間Sun Feb 17 16:30:43 2013
請問 =T(n-8)+2(lg(n-6)+lg(n-4)+lg(n-2)+lgn)
=...
=T(n-n)+2(lg2+lg4+...+lgn)
這是怎麼化簡的，
我在網路上查到類似的一題
T(n)=T(n-1)+ lgn
其作法不是用迭代法解的，是用證明的方法，如下
<解法>
猜測此遞迴式的解為Θ (nlgn) (為什麼是猜這個？)
需要分別證明T(n)≦cnlgn 和T(n)≧cnlgn
哪種方法才是正確的呢？
感謝
※ 引述《death888 (ZZZZ)》之銘言：
: ※ 引述《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: 1.160.223.9
推 gn123:你的第三行<=lgn+lgn+..+lgn=n/2*lgn=O(nlgn) 02/17 17:39
→ wjungle:不好意思，是問第一行到第三行是怎麼化簡的 02/17 17:53
→ vecan:這不是就展開而已嗎 甚麼化簡... 02/17 17:57
→ vecan:然後 為什麼知道猜測複雜度為nlogn? 02/17 18:03
→ vecan:就類似已經用展開或者MASTER..等方式求算出來後 02/17 18:04
→ vecan:為求精確才進行證明 所以你沒把完整題目拿出來 就沒有哪個對 02/17 18:05
→ vecan:或不對，也可以說看配分來決定 寫到哪、用哪種方式洽當 02/17 18:05
→ wjungle:不好意思，比較笨，就不會展開log，可以教一下嗎？ 02/18 08:11
→ wjungle:若是用master法，可以說一下是用哪個推出來的嗎？ 02/18 08:12
→ wjungle:會了！...==T(n-n)+2[lg(n-(n-2))+lg(n-(n-4))+...+lgn] 02/18 08:32
→ vecan:沒錯 就是那樣，我說master不是指這題，這題無法用master 02/18 22:56
→ vecan:我是指 各種題目可用各種其他求算精確 或者 粗略的複雜度 02/18 22:57
→ vecan:最後可在用 你所看到的證明方式 如定義證明 去給出確切驗證 02/18 22:59