Question

for(i=1;i<=n;++i) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j];}

求出它的时间复杂度

Answer 1

先整理一下：
for(i=1;i<=n;++i) // 重复n次，O(n)
for(j=1;j<=n;j++) // 又重复n次, O(n)
{
c[i][j]=0; // 工作量 1
for(k=1;k<=n;++k) // 重复n次，O(n)
c[i][j]+=a[i][k]*b[k][j]; // 工作量 1
} // 该括号部分语句工作量为 O(1+n*1)=O(n)

// 总的工作量（复杂度）为O(n * n * n)=O(n³)，简单的说，并列语句时，工作量相加，涉及到语句的循环时，工作量乘循环次数，所以一般只要看循环多少层就可以了。这里的第三层语句中工作量实际上不都被忽略了吗？

Answer 2

O(n的3次方)

追问

可以写出具体过程吗

追答

最内层循环的循环体重复执行“n的3次方”次啊。