[理工] [DS]101台大電機丙第三題 Billgaspeed PTT批踢踢實業坊

作者: Billgaspeed (Billgaspeed) 2016-02-11 22:43:04

http://i.imgur.com/laPAdJr.jpg
這是我的想法
http://i.imgur.com/gfF79ig.jpg
但版上答案是C
想問一下是我想法錯誤還是時間複雜度算錯
感謝各位

作者: amge1524 (台灣加油) 2016-02-11 23:51:00

為何是log(l) * o(l), 迴圈又不是每個都run goo(l)

作者: hello11705 (小默) 2016-02-12 12:20:00

我是這樣算的啦椅稻･` http://i.imgur.com/F3UoT5x

作者: janus7799 (Janus逍遙) 2016-02-12 16:52:00

外層做n次，內層做2的log(n)次方=也是n次

作者: Billgaspeed (Billgaspeed) 2016-02-12 19:38:00

可是他有J=J/2耶感覺會有loglog(l) * o(l)是我令數字帶進去trace出的結果我令n=16

作者: FRAXIS (喔喔) 2016-02-14 19:45:00

內層是 O(i).. 因為是 i + i/2 + i/4 ... <= 2i

繼續閱讀