[理工] 資結 時間複雜度

[brad84622 (brad84622)]

各位早
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
推 gary19941208: 四倍關係是程式跑出來的"結果"，但是題目問的是"時
→ gary19941208: 間"的關係，執行n的時候是執行了兩次n-1的時間，然
→ gary19941208: 後乘2再加1，所以是T(n)=2T(n-1)+常數，常數是乘法
→ gary19941208: 和加法所需的時間
→ aa06697: 程式碼的2*T(n/2)的2* 是算在常數時間裡面唷
→ aa06697: 若改成return 4*T(n/2) 就會變成 T(n/2) + constant
→ brad84622: 懂了！！ 感謝樓上2位