[非關] 資料結構與演算法獵人

[yehiso ()]

想請問版上資料結構與演算法觀念好的程式獵人

關於程式碼中count steps的問題


如一個for迴圈

for(int i=1;i<=n;i++);


這一個statement的count steps要如何計算

聖經書上的算法是1(i的初始化)+n(for)+1(最後一次執行)共n+2


問題來了,迴圈執行時,先判斷i<=n，在執行body,最後i++

這邊先不考慮body的情況下，那麼for應該是n(判斷)+n(i++) = 2n steps阿


雖然複雜度一樣是O(n)，但如果是為了方便計算而省略，那為何又要把

初始化和最後一次的執行的2 steps算進去


這問題困擾我很久了，希望有大神能開示一下。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.238.101.59
※ 文章網址: http://www.ptt.cc/bbs/Hunter/M.1398042367.A.D7A.html
推 Hikkiaholic:感覺在講不同東西 他在講"迴圈執行幾次" 就是後面如果
→ Hikkiaholic:有body body會跑幾次 而你是在講迴圈花的時間
→ Hikkiaholic:算時間是用你的算法沒錯 碰過好幾次 雖然後來都用O(n)
→ Hikkiaholic:書上那段我沒印象 但感覺在講{}的次數
又回去翻了一下，Horowitz的聖經書上的確是這麼寫的。

作者是把一句statement都算一個step，如

x = y;

x = y + z + (x/y) + (x*y*z-x/z);

都為一個step

總之無關複雜度,感謝各位回答

推 bill42362:i<=n, body, i++ 都算在 n 裡
推 bill42362:O(n) 和 i<=n 的 n 是兩個不同的東西，建議把迴圈裡的 n
→ bill42362:改成 m，再重新思考一次 @@"
推 allen65535:同意1樓，另外建議你養成上課舉手發問的習慣
※ 編輯: yehiso (36.238.103.34), 04/21/2014 23:36:59