c - 如何执行快速数组乘法？

Question

我有两个大小相同的数组:

A = [a1, a2, a3]
B = [b1; b2; b3]

我需要执行数组乘法以构建以下矩阵:

            |a1|
M = A * B = |a2| * |b1 b2 b3|  //M31 * M13 ==> M33 and M13 * M31 ==> M11.  Mnk: Matrix with n lines and k columns.
            |a3|


    | a1b1 a1b2 a1b3 |
M = | a2b1 a2b2 a2b3 |
    | a3b1 a3b2 a3b3 |

完成这项任务最快的算法是什么？

更详细:我需要使用 8086 指令集完成这项工作，但在这里我更愿意接收 C 代码中的算法。

Answer 1

看起来像Matrix Multiplication Algorithm更准确地说，我认为您正在寻找 efficient方式。

矩阵相乘的一般方法是 O(n^3)，但通过有效的方法，您将得到 O(n^2.807)。是否值得您花时间实现有效的方法？我不知道，但你必须对其进行评估。

如果您只有一维数组，那么唯一的方法是双循环，在这种情况下，您正在查看运行时间 O(n^2)。想出它不应该那么复杂:

for(int i = 0; i < A.length; i++)
{
    for(int j = 0; j < B.length; j++)
    {
        C[i][j] = A[i] * B[j];
    }
}