作者haniwang (hani)
看板Grad-ProbAsk
标题[理工] 105 台 资演
时间Wed Feb 6 16:22:24 2019
想请问c小题设定那个范围会有什麽影响
https://i.imgur.com/03img89.jpg
想请问第4题的a b小题怎麽算
https://i.imgur.com/FChqr7h.jpg
麻烦各位了！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.139.0.113
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1549441347.A.761.html
1F：→ GeniusPuddin: 下面看起来是第3题? c小题那个就是你一直展开n 02/06 22:56
2F：→ GeniusPuddin: 最後当n<=sqrt(M)的时候T值会碰到M 02/06 22:57
3F：→ GeniusPuddin: 总之就答案的复杂度会包含n,M搂 02/06 22:57
4F：→ JKLee: c小题，可以先假设n=sqrt(M)*2^k 02/07 07:40
5F：→ JKLee: 接着画recursive tree 02/07 07:41
6F：→ JKLee: tree的第i层的时间为big-theta(1)*8^i 02/07 07:44
7F：→ JKLee: 但最後一层，也就是第k层的时间为T(sqrt(M))*8^k=M*8^k 02/07 07:47
8F：→ JKLee: 最後把每一层的时间加总 02/07 07:47
9F：→ JKLee: 仔细观察，你会发现当n介於这个范围时: 02/07 07:53
10F：→ JKLee: sqrt(M)*2^(k-1)<n<=sqrt(M)*2^k 02/07 07:53
11F：→ JKLee: 不会改变tree的高度，tree的层数依旧为k层 02/07 07:53
12F：→ haniwang: 感谢两位！ 02/07 17:22