При умножении двух матриц нам нужно выделить третий, чтобы сохранить результат. Следует ли учитывать это распределение при расчете потребления памяти алгоритмом?Является ли алгоритм матричного умножения для матриц NxM и MxP O (NP) в пространстве?
Я не могу представить аргумента, что пространство, требуемое для алгоритма, меньше, чем требуется для хранения результата; это должна быть нижняя граница требуемого пространства.
Но, по-видимому, мое воображение не соответствует поставленной задаче, и ни пространство для входных параметров, ни пространство для вывода/результата не должны учитываться в алгоритме.
Итак (как указано ниже, убедили меня): нет.
Это полностью субъективно. Вы могли бы также утверждать, что фундаментальные затраты на сохранение результата не связаны с алгоритмом и поэтому не должны быть отнесены к нему. –
Если целью алгоритма является вычисление этого значения, и вы НЕ должны его хранить, не может ли это быть реализовано с одним большим no-op? Похоже, что он резко меняет то, что означает «стоимость». Не могли бы вы привести пример, где стоимость представления результата не считается частью пространственной сложности алгоритма, поскольку я, честно говоря, не могу придумать его. –
То, что я имею в виду, для данной задачи (в этом случае умножается матрица), не имеет значения, какой алгоритм вы выберете, всегда есть неотъемлемая стоимость необходимости хранить результат где-то. Но эта стоимость связана с задачей, а не с алгоритмом. –
Как говорят другие ответы, вы должны различать пространство, взятое самой матрицей и алгоритмом умножения.
Что касается классической структуры данных матриц NxM, то это место занимает O (NM).
Что касается алгоритма как такового, то он зависит: Основной алгоритм последовательного умножения принимает O (1) пространство, поскольку он умножает и суммирует один элемент за раз.
В параллельном алгоритме, умножающем матрицы NxM и MxP, каждый процессор должен принимать O (1) пространство, так как каждый процесс вычисляет одно значение умножения, но является O (X) в пространстве, где X - количество параллельных процессов, работающих на решение.
Кроме того, ответ на этот вопрос заключается в следующем: речь идет исключительно о том, как вы выбираете свое определение сложности памяти. –
Оли правильно +1 - ваши предположения/определения определяют объем возможных ответов. Я считаю, что субъективный подход - лучший способ выразить это. –