[問題] 計概問題

看板Grad-ProbAsk作者 (wsx)時間15年前 (2009/03/21 14:13), 編輯推噓2(2推 0噓 12→)
留言14則, 5人參與, 最新討論串7/11 (看更多)
請問有一個程式 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
→
03/21 14:21, , 1F
O(n)
03/21 14:21, 1F
→
03/21 14:23, , 2F
sum = sum + i這行會執行n/2次，所以是O(n/2)=O(n)
03/21 14:23, 2F
推
03/21 14:24, , 3F
一個迴圈而已
03/21 14:24, 3F
→
03/21 14:27, , 4F
記得我好像也想選O(n) 但選項內好像沒有耶 不知有沒記錯
03/21 14:27, 4F
→
03/21 14:31, , 5F
謝謝樓上大大們<(_ _)>
03/21 14:31, 5F
→
03/21 14:35, , 6F
除非它i=i+2，那個+打錯了.改成*才會是O(log n)
03/21 14:35, 6F
→
03/21 14:41, , 7F
請問大大您是怎麼看出來是執行n/2次 和若是i=i*2 就是logn呢?
03/21 14:41, 7F
→
03/21 14:42, , 8F
看這個的能力還蠻弱的 請大大指教一下 謝謝喔 不好意思
03/21 14:42, 8F
→
03/21 14:46, , 9F
i要乘幾次2才會是n答案是logN，不過i的初值要從1開始
03/21 14:46, 9F
→
03/21 14:48, , 10F
n/2是因為他一直加2，不就等於除2嗎？像10是2加5次
03/21 14:48, 10F
→
03/21 14:51, , 11F
原來是這樣 謝謝大大耐心詳細指導<(_ _)>
03/21 14:51, 11F
→
03/21 14:52, , 12F
寫太快.XD..2^x = n兩邊取log(以2為底)，x = log n
03/21 14:52, 12F
推
03/21 23:04, , 13F
我記得他題目是說最有可能的選項耶!所以我選O(nlogn)
03/21 23:04, 13F
→
03/21 23:05, , 14F
因為我想說他最接近O(n)，所以他最有可能
03/21 23:05, 14F
‣ 更多 wsx 的文章
文章代碼(AID): #19n8MLrH (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 7 之 11 篇)：
排序： 最舊先 | 最新先 | 留言數
問題
0
10
[問題] 計概問題 計概問題
wesdxc
15年前, 03/20
問題
2
14
[問題] 計概問題 計概問題
wsx
15年前, 03/21
在新視窗開啟完整討論串 (共11篇)
‣ 更多 wsx 的文章
文章代碼(AID): #19n8MLrH (Grad-ProbAsk)