Czym jest złożoność dodawania macierzy?

Question

Znalazłem some mentions in another question of matrix addition being a quadratic operation. Ale myślę, że jest liniowy.

Jeśli podwoję rozmiar macierzy, muszę obliczyć podwójne dodatki, a nie poczwórne.

Głównym punktem rozbieżności wydaje się być rozmiar problemu. Dla mnie jest to liczba elementów w macierzy. Inni uważają, że jest to liczba kolumn lub linii, stąd złożoność O(n^2).

Innym problemem, jaki mam z widzeniem go jako operację kwadratową, jest to, że oznacza to, że dodawanie macierzy trójwymiarowych jest sześcienne, a dodawanie macierzy 4-wymiarowych to O(n^4) itp., Mimo że wszystkie te problemy można zredukować do problemu dodania dwóch wektorów, które mają oczywiście liniowe rozwiązanie.

Czy mam rację czy nie? Jeśli jest źle, dlaczego?

Answer 1

Jak już wspomniano, zależy to od definicji rozmiaru problemu: czy jest to całkowita liczba elementów, czy szerokość/wysokość macierzy. To, co kiedykolwiek jest poprawne, zależy od większego problemu, którego częścią jest dodatek matrycowy.

NB: na niektórych urządzeniach (GPU, maszyny wektorowe itp.) Dodanie może przebiegać szybciej niż oczekiwano (nawet jeśli złożoność jest wciąż taka sama, patrz dyskusja poniżej), ponieważ sprzęt może wykonać wiele dodatków w jednym kroku. W przypadku ograniczonego rozmiaru problemu (np. N < 3) może to być nawet jeden krok.

Answer 2

To O (M * N) dla dwuwymiarowej macierzy z M rzędami i N kolumnami.

Albo możesz powiedzieć, że to O (L), gdzie L to całkowita liczba elementów.

Answer 3

myśleć o realizacji ogólnym przypadku:

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

jeśli weźmiemy prostą macierz kwadratowa, czyli NxN uzupełnienia

Answer 4

Zazwyczaj problem jest określona przy użyciu matryc kwadrat „o rozmiarze N”, czyli NxN . Zgodnie z tą definicją dodanie macierzy jest O (N^2), ponieważ musisz odwiedzić każdy z elementów NxN dokładnie jeden raz.

Zgodnie z tą samą definicją, mnożenie macierzy (przy użyciu kwadratowych macierzy NxN) jest równe O (N^3), ponieważ trzeba odwiedzić N elementów w każdej z macierzy źródłowych, aby obliczyć każdy z elementów NxN w macierzy produktu.

Ogólnie rzecz biorąc, wszystkie operacje macierzy mają dolną granicę O (N^2) po prostu dlatego, że musisz co najmniej odwiedzać każdy element, aby obliczyć cokolwiek związanego z całą macierzą.