[理工] [DS]101台大電機丙 第三題

[Billgaspeed (Billgaspeed)]

http://i.imgur.com/laPAdJr.jpg

這是我的想法

http://i.imgur.com/gfF79ig.jpg

但版上答案是C

想問一下是我想法錯誤還是時間複雜度算錯

感謝各位

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.51.148
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455201786.A.4EB.html
→ amge1524: 為何是log(l) * o(l), 迴圈又不是每個都run goo(l)
推 hello11705: 我是這樣算的啦 椅稻･`  http://i.imgur.com/F3UoT5x
推 janus7799: 外層做n次，內層做2的log(n)次方=也是n次
→ Billgaspeed: 可是他有J=J/2耶 感覺會有log
→ Billgaspeed: log(l) * o(l)是我令數字帶進去trace出的結果
→ Billgaspeed: 我令n=16
推 FRAXIS: 內層是 O(i).. 因為是 i + i/2 + i/4 ... <= 2i