[理工] 遞迴樹問題

看板Grad-ProbAsk作者 (ponny)時間9年前 (2016/11/16 09:25), 編輯推噓6(6推 0噓 8→)
留言14則, 4人參與, 最新討論串1/2 (看更多)
哈囉大家早 我今天在寫成大與台大這兩題的時候，覺得是同樣的算法但是答案差了一個M倍，請大家幫忙解答>< 成大103 http://i.imgur.com/Ot1vh7I.jpg
http://i.imgur.com/0lhSCBv.jpg
臺大105 http://i.imgur.com/pVqbBW5.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.126.194.203 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479259534.A.AF1.html
推
11/16 10:04, , 1F
他是不是沒有乘M阿
11/16 10:04, 1F
→
11/16 10:07, , 2F
他錯了吧 他的式子最下面那個lv也是算常數cost而已 (16^h
11/16 10:07, 2F
→
11/16 10:07, , 3F
)*c那裡
11/16 10:07, 3F
→
11/16 10:07, , 4F
應該要乘M吧
11/16 10:07, 4F
推
11/16 10:25, , 5F
你都算出8^(log n/(m^1/2)了=[n/(m^1/2)]^log8=[n
11/16 10:25, 5F
→
11/16 10:25, , 6F
/(m^1/2)]^3=n^3/m^3/2=n^3/m*m^(1/2)最後乘上m=>
11/16 10:25, 6F
→
11/16 10:25, , 7F
答案
11/16 10:25, 7F
推
11/16 10:34, , 8F
演算法那本最下面那層應該帶16^h*M，如h大所述
11/16 10:34, 8F
推
11/16 23:14, , 9F
不太懂為什麼要去乘M
11/16 23:14, 9F
→
11/16 23:14, , 10F
畢竟recursion tree 不是本來就直接算出node數再去乘做一次
11/16 23:14, 10F
→
11/16 23:14, , 11F
node需要的時間C就好嗎
11/16 23:14, 11F
推
11/17 15:20, , 12F
是不是因為M不是一個常數而是獨立於n的變數所以要算進
11/17 15:20, 12F
→
11/17 15:20, , 13F
去?
11/17 15:20, 13F
推
11/24 01:02, , 14F
對
11/24 01:02, 14F
‣ 更多 boy00114 的文章
文章代碼(AID): #1OAxMEhn (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 boy00114 的文章
文章代碼(AID): #1OAxMEhn (Grad-ProbAsk)