for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x++; 求时间复杂度

一道考试题目，没做出来问下解题思路

推荐答案 2018-05-13

这个是O(n^3)的
实际上就是∑(i=1,n)∑(j=1,i)∑(k=1,j)1
也就是∑(i=1,n)∑(j=1,i)j
也就是∑(i=1,n)(i*(i+1)/2)
(∑(i=1,n)(i*i))/2+(∑(i=1,n)i)/2
前者有一个求和公式，可以得到结果是n*(n+1)*(2n+1)/12，展开后显然是三次的
后者可以忽略，次数低
复杂度O(n^3)
只要是这种形式的循环，复杂度全部都是O(n^(循环层数))追问

呃有个地方没懂，算复杂度应该是最内层循环的次数吧，我是算到j层时应该是(1+n)*n/2次，n为3时j循环执行6次，但是到k层就实在算不清了，是这样算不对吗

温馨提示：答案为网友推荐，仅供参考

当前网址：http://www.wendadaohang.com/zd/A4K3AG33d5d151WdK55.html

相似回答

...for(j=1;j<=i;j++) for(k=1;k<=i;k++) x=i+j-k;答：1+4+9+16+25+……+n^2 =n+(0+3+8+15+24+...+(n+1)(n-1))上面这个式子说明复杂度是O(n^3)的，不过如果要求Θ的话，我觉得很可能是n^2·logn？后面那个式子可以化简不过我现在脑子不太够用……

哪位好人能帮我分析一下下列各程序段中x = x + y;语句的程序步数。答：for (int j = 1; j <= i; j++)，第二个for的执行次数是i的值，而i的值从1变为n，故用累加算法得，执行次数：n*(n+1)/2 ③最后是三层循环for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++)for (int k = 1; k <= j; k++)，第三个for的执行...

For(i=1;i<n;i++) For(j=1;j<i;j++) For(k=1;k<j;k++) X=x+1; 算出...答：三个希格玛的嵌套公式，外层是i从1到n-1，中层是j从1到i-1，内层是k从1到j-1 里面的表达式是1，因为内部只有x使用了1次于是化简为两个希格玛的嵌套公式，外层是i从1到n-1，内层是j从1到i-1 里面的表达式是1+2+...+（j-1）=j*（j-1）/2 继续往下化简就有点麻烦了，涉及到高中数...

时间复杂度?for(i=1;i<n;i++); { for(j=1;j<i;j++) } 这样的解释?答：楼主的理解错了,第一个for是运行N次(其实是n-1次,不进入循环体本体是不计算次数的,不过没影响),第二个也是1+2+3+4+...+n-2次(其实是0+1+2+...+n-2,不过也没有影响),可n*((n-2)*(n- 1)/2)的意思是什么呢?意思是(n-2)*(n-1)/2这个运算,做了n次?事实是这样的吗?不...

for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1;中...答：如果是1层循环，则次数是 1+1+1+...+1 = n 如果是2层循环，则将后面的1换成j的执行次数，也就是 1+(1+1)+(1+1+1) +...+(1+1+1+...+1) = 1+2+3+...+n = 1/2*n*(n+1)如果是3层循环，则将里层的1再换成k的执行次数，也就是 1+(1+(1+1)) + (1+(1+1...

求数据结构程序的时间复杂度答：只有第一个正确。第一个：for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j； 时间复杂度为： O(m*n)第二个：i=0，s=0； while (s<n) {s=s+i；i++；} 时间复杂度为： O(根号n)第三个：for(i=1,s=0:i<=n:i++){t=1:f...

、下面程序段的时间复杂度是。 for(i=1;i<=n;i++) for(j=1;j<=?答：；下面两段程序段的时间复杂度都是（N^2) 。for(i=1；i<＝n；i++) for(j=1；j<＝n; j++)...以及：for(i=1；i<＝n；i++) for(j=1；j<＝i; j++)...

for(i=1;i<=n;i++)for(j=1;j<=i;j++)s; 执行s语句的次数?答：双重循环，求S执行次数需要将两个循环的次数相乘。for(i=1;i<=n;i++)这句要执行n次 for(j=1;j<=i;j++)s;这条语句执行的次数为1+2+3+..+n，共n(n+1)/2次（等差公式）共n*n(n+1)/2次

for(i=1;i<=n;i++) for(j=1;j<=i;j++) s++;求时间复杂度答：总运行次数为1 + 2 + ... + n = n(n+1)/2 ，所以时间复杂度为O(n^2)

大家正在搜

for i in range fori in range 在循环语句forin1i1i matlab function for i in n for nose while(n++<=2)conversation rch for n