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

[jojoboy0115 (jojo)]

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
推 skyHuan: 改後面的f(n)有可能是8個n/2
→ skyHuan: 他寫的那個是每步驟成本的意思
→ skyHuan: 在算T(n)這個步驟需要theta(1)=c的成本
→ skyHuan: 剩下call遞迴，就是8T(n/2)的部分
→ skyHuan: 就是成本樹的第二層，一樣每部theta(1)
→ jojoboy0115: 了解了，感謝sky大！