[理工] 資結 時間複雜度

[for0423 (屬於金牛的妳)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1523690038.A.85E.html
推 wilson50101: T(1)=1就是n=1帶入
→ wilson50101: 他因為<=1只需要做return 2就結束了
→ wilson50101: 不會再有遞迴 所以所花時間是1 (常數等級)
→ wilson50101: T(n)=2T(n/2)+theta(1)
→ wilson50101: 因為原本的遞迴有兩個呼叫
→ wilson50101: 所以時間就是兩個呼叫的時間加起來即2T(n/2)
→ wilson50101: theta(1)是指他除了呼叫遞迴之外
→ wilson50101: 做兩個*一個+所花的時間
→ for0423: 謝謝W大 我懂了