Question

java 计算时间复杂度

1 for( int i = 0; i < n; i++ )
2 for( int j = i; j <= n; j++ )
3 for( int k = i; k <= j; k++ )
4 sum++;
5 for( int p = 0; p < n*n; p++ )
6 for( int q = 0; q < p; q++ )
7 sum—;

第四句 运行次数是
O( N3 )
那么 第七句的运行次数 是多少？？？

答案所给的是O( N4)， 这个是怎么来的？？？？

Answer 1

for(int p=0;p<n*n;p++)
    for(int q=0;q<p;q++)
        sum--;
下面我来简单解释一下为什么是O（n^4）
p的所有取值，以及相对性的sum运算的次数如下
p的取值：0  1  2  3  4  ...  (n^2 -1)
sum次数：0  0  1  2  3  ...  (n^2 -2)
从上面的式子我们知道sum--执行的次数也就是sum次数的累加和：
0+0+1+2+3+...+(n^-2)=1+2+3+ ... +(n^2 -2)这里我们可以用求和公式，但是需要搞定一个这里有多少项，很明显(n^2 -2)项，带入求和公式如下
=(1+(n^2 -2))*(n^2 -2)/2=(n^2 -1)(n^2 -2)/2=(n^4 -3*n^2 +2)/2
所以答案是O(n^4)

追问

（n^2 -1) 这个是什么意思？

追答

n的2次方

Answer 2

你算最大值就可以了。前一半每个循环的最大index是n，所以是n*n*n。后一半的循环每个循环最大index是n*n，所以最后时间复杂度是(n*n)*(n*n)也就是N^4