数据结构时间复杂度的问题
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
c[i] [j]=0;
for (k=0;k<n;k++)
c[i] [j]+=a[i] [k]*b[k] [j];
这段程序每行的程序步分别是多少？还有时间复杂度是怎么算的？书上写的不是很明白，顺便答案是，第一行到第五行分别是n+1;n(n+1);n^2;n^2(n+1);n^3
第1个回答 2013-10-28
第二个for循环吧第三行到底五行括起来，
第一行：for内部的程序步：0--n，共n+1
第二行：与第一行类似n+1次，而且在第一个for内部0--(n-1)=n次，所以程序步n*(n+1)
依次算出各行的程序步
时间复杂度：与程序步类似，只留最高次幂非别为：n, n^2, n^2, n^3, n^3。
第一行：for内部的程序步：0--n，共n+1
第二行：与第一行类似n+1次，而且在第一个for内部0--(n-1)=n次，所以程序步n*(n+1)
依次算出各行的程序步
时间复杂度：与程序步类似，只留最高次幂非别为：n, n^2, n^2, n^3, n^3。
第2个回答 2020-03-06
第3个回答 2013-10-28
程序添加括号如下：
for(int i=0;i<n;i++) //0~n,为n+1
{ for(int j=0;j<n;j++)
//0~n，为n+1。外层循环执行了n次，第n+1次只判断了条件没执行语句，故为n(n+1)
{ c[i] [j]=0; //j的那层循环也是判断了n+1次，执行了n次，算上i层的n次，一共n^2
for (k=0;k<n;k++) //i、j一共执行了n^2，k自己判断n+1次，为n^2(n+1)
c[i] [j]+=a[i] [k]*b[k] [j]; //i，j，k层都只执行n次，故为n^3
}
}
一定要将程序的嵌套理解清楚才可以。
注：for(int i=0;i<n;i++)，i=0到i=n-1都满足i<n，执行括号里的语句。i=n时，判断条件，for执行一次，但不满足i<n，故不执行括号里的语句。所以判断语句执行n+1次，括号里的语句执行n次。本回答被提问者采纳
for(int i=0;i<n;i++) //0~n,为n+1
{ for(int j=0;j<n;j++)
//0~n，为n+1。外层循环执行了n次，第n+1次只判断了条件没执行语句，故为n(n+1)
{ c[i] [j]=0; //j的那层循环也是判断了n+1次，执行了n次，算上i层的n次，一共n^2
for (k=0;k<n;k++) //i、j一共执行了n^2，k自己判断n+1次，为n^2(n+1)
c[i] [j]+=a[i] [k]*b[k] [j]; //i，j，k层都只执行n次，故为n^3
}
}
一定要将程序的嵌套理解清楚才可以。
注：for(int i=0;i<n;i++)，i=0到i=n-1都满足i<n，执行括号里的语句。i=n时，判断条件，for执行一次，但不满足i<n，故不执行括号里的语句。所以判断语句执行n+1次，括号里的语句执行n次。本回答被提问者采纳
相似回答
