Question

时间复杂度？for（i=1;i<n;i++）; { for(j=1;j<i;j++) } 这样的解释？

for（i=1;i<n;i++）;
{
for(j=1;j<i;j++)
}
这样的解释？

Answer 1

楼主的理解错了,第一个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次?事实是这样的吗?不是的。(n-1)*
(n-2)/2这个是最内层循环体的本体运行的次数,而n-1次是外层循环体执行的次数,总复杂度是(n-1)*(n-2)/2+n-1这两部分组成的,由于前者大于后者,因此复杂度是(n-1)*(n-2)/2,最终是n^2。算复杂度其实主要看最里面那层运行多少次(其实可在i循环里加个"k++",j循环里面加个p++,k和p初始为0,运算输出可得k=n-1,p=(n-1)*(n-2)/2),还不明白可以再交流,444231011@qq.com

Answer 2

0 + 1 + 2 + 3 + 4 + 5 。。。。 + （n - 1）
=
n * n / 2

= n^2 / 2

一般近似为n^2

追问

第一个for运行了N次，第二个是不是运行了1+2+3+4+5+。。。。。+n-2次 ，n*（(n-2)(n-1)/2）,我的理解错在哪里？

Answer 3

(n-1)*(n-2) / 2

追问

为什么？

追答

第一层循环 n-1次
当i = 1 第二层循环没进去 0
当i = 2 1
当i = 3 2
....
当i = n-1 n-2

然后把0 + 1 + 2 + ....+ n-2

Answer 4

你要问什么？这就是一个延时程序，还是个无规律的

追问

第一个for运行了N次，第二个是不是运行了1+2+3+4+5+。。。。。+n-2次 ，n*（(n-2)(n-1)/2）,我的理解错在哪里？

追答

是呀，你的理解有点错，第一个for循环了n-1次，第二个是循环了1+2+。。。+n-2次。你要理解这的意义是什么，老师让你算的？

追问

请回答

追答

回答什么，不是给你说了，你理解理了，最后不是n*（(n-2)(n-1)/2）,是1+2+。。。+n-2+n-1

追问

为什么？

追答

两个循环次数想加呀，主要是你用第一个循环控制了第二上循环。
for(i=0;i<n;i++)
for(j=0;j<m;j++)
这就是n*m其实就 n个m次

上面我说错了，就是1+2+3+4+5+。。。。。+n-2次