[理工] 資結 時間複雜度

看板Grad-ProbAsk作者 (屬於金牛的妳)時間7年前 (2018/04/14 15:13), 編輯推噓1(1推 0噓 8→)
留言9則, 2人參與, 7年前最新討論串8/12 (看更多)
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
推
04/14 15:55, 7年前 , 1F
T(1)=1就是n=1帶入
04/14 15:55, 1F
→
04/14 15:55, 7年前 , 2F
他因為<=1只需要做return 2就結束了
04/14 15:55, 2F
→
04/14 15:56, 7年前 , 3F
不會再有遞迴 所以所花時間是1 (常數等級)
04/14 15:56, 3F
→
04/14 16:00, 7年前 , 4F
T(n)=2T(n/2)+theta(1)
04/14 16:00, 4F
→
04/14 16:00, 7年前 , 5F
因為原本的遞迴有兩個呼叫
04/14 16:00, 5F
→
04/14 16:00, 7年前 , 6F
所以時間就是兩個呼叫的時間加起來即2T(n/2)
04/14 16:00, 6F
→
04/14 16:00, 7年前 , 7F
theta(1)是指他除了呼叫遞迴之外
04/14 16:00, 7F
→
04/14 16:00, 7年前 , 8F
做兩個*一個+所花的時間
04/14 16:00, 8F
→
04/14 16:12, 7年前 , 9F
謝謝W大 我懂了
04/14 16:12, 9F
‣ 更多 for0423 的文章
文章代碼(AID): #1QqQesXU (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 8 之 12 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共12篇)
‣ 更多 for0423 的文章
文章代碼(AID): #1QqQesXU (Grad-ProbAsk)