[理工] 資結 時間複雜度

看板Grad-ProbAsk作者 (brad84622)時間9年前 (2016/08/15 03:06), 編輯推噓1(1推 0噓 6→)
留言7則, 3人參與, 最新討論串4/12 (看更多)
各位早 http://i.imgur.com/p2mnjK9.jpg
http://i.imgur.com/Ao06nQL.jpg
想請問為什麼是2T而不是4T呢 ----- Sent from JPTT on my Samsung SM-N9208. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.166.145 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1471201618.A.685.html
推
08/15 07:40, , 1F
四倍關係是程式跑出來的"結果"，但是題目問的是"時
08/15 07:40, 1F
→
08/15 07:41, , 2F
間"的關係，執行n的時候是執行了兩次n-1的時間，然
08/15 07:41, 2F
→
08/15 07:41, , 3F
後乘2再加1，所以是T(n)=2T(n-1)+常數，常數是乘法
08/15 07:41, 3F
→
08/15 07:41, , 4F
和加法所需的時間
08/15 07:41, 4F
→
08/15 11:47, , 5F
程式碼的2*T(n/2)的2* 是算在常數時間裡面唷
08/15 11:47, 5F
→
08/15 11:48, , 6F
若改成return 4*T(n/2) 就會變成 T(n/2) + constant
08/15 11:48, 6F
→
08/15 15:14, , 7F
懂了！！ 感謝樓上2位
08/15 15:14, 7F
‣ 更多 brad84622 的文章
文章代碼(AID): #1NiC5IQ5 (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 4 之 12 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共12篇)
‣ 更多 brad84622 的文章
文章代碼(AID): #1NiC5IQ5 (Grad-ProbAsk)