행렬 추가의 복잡성은 무엇입니까?

Question

나는 some mentions in another question of matrix addition being a quadratic operation을 발견했다. 그러나 그것은 선형이라고 생각합니다.

행렬의 크기를 두 배로하면 4 배가 아닌 2 배의 덧셈을 계산해야합니다.

주요 분기점은 문제의 크기 인 것처럼 보입니다. 나에게 매트릭스의 요소 수입니다. 다른 사람들은 이것이 열 또는 행의 수라고 생각하므로 복잡성은 O(n^2)입니다.

I는 이차 수술로보고에있는 또 다른 문제는 이러한 모든 문제는 문제가 감소 될 수있다하더라도, 등, 3 차원 매트릭스를 추가하는 입방정, 4 차원의 행렬을 추가하는 O(n^4) 수단이다 분명히 선형적인 해법을 가진 두 개의 벡터를 더하는 것입니다.

내가 옳은가요? 틀렸다면, 왜?

Answer 1

이미 언급했듯이 문제 크기의 정의에 따라 다릅니다 : 요소의 총 개수 또는 행렬의 너비/높이입니까? 어느 것이 정확한지는 실제로 행렬 더하기의 일부인 더 큰 문제에 달려 있습니다.

NB : 일부 하드웨어 (GPU, 벡터 머신 등)에서는 하드웨어가 한 단계에서 여러 번 추가를 수행 할 수 있기 때문에 추가가 예상보다 빠르게 실행될 수 있습니다 (복잡성은 여전히 ​​동일합니다. 아래 설명 참조). 한정된 문제 크기 (예 : n < 3)의 경우 한 단계 일 수도 있습니다.

Answer 2

M 행과 N 열이있는 2 차원 행렬의 경우 O (M * N)입니다.

또는 O (L)라고 할 수 있습니다. 여기서 L은 총 요소 수입니다. 일반적인 경우 구현의

Answer 3

생각 : 우리가 간단한 정방 행렬을 경우

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

, 그에서는 N × N을 의미 NXN 추가

보통 문제가 "크기 N의"사각 행렬을 사용하여 정의

Answer 4

입니다 . 이 정의에 따르면 NxN 요소 각각을 정확히 한 번 방문해야하기 때문에 행렬 추가는 O (N^2)입니다.

동일한 정의에 따라 행렬 곱셈 (제곱 NxN 행렬 사용)은 O (N^3)입니다. 왜냐하면 제품 행렬의 NxN 요소 각각을 계산하기 위해 각 소스 행렬에서 N 요소를 방문해야하기 때문입니다.

일반적으로 모든 행렬 연산은 O (N^2)의 경계가 있습니다. 왜냐하면 전체 행렬과 관련된 모든 것을 계산하기 위해 각 요소를 최소한 한 번 방문해야하기 때문입니다.