[高分求助]计算各程序段的时间复杂度

Question

(1)
for (i=0;i<n;i++)
for (j=i;j<n;j++) x++;
(2)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
for (k=1;k<=n;k++)
x++;
(3)
for (i=1;i<n;i++)
for (j=1;j<n;j++) x++;
for (k=1;k<n;k++) x++;
(4)
for (i=1;i<n;i++)
{
j=i;
while (j<n) j*=2;
}
C语言的四个小题，请给出计算过程，谢谢！
想问下下面的大侠，n^2是什么意思？关键是我不懂这个符号“^”的意思，谢谢！

Answer 1

根据循环嵌套的层数进行初步判断即可
1 n^2
2 n^3
3 n^2
4 n^2

Answer 2

1， n的平方
2， n的3次方
3， n的平方+n
4， n(n+1)/2

n^2 就是n 的平方。。。

Answer 3

(1) n*(n+1)/2
for (i=0;i<n;i++)
for (j=i;j<n;j++) x++;
//i=0执行n次(j=0~n-1)
//i=1执行n-1次(j=1~n-1)
......
总次数: n+(n-1)+(n-2)+...+1 也即 1+2+3+...+n =n(n+1)/2

(2) n*n*n
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
for (k=1;k<=n;k++)
x++;
//k 循环执行 n 次, j 循环执行 n 次, i 循环执行 n 次
//所以总次数为 n次的n次的n次, 即 n*n*n , 也即 n^3

(3) (n-1)*(n-1)+(n-1)= (n-1)*n
for (i=1;i<n;i++)
for (j=1;j<n;j++) x++;
//j 循环执行 n-1 次(1~n-1) , i 循环执行 n-1 次;
//这里总次数为 (n-1)*(n-1)
for (k=1;k<n;k++) x++;
// 这里执行 (n-1)
总次数为 (n-1)*(n-1)+(n-1)=(n-1)*n

(4) (n-1)+(n-1)/2+(n-1)/4+(n-1)/8+...(/为整除)
for (i=1;i<n;i++)
{
j=i;
while (j<n) j*=2;
}