有關回圈執行次數的問題

看板C_and_CPP作者learnerQQ (小銓)時間15年前 (2009/07/10 13:25)推噓1(2推 1噓 8→)

留言11則, 5人參與討論串1/1

小弟有個很囧的問題想請問一下板上有關下面迴圈執行的次數 int i,j,k,n; 執行次數 ------------------------------------------------------------------------------ for(i=1;i<=n;i+) (n+1) for(j=1;j<=n;j++) n * (n+1) for(k=1;k<=n;k++) n * n * (n+1) printf(" %d ,%d %d \n",i,j,k); ----------------------------------------------------------------------------- Total: (n+1) + n*(n+1) + n*n*(n+1) = n^3 + 2 n^2 + 2n +1 可是某書上寫著實際的迴圈執行次數為: n * (n+1) *(n+2) /6 於是，我很假設 n=3; 且我知道設定運算 " = " 的 COST 是 O(1) i j k i j k ---------------------- ---------------------- 值: 1 1 1 值: 2 2 1 2 2 3 3 4 (jump) 4 (jump) 2 1 3 1 2 2 3 3 4 (jump) 4 (jump) 3 1 4 (jump) 2 3 1 1 3 2 4 (jump) 3 4 (jump) 4 (jump) 2 1 1 2 1 2 2 3 3 4 (jump) 4 (jump) 3 1 2 3 4 (jump) 4 ( END) 上述的設定動作詳細如上圖 " 共有 52 次設定 " 27 次 printf(" "); 依我推的函數 : f(3)= n^3 + 2* ( n^2) + 2*n +1 = 52 但是書上的函數 f'(3) = n *(n+1)*(n+2) / 6 = 10 到底他所謂的執行次數是指 printf(" ") 的次數還是設定的次數? 我真的搞不清楚兩個迴圈我的推導跟課本是一樣的怎三個迴圈就出錯 ?? 我知道複雜的程式推導實際執行次數是很複雜的一件事但這個東西我希望能弄懂 ~"~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.225.21.177

推

syntex

07/10 14:32, , 1^F

07/10 14:32, 1^F

→

syntex

07/10 14:32, , 2^F

07/10 14:32, 2^F

→

syntex

07/10 14:33, , 3^F

07/10 14:33, 3^F