矩阵加法和乘法算法

Question

令 m, n 为整数，满足 0<= m,n< N。

定义：

  Algorithm A: Computes m + n in time O(A(N))

  Algorithm B: Computes m*n in time O(B(N))

  Algorithm C: Computes m mod n in time O(C(N))

使用算法 A、B 和 C 的任意组合描述了一个用于 N X N 矩阵加法和矩阵乘法的算法，其中的条目在 Z/NZ 中。还要指明算法的运行时间大 O 表示法。

尝试解决方案：

对于 Z/NZ 中的 N X N 加法：令 A 和 B 为 Z/NZ 中的 N X N 矩阵，其中条目 a_{ij} 和 b_{ij} 使得 i,j 在 {0,1,...,N} 中，其中 i 表示行，j 表示矩阵中的列。另外，令 A + B = C

Step 1. Run Algorithm A to get a_{ij} + b_{ij} = c_{ij}   in time O(A(N))

Step 2. Run Algorithm C to get c_{ij} mod N in time O(C(N))

对 {0,1,...,N} 中的所有 i,j 重复步骤 1 和 2。

这意味着我们必须重复步骤 1,2 N^2 次。所以总运行时间估计为

 N^2[ O(A(N)) + O(C(N)) ] = O(N^2 A(N)) + O(N^2 C(N)) = O(|N^2 A(N)| + |(N^2 C(N)|).

对于乘法算法，我只是用算法 B 替换了步骤 1，得到的总运行时间为 O(|N^2 B(N)| + |(N^2 C(N)|)，就像上面一样。

请告诉我我是否正确地解决了这个问题，尤其是使用大 O 表示法。

谢谢。

Answer 1

你的 matrix multiplication 算法是错误的，并且会产生错误的答案，因为 A*B_{i,j} != A_{i,j} * B_{i,j}（除了一些特殊情况，如零矩阵）

我假设问题的目标不是实现有效的矩阵乘法，因为这是一个困难且仍在研究的问题，所以我将回答矩阵乘法的天真实现。

对于任何索引 i,j:

(AB)_{i,j} = Sum( A_{i,k} * B_{k,j}) = 
           = A_{i,1} * B_{1,j} + A_{i,2} * B_{2,j} + ... + A_{i,k} * B_{k,j} + ... + A_{i,n} * B_{n,j}

如您所见，每对 i,j 有 n 乘法和 n-1 加法关于 C 的调用量 - 这取决于您是否需要在每次添加后调用它，或者在完成后仅调用一次（这实际上取决于您必须代表每个数字的位数），因此对于每对 i,j - 您可能需要它从一次到 2n-1 调用。

这给了我们总复杂度（假设每个 (i,j) 对的模数为 2n-1，如果如上所述需要的更少 - 相应调整）：

O(n^3*A + n^3*B + n^3*C)

作为旁注，一个良好的健全性检查表明你的算法确实不正确 - 事实证明矩阵乘法不能比 Omega(n^2 logn)（Raz,2002）和当前最佳实现更好是 ~O(n^2.3)

Answer 2

#include <stdio.h>

void main() 
{
  int i, j;
  int a[3][3], b[3][3];

  printf("enter elements for 1 matrix\n");

  for (i = 0; i < 3; i++) 
  {
    for (j = 0; j < 3; j++) 
    {
      scanf("%d", &a[i][j]);
    }
    printf("\n");
  }

  printf("enter elements for 2 matrix\n");

  for (i = 0; i < 3; i++) 
  {
    for (j = 0; j < 3; j++) 
    {
      scanf("%d", &b[i][j]);
    }
    printf("\n");
  }

  printf("the sum of matrix 1 and 2\n");

  for (i = 0; i < 3; i++) 
  {
    for (j = 0; j < 3; j++) 
    {
        printf("%d\n", (a[i][j] + b[i][j]));
    }
    printf("\n");
  }
}

矩阵加法和乘法算法

Algorithm for matrix addition and multiplication

algorithm

time

big-o

matrix

matrix-multiplication