作者for0423 (属於金牛的你)
看板Grad-ProbAsk
标题[理工] 资结 时间复杂度
时间Sat Apr 14 15:13:55 2018
https://i.imgur.com/iNNFkQV.jpg
https://i.imgur.com/ZXLQ0pj.jpg
不太懂解答第一行为什麽要加theta(1)
还有为什麽T(1)=1
麻烦各位了QQ
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.8.73.80
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1523690038.A.85E.html
1F：推 wilson50101: T(1)=1就是n=1带入 04/14 15:55
2F：→ wilson50101: 他因为<=1只需要做return 2就结束了 04/14 15:55
3F：→ wilson50101: 不会再有递回 所以所花时间是1 (常数等级) 04/14 15:56
4F：→ wilson50101: T(n)=2T(n/2)+theta(1) 04/14 16:00
5F：→ wilson50101: 因为原本的递回有两个呼叫 04/14 16:00
6F：→ wilson50101: 所以时间就是两个呼叫的时间加起来即2T(n/2) 04/14 16:00
7F：→ wilson50101: theta(1)是指他除了呼叫递回之外 04/14 16:00
8F：→ wilson50101: 做两个*一个+所花的时间 04/14 16:00
9F：→ for0423: 谢谢W大 我懂了 04/14 16:12