[理工] 算法 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