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

看板Grad-ProbAsk作者 (AG)時間15年前 (2011/02/11 19:25), 編輯推噓0(0推 0噓 14→)
留言14則, 4人參與, 最新討論串2/3 (看更多)
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
→
02/11 19:29, , 1F
題目應該是說"第k層" ^^"
02/11 19:29, 1F
→
02/11 19:31, , 2F
好像不是 XDD 但原PO應該多算一層了
02/11 19:31, 2F
→
02/11 19:35, , 3F
如果root的height是1, depth k 應該只有k項
02/11 19:35, 3F
→
02/11 19:39, , 4F
展開的前兩行最後一項好像怪怪的?
02/11 19:39, 4F
→
02/11 19:53, , 5F
剛展開括號內是 1/sqrt(2) 的等比, 跟原po不大一樣耶?
02/11 19:53, 5F
→
02/11 22:33, , 6F
謝謝 我在看看 :)
02/11 22:33, 6F
→
02/11 22:35, , 7F
順道問一下, T(1)前我的係數是N^2 不知道是否正確呢?
02/11 22:35, 7F
→
02/11 22:40, , 8F
展開是我自己算的 應該是lgN吧?!
02/11 22:40, 8F
→
02/11 22:44, , 9F
我是想 bT(N/a) b一直是a的平方, 所以a是N時, b是N^2 ?
02/11 22:44, 9F
sorry, 我忘記前面還有一個4的冪次方 = = 應該是N^2沒錯! ※ 編輯: christianSK 來自: 111.243.149.78 (02/11 22:48)
→
02/11 22:50, , 10F
嗯嗯 :) 原PO你第一行 最後一項好像寫成N/2了 抄錯嗎XD
02/11 22:50, 10F
※ 編輯: christianSK 來自: 111.243.149.78 (02/11 22:54)
→
02/11 22:54, , 11F
XD" 很不靈光! 謝謝
02/11 22:54, 11F
→
02/11 23:05, , 12F
XD這題我展開到一半就寫不下去直接用 Master了..
02/11 23:05, 12F
→
02/11 23:14, , 13F
我回了個展開不知道對不對 XD
02/11 23:14, 13F
→
09/11 14:14, , 14F
XD" 很不靈光! 謝 https://daxiv.com
09/11 14:14, 14F
‣ 更多 christianSK 的文章
文章代碼(AID): #1DLHp7NX (Grad-ProbAsk)
‣ 更多 christianSK 的文章
文章代碼(AID): #1DLHp7NX (Grad-ProbAsk)