[理工] 演算法 P.31 32題

看板Grad-ProbAsk作者 (jojo)時間7年前 (2018/12/06 22:59), 編輯推噓1(1推 0噓 5→)
留言6則, 2人參與, 7年前最新討論串1/1
https://i.imgur.com/dPEyEKP.jpg
請問為什麼它的recursion tree子節點， 不是分別為 (n/2) (n/2) ... (n/2) ←有八個 ？ 其實也不可能是8個(n/2)，這樣合起來就是4n...大於1 它的8c是怎麼判斷的?是把T(n/2)當成constant? 感謝大家~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.224.107.101 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1544108398.A.880.html
推
12/06 23:48, 7年前 , 1F
改後面的f(n)有可能是8個n/2
12/06 23:48, 1F
→
12/06 23:48, 7年前 , 2F
他寫的那個是每步驟成本的意思
12/06 23:48, 2F
→
12/06 23:48, 7年前 , 3F
在算T(n)這個步驟需要theta(1)=c的成本
12/06 23:48, 3F
→
12/06 23:48, 7年前 , 4F
剩下call遞迴，就是8T(n/2)的部分
12/06 23:48, 4F
→
12/06 23:48, 7年前 , 5F
就是成本樹的第二層，一樣每部theta(1)
12/06 23:48, 5F
→
12/07 00:16, 7年前 , 6F
了解了，感謝sky大！
12/07 00:16, 6F
‣ 更多 jojoboy0115 的文章
文章代碼(AID): #1S2JbkY0 (Grad-ProbAsk)