当两个矩阵相乘时，我们需要分配第三个矩阵来存储结果。在计算算法的内存消耗时是否应该考虑这个分配？
问问题
621 次
2 回答
1
我无法想象一个算法所需的空间小于存储结果所需的空间。这应该是所需空间的下限。
但显然我的想象力无法胜任手头的任务，输入参数的空间和输出/结果的空间都不应该计入算法。
所以（正如下面的评论说服了我）：不。
于 2012-01-14T02:41:25.307 回答
0
正如其他回复所说，您必须区分矩阵本身占用的空间和乘法算法。
对于经典的 NxM 矩阵数据结构，占用的空间是 O(NM)。
至于算法本身，它取决于：基本的连续乘法算法占用 O(1) 空间，因为它一次将一个元素相乘和求和。
在将 NxM 和 MxP 矩阵相乘的并行算法中，每个处理器应该占用 O(1) 空间，因为每个进程计算一个乘法值，但在空间上是 O(X)，其中 X 是处理解决方案的并行进程的数量。
于 2012-01-14T03:31:24.653 回答