Re: [理工] [DS] 96成大資工

[BenLinus (班)]

※ 引述《christianSK (AG)》之銘言：
: http://0rz.tw/RunXm
: alog的第二題
: 如果說用master theorem可以知道是 theta(N^2*N^0.5)
: 不過我展開之後卻發現有點奇怪

                        2  0.5
原題 T(N) = 4*T(N/2) + N *N

                                2      0.5
先算一個 T(N/2) = 4*T(N/4) +(N/2) *(N/2)  


                         2     0.5    2  0.5
T(N) = 4( 4*T(N/4) +(N/2) *(N/2) ) + N *N


                    2  0.5         0.5
     = 16T(N/4) +  N *N   [1 + (1/2) ]

     = ...

        2        2  0.5         0.5                    0.5
     = N T(1) + N *N   [1 + (1/2)  + ... + (1/2^(lgN-1))  ]

                                       lgN
        2        2  0.5    1 - sqrt(0.5)
     = N T(1) + N *N   [ --------------------]
                           1 - sqrt(0.5)


我展開長這樣, 不知道正確與否? 有算的人請幫忙check 謝謝!! ^^


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.195.103
※ 編輯: BenLinus        來自: 114.43.195.103       (02/11 23:15)
推 BLACKY31:倒數第二項的公比不會是 sqrt(0.5)喔~~
→ BenLinus:@@ 所以應該是...?
推 BLACKY31:事實上他是這樣子的數列 sqrt(1/2) sqrt(1/4) sqrt(1/8)
→ BLACKY31:咦?  我搞笑了XD
→ BenLinus:XD 沒關係, 這樣代表算對了!! 先把粗心用完考試就穩了!!
推 BLACKY31:sqrt(1/2)^lgN = N^(-1/2)
→ BenLinus:對耶, 感謝樓上補充~