请教一个片断的算法复杂度
int i,j,k;for (i = 1; i < n; i++)
for (j = 0; j < i*i; j++)
if (j % i == 0)
for (k = 0; k < j; k++)
sum++;
做BIG O分析
关键是第二个for里又套了个if，而这个if的执行次数与n有关，不能做最坏分析
请各位不吝赐教
2006-08-25 11:23
在0到i*i中有O(i)个满足if,
循环
for (j = 0; j < i*i; j++)
.......
循环了O(i*i)次,有i次满足if要进入内循环循环O(i*i)次,所以这个循环的复杂度为O(i*i+i*i*i)=O(i^3);
总时间复杂度为O(n^4)
这个题目很无聊
2006-08-25 13:18
2006-08-25 13:57
在0到i*i中有O(i)个满足if,
循环
for (j = 0; j < i*i; j++)
.......
循环了O(i*i)次,有i次满足if要进入内循环循环O(i*i)次,所以这个循环的复杂度为O(i*i+i*i*i)=O(i^3);
总时间复杂度为O(n^4)
这个题目很无聊
我觉得不是i次,当j为素数是,内循环是不会被执行的.
2006-09-03 15:17