作者mqazz1 (無法顯示)
站內Prob_Solve
標題[問題] 程式執行複雜度
時間Sat Oct 1 19:52:05 2011
1. for(a=1; a<=n; a++)
for(b=1; b<=a; b*=2)
c++;
2. for(a=1; a<=n; a*=2)
for(b=1; b<=a; b*=2)
c++;
3. k=0;
for(i=0; i<n; i++)
for(j=0; j<i*i; j++)
for(z=0; z<j; z++)
k++;
4. k=0;
for(i=1; i<n; i++)
for(j=1; j<i*i; j++)
if(j%i==0)
for(z=0; z<j; z++)
k++;
請問這四題的時間複雜度要怎麼分析?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.26.214
1F：→ firejox:for(j%i==0) = =+ 10/01 20:06
2F：推 chchwy:這是某年的交大考題嗎 10/01 20:29
1和2是台科的 3和4是交大的
3F：→ suhorng:猜: O(nlogn) O((log n)^2) O(n^2), and k恆等於0 ? 10/01 20:43
某補習班x逸的答案是 1.O(nlogn) 2.O((logn)^2) 3.O(n^5) 4. O(n^4)
可以請問這些要怎麼解嗎?
4F：→ suhorng:第四個我是把for當成if來猜... 10/01 20:43
5F：→ firejox:你不覺得"for(j%i == 0)" 這個很奇怪嗎.... 10/01 21:24
我打錯了 已改..
※ 編輯: mqazz1 來自: 61.228.26.214 (10/01 21:49)