作者learnerQQ (小銓)
看板C_and_CPP
標題[問題]
時間Fri Jul 10 13:25:30 2009
小弟 有個很囧的問題 想請問一下板上 有關下面迴圈執行的次數
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
1F：推 syntex:第一，你列的程式後面執行次數是錯的，應該是n*n*n 07/10 14:32
2F：→ syntex:第二，根據n*(n+1)*(n+2)/6 我覺得你程式會否看錯，是不是 07/10 14:32
3F：→ syntex:for(i=1;i<=n;i++) for(j=i;j<=n;j++) for(k=j;k<=n;k++) 07/10 14:33
4F：噓 adrianshum:先寫好標題 =_= 07/10 14:48
5F：→ netsphere:1,2,3 只有3個 1,2,3,....,n只有n個拉 07/10 16:21
6F：→ learnerQQ:那不知道 設定 "=" 算不算 執行次數呢@"@? 還是 printf 07/10 16:47
7F：→ learnerQQ:才算執行次數 這樣n=3 印出 27次 n*n*n=27 07/10 16:48
8F：→ netsphere:你不是問迴圈跑起幾次嗎? 跟 設定 "=" 有什麼關係 07/11 09:28
9F：推 Doule:n * (n+1) *(n+2) /6 是指Σk^3 (k=1~n) 07/20 17:35
10F：→ Doule:所以你的程式應該是三樓說的那樣 07/20 17:35
11F：→ Doule:PS. Σk^3 是高一數學歐 07/20 17:36