时间复杂度 int i,j,k; for(i=0;i<n;i++) for(j=0;j<n;j++) {c[i][j]=0; for(k=0;k<n;k++) c[i][j]

Question

求每句的时间复杂度
int i,j,k;
for(i=0;i<n;i++) /* n+1 */ 为什么是n+1而不是n?
for(j=0;j<n;j++) /* n*(n+1) */ 如果上面的成立的话，这里应该是（n+1）*(n+1)才对呀？
{c[i][j]=0; /* n*n */
for(k=0;k<n;k++) /* n*n*(n+1) */
c[i][j]=c[i][j]+A[i][K]*B[k][j]; }/* n*n*n */
}
这是一个两个N阶方阵的乘积；
书中已经说了每句的时间复杂度，我不太明白，求高手帮我注解下，谢谢了。

Answer 1

int i,j,k;
for(i=0;i<n;i++) /* n+1 */ i=0,1,...n-1时执行循环体，i=n时结束循环，因此是n+1次
for(j=0;j<n;j++) /* n*(n+1) */ 上面i=n时结束了循环，不再执行内层的循环，因此外层是n，内层是n+1，总的是n*(n+1)
{c[i][j]=0; /* n*n */
for(k=0;k<n;k++) /* n*n*(n+1) */
c[i][j]=c[i][j]+A[i][K]*B[k][j]; }/* n*n*n */
}