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

作者: jojoboy0115 (jojo)   2018-12-06 22:59:55
https://i.imgur.com/dPEyEKP.jpg
請問為什麼它的recursion tree子節點,
不是分別為 (n/2) (n/2) ... (n/2) ←有八個 ?
其實也不可能是8個(n/2),這樣合起來就是4n...大於1
它的8c是怎麼判斷的?是把T(n/2)當成constant?
感謝大家~
作者: skyHuan (Huan)   2018-12-06 23:48:00
改後面的f(n)有可能是8個n/2他寫的那個是每步驟成本的意思在算T(n)這個步驟需要theta(1)=c的成本剩下call遞迴,就是8T(n/2)的部分就是成本樹的第二層,一樣每部theta(1)
作者: jojoboy0115 (jojo)   2018-12-07 00:16:00
了解了,感謝sky大!

Links booklink

Contact Us: admin [ a t ] ucptt.com