求时间复杂度（for循环内判断条件平方）

Question

for循环内判断条件平方求时间复杂度

sum = 0;
        for (i=0;i<N;i++)
            for(j=0;j<i*i;j++)
                for(k=0;k<j;k++)
                sum++;

i*i的情况应该如何判断

Answer 1

是O(N^5)，你的代码是0到N-1,同理为1～N
N=1 1
N=2 1+(1+2+3+4)=11;
N=3 1+(1+2...+4)+(1+2+3+4+5....+9)=56
N=n 1+(1+2+3+4)+....+(1+2+....+n^2) = 1+((1+2^2)2^2)/2+....+((1+n^2)n^2)/2=((1+2^2+3^2+n^2)+(1+2^4+3^4+n^4))/2
算一下可知最高次为n^5 所以为O(N^5)