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

[christianSK (AG)]

http://0rz.tw/RunXm

alog的第二題

如果說用master theorem可以知道是 theta(N^2*N^0.5)

不過我展開之後卻發現有點奇怪

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

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

     =  ...

     = N^2*T(1) + N^2* ( 1 + 2^0.5 + 3^0.5 + ... + lgN^0.5 )* N^0.5

這樣的話 不就是變成 theta ( lgN* N^2* N^0.5 ) ?

不知道我哪裡想錯了~


ds第二大題中的第6小題

因為 k >= 1 所以root的height應該是1吧??

這樣的話 maximun node 應該是 1 + 2 + 4 + ... + 2^k = 2^(k+1) -1 吧?!

不過手邊的答案是給 2^k - 1這個選項是對的!

不知道大家是怎麼想的 先謝謝大家了 :)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.123.122
→ BenLinus:題目應該是說"第k層" ^^"
→ BenLinus:好像不是 XDD  但原PO應該多算一層了
→ BenLinus:如果root的height是1, depth k 應該只有k項
→ BenLinus:展開的前兩行最後一項好像怪怪的?
→ BenLinus:剛展開括號內是 1/sqrt(2) 的等比, 跟原po不大一樣耶?
→ christianSK:謝謝 我在看看 :)
→ BenLinus:順道問一下, T(1)前我的係數是N^2 不知道是否正確呢?
→ christianSK:展開是我自己算的 應該是lgN吧?!
→ BenLinus:我是想 bT(N/a)  b一直是a的平方, 所以a是N時, b是N^2 ?
sorry, 我忘記前面還有一個4的冪次方 = =

應該是N^2沒錯!
※ 編輯: christianSK     來自: 111.243.149.78       (02/11 22:48)
→ BenLinus:嗯嗯 :) 原PO你第一行 最後一項好像寫成N/2了 抄錯嗎XD
※ 編輯: christianSK     來自: 111.243.149.78       (02/11 22:54)
→ christianSK:XD" 很不靈光! 謝謝
→ aoqq12:XD這題我展開到一半就寫不下去直接用 Master了..
→ BenLinus:我回了個展開不知道對不對 XD
→ sneak: XD" 很不靈光! 謝 https://daxiv.com