时间复杂度的分析
请问这个时间复杂度应该怎么求解？谢谢大家！！[ 答案是O(N^4) ]
sum=0;
for(i=1;i<N;i++)
for(j=1;j<i*i;j++)
if(j%i==0)
for(k=0;k<j;k++)
sun++; 本帖最后由 兔子不吃窝边草 于 2021-9-19 18:07 编辑
最后一行为sum；
由5,6行可知循环了j次；
分析第4行，j%i为0说明j为i的倍数；
由第3行分析，j为1到i^2-1，所以j可以为i*1，i*2，…，i*(i-1)，共计为i*（1+2+…+i-1）=1/2 * i^2 *（i-1），复杂度为i^3;
由第2行可知i为1到N-1，共计1^3+2^3+…+（N-1）^3，倒序相加推得1/2*( (1^3+（N-1）^3)+(2^3+(N-2)^3)+…+(（N-1）^3+1^3)),每一项的复杂度为N^3，共N-1项，所以复杂度为N^4。
页:
[1]