作者wsx (wsx)
看板Grad-ProbAsk
标题[问题] 计概问题
时间Sat Mar 21 14:13:40 2009
请问有一个程式
int sum=0;
for(int i=0 ;i < n ;i=i+2)
sum = sum +i;
请问它的时间复杂度是多少?
O(nlog2n) ? O(logn) ? 还是其他呢?
先谢谢大大的回答
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.161.139.234
1F：→ AOK:O(n) 03/21 14:21
2F：→ square690410:sum = sum + i这行会执行n/2次，所以是O(n/2)=O(n) 03/21 14:23
3F：推 s987692:一个回圈而已 03/21 14:24
4F：→ wsx:记得我好像也想选O(n) 但选项内好像没有耶 不知有没记错 03/21 14:27
5F：→ wsx:谢谢楼上大大们<(_ _)> 03/21 14:31
6F：→ square690410:除非它i=i+2，那个+打错了.改成*才会是O(log n) 03/21 14:35
7F：→ wsx:请问大大您是怎麽看出来是执行n/2次 和若是i=i*2 就是logn呢? 03/21 14:41
8F：→ wsx:看这个的能力还蛮弱的 请大大指教一下 谢谢喔 不好意思 03/21 14:42
9F：→ square690410:i要乘几次2才会是n答案是logN，不过i的初值要从1开始 03/21 14:46
10F：→ square690410:n/2是因为他一直加2，不就等於除2吗？像10是2加5次 03/21 14:48
11F：→ wsx:原来是这样 谢谢大大耐心详细指导<(_ _)> 03/21 14:51
12F：→ square690410:写太快.XD..2^x = n两边取log(以2为底)，x = log n 03/21 14:52
13F：推 amiru3:我记得他题目是说最有可能的选项耶!所以我选O(nlogn) 03/21 23:04
14F：→ amiru3:因为我想说他最接近O(n)，所以他最有可能 03/21 23:05