作者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/m.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