分析以下算法的时间复杂度

Question

public void fun(int n){
int s=0,i,j,k;
for (i=0;i<=n;i++)
for (j=0;j<=i;j++)
for (k=0;k<j;k++)
s++;
}

Answer 1

三重循环，时间复杂度O(n³)追问

可以给出解题过程吗？

追答

因为这是个三重循环，所以时间复杂度就是O(n³)

如果你非要算的话，最里层循环∑=1+2+...+j=j(j+1)/2

次里层循环∑=a1+a2+...+ai，其中ai=i(i+1)/2

最外层循环∑=b1+b2+...+bn，其中bn=an(an+1)/2

然后依次求数列通项

最后得到结果