[已解决]时间复杂度的分析

孤岛recwert

请问这个时间复杂度应该怎么求解？谢谢大家！！
   [ 答案是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-17 22:30:21

最后一行为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。

跳转到最佳答案楼层

兔子不吃窝边草

最后一行为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。