[問題] 計概問題

[wsx (wsx)]

請問有一個程式

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
→ AOK:O(n)
→ square690410:sum = sum + i這行會執行n/2次，所以是O(n/2)=O(n)
推 s987692:一個迴圈而已
→ wsx:記得我好像也想選O(n) 但選項內好像沒有耶 不知有沒記錯
→ wsx:謝謝樓上大大們<(_ _)>
→ square690410:除非它i=i+2，那個+打錯了.改成*才會是O(log n)
→ wsx:請問大大您是怎麼看出來是執行n/2次 和若是i=i*2 就是logn呢?
→ wsx:看這個的能力還蠻弱的 請大大指教一下 謝謝喔 不好意思
→ square690410:i要乘幾次2才會是n答案是logN，不過i的初值要從1開始
→ square690410:n/2是因為他一直加2，不就等於除2嗎？像10是2加5次
→ wsx:原來是這樣 謝謝大大耐心詳細指導<(_ _)>
→ square690410:寫太快.XD..2^x = n兩邊取log(以2為底)，x = log n
推 amiru3:我記得他題目是說最有可能的選項耶!所以我選O(nlogn)
→ amiru3:因為我想說他最接近O(n)，所以他最有可能