这段算法是什么意思，请通俗一点 - 编程论坛

#2

beyondyf2010-10-16 12:34

不知道出于什么目的，而且下标还是从1开始而不是0。
总之这段代码将矩阵a的第i,j个元素分别乘以矩阵b的第j列的每一个元素，并将和赋值给c的第i,j个元素。
这段代码的效率不高，修改一下：
for(i=1; i<=n; i++)
  for(j=1; j<=n j++)
  {
      TYPE tmp=0;
      for(k=1; k<=n; tmp+=b[k++][j]);
      c[i][j] = a[i][j]*tmp;
  }
将TYPE替换为实际的变量类型。

#3

Tveiker2010-10-16 15:29

下标从1开始应该是更好的与数学表达式相联系吧。
该段代码的意思就是求一个矩阵c[i][j]，且C[i][j]是a[i][j]与矩阵第j列所有元素和的乘积。
上楼的代码某种程度降低了原代码的时间复杂度，但没降数量级；仍为n的3次方
修改下，降一个数量级
int sum[n+1]    //由于原程序下标从1开始(其实下标可以从0开始，这样可以降低空间复杂度，这里只是附和原程序)
for(int i=1;i<n+1;i++)
    sum[i]=1;         //初始化
/*
计算b每列的和
*/
for(i=1;i<n+1;i++)
   for(int j=1;j<n+1;j++)
       sum[i]=+b[j][i];
/*
实现核心算法
*/
for(int i=1;i<n+1;i++)
   for(int j=1;j<n+1;j++)
      c[i][j]=a[i][j]*sum[j];
上面的算法时间复杂度为2*n*n+n

#4

聋眼睛瞎耳朵2010-10-16 15:29

改成这样
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]=c[i][j]+a[i][k]*b[k][j];//这句变了一下
   }
就是求两个矩阵的乘积的算法

[ 本帖最后由聋眼睛瞎耳朵于 2010-10-16 15:47 编辑 ]

#5

beyondyf2010-10-16 18:21

3楼是位精益求精的朋友

感谢你的指正。
关于复杂度的计算要有一个基准。基于乘法运算的速度远低于加法运算所以我优化的原则是尽量减少乘法运算的次数，并以一次乘法运算作为时间复杂度单位的话，那么我的代码的复杂度也是N的2次方。
当然，我相信还是你的代码会更快一点。这是牺牲空间复杂度换取时间复杂度，以目前电脑内存的水平这种做法是可取的。
一点小的问题，sum应该初始化为0而不是1，另外求和中的=+应该是一处笔误，并且编译器不会报错，如果实际中没有发现的话会导致计算结果错误。但这并不影响我对你代码的理解，感谢你的参与交流

#6

dong35802010-10-17 20:48

虽然学到这儿，可还是觉得蒙了。代码看懂了，可那个时间复杂度倒是很晕

#7

爱上对方法国2010-10-28 11:38

求两个矩阵么