作者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)