作者jojoboy0115 (jojo)
看板Grad-ProbAsk
标题[理工] 演算法 P.31 32题
时间Thu Dec 6 22:59:55 2018
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1544108398.A.880.html
1F：推 skyHuan: 改後面的f(n)有可能是8个n/2 12/06 23:48
2F：→ skyHuan: 他写的那个是每步骤成本的意思 12/06 23:48
3F：→ skyHuan: 在算T(n)这个步骤需要theta(1)=c的成本 12/06 23:48
4F：→ skyHuan: 剩下call递回，就是8T(n/2)的部分 12/06 23:48
5F：→ skyHuan: 就是成本树的第二层，一样每部theta(1) 12/06 23:48
6F：→ jojoboy0115: 了解了，感谢sky大！ 12/07 00:16