Является ли алгоритм умножения матриц для NxM и MxP матриц O (NP) в пространстве?

Question

При умножении двух матриц нам нужно выделить третью для сохранения результата.Следует ли учитывать это распределение при расчете потребления памяти алгоритмом?

Answer 1

Я не могу представить аргумент, что пространство, необходимое для алгоритма, меньше, чем то, что требуется для хранения результата;это должна быть нижняя граница требуемого пространства.

Но, очевидно, мое воображение не соответствует поставленной задаче, и ни пространство для входных параметров, ни пространство для вывода / результата не должны учитыватьсяалгоритм.

Итак (как убедили меня комментарии ниже): нет.

Answer 2

Как говорят другие ответы, вы должны различать пространство, занимаемое самой матрицей и алгоритмом умножения.

Что касается классической структуры данных NxM matriz, то занимаемое пространство составляет O (NM).

Что касается самого алгоритма, то он зависит: базовый алгоритм последовательного умножения занимает пространство O (1), поскольку он умножает и суммирует один элемент за раз.

В параллельном алгоритме, умножающем NxM и MxPВ матрицах каждый процессор должен занимать пространство O (1), поскольку каждый процесс вычисляет одно значение умножения, а в пространстве - O (X), где X - число параллельных процессов, работающих над решением.