作者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