Какова сложность добавления матрицы?

Question

Я нашел some mentions in another question of matrix addition being a quadratic operation. Но я думаю, что он линейный.

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

Главной точкой расхождения, по-видимому, является размер проблемы. Для меня это число элементов в матрице. Другие считают, что это количество столбцов или строк, следовательно, сложность O(n^2).

Еще одна проблема, которую я рассматриваю как квадратичную операцию, состоит в том, что это означает, что добавление трехмерных матриц является кубическим, а добавление 4-мерных матриц равно O(n^4) и т. Д., Хотя все эти проблемы могут быть сведены к проблеме добавления двух векторов, который имеет, очевидно, линейное решение.

Я прав или неправильно? Если не так, почему?

Answer 1

Как вы уже отметили, это зависит от вашего определения размера проблемы: это общее количество элементов или ширина/высота матрицы. Который всегда правильный, зависит от большей проблемы, частью которой является дополнение матрицы.

NB: на некоторых аппаратных средствах (графические процессоры, векторные машины и т. Д.) Добавление может работать быстрее, чем ожидалось (хотя сложность остается прежней, см. Обсуждение ниже), поскольку аппаратное обеспечение может выполнять несколько дополнений за один шаг. Для ограниченного размера проблемы (например, n < 3) это может быть даже один шаг.

Answer 2

Это O (M * N) для двумерной матрицы с M строками и N столбцами.

Или вы можете сказать, что это O (L), где L - общее количество элементов.

Answer 3

думать о реализации в общем случае:

for 1 : n 
for 1 : m 
    c[i][j] = a[i][j] + b[i][j] 

если мы возьмем простую квадратную матрицу, то есть NxN дополнение

Answer 4

Обычно проблема определяется с использованием квадратных матриц «из размера N», что означает NxN , По этому определению сложение матрицы является O (N^2), так как вы должны посетить каждый из элементов NxN ровно один раз.

В этом же определении матричное умножение (с использованием квадратных матриц NxN) является O (N^3), поскольку вам нужно посетить N элементов в каждой из исходных матриц для вычисления каждого из элементов NxN в матрице продукта.

Как правило, все операции с матрицами имеют нижнюю границу O (N^2) просто потому, что вы должны хотя бы один раз посетить каждый элемент, чтобы вычислить все, что связано с всей матрицей.