Какова сложность матричного дополнения?
Это предотвращает меньше (меньше больше) от очистки экрана в конце файла:
export LESS="-X"
4 ответа
Как вы уже отметили, это зависит от вашего определения размера проблемы: это общее количество элементов или ширина / высота матрицы. Что когда-либо будет правильным, на самом деле зависит от более крупной проблемы, частью которой является матричное сложение.
NB: на некотором оборудовании (графический процессор, векторные машины и т. Д.) Добавление может выполняться быстрее, чем ожидалось (даже если сложность остается той же, см. Обсуждение ниже), поскольку оборудование может выполнять несколько добавлений за один шаг. . Для ограниченного размера задачи (например, n <3) это может быть даже один шаг.
Это O (M * N) для 2-мерной матрицы с M строками и N столбцами .
Или вы можете сказать, что это O (L), где L - общее количество элементов.
Обычно проблема определяется с использованием квадратных матриц «размера N», что означает NxN. Согласно этому определению, сложение матриц - это O (N ^ 2), поскольку вы должны посетить каждый из элементов NxN ровно один раз.
По тому же определению умножение матриц (с использованием квадратных матриц NxN) равно O (N ^ 3), потому что вам необходимо посетить N элементов в каждой из исходных матриц, чтобы вычислить каждый из элементов NxN в матрице продукта.
Как правило, все операции с матрицами имеют нижнюю границу O (N ^ 2) просто потому, что вы должны посетить каждый элемент хотя бы один раз, чтобы вычислить что-либо, связанное со всей матрицей.
подумайте о реализации в общем случае:
for 1 : n
for 1 : m
c[i][j] = a[i][j] + b[i][j]
если мы возьмем простую квадратную матрицу, то есть nxn сложения