[理工] [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

继续阅读