[非關] 資料結構與演算法獵人
想請問版上資料結構與演算法觀念好的程式獵人
關於程式碼中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
推
04/21 09:41, , 1F
04/21 09:41, 1F
→
04/21 09:42, , 2F
04/21 09:42, 2F
→
04/21 09:45, , 3F
04/21 09:45, 3F
→
04/21 09:46, , 4F
04/21 09:46, 4F
又回去翻了一下，Horowitz的聖經書上的確是這麼寫的。
作者是把一句statement都算一個step，如
x = y;
x = y + z + (x/y) + (x*y*z-x/z);
都為一個step
總之無關複雜度,感謝各位回答
推
04/21 18:59, , 5F
04/21 18:59, 5F
推
04/21 19:02, , 6F
04/21 19:02, 6F
→
04/21 19:03, , 7F
04/21 19:03, 7F
推
04/21 21:32, , 8F
04/21 21:32, 8F
※ 編輯: yehiso (36.238.103.34), 04/21/2014 23:36:59
Hunter 近期熱門文章
PTT動漫區 即時熱門文章
