이 섹션에서는 희소 행렬이 무엇이고 메모리에서 어떻게 표현할 수 있는지 알아보겠습니다. 따라서 행렬의 요소 대부분이 0인 경우 행렬은 희소 행렬이 됩니다. 또 다른 정의는 최대 1/3의 0이 아닌 요소(m x n의 약 30%)가 있는 행렬을 희소 행렬이라고 합니다.
우리는 효율적인 방법으로 몇 가지 작업을 수행하기 위해 컴퓨터 메모리의 행렬을 사용합니다. 그러나 행렬이 본질적으로 희소하면 연산을 효율적으로 수행하는 데 도움이 될 수 있지만 메모리에서 더 많은 공간을 차지합니다. 그 공간은 목적이 없습니다. 그래서 우리는 희소 행렬을 저장하기 위해 다른 종류의 구조를 따를 것입니다.
아래와 같은 희소 행렬이 있다고 가정합니다. -
우리가 볼 수 있듯이 8개의 0이 아닌 요소와 28개의 0 값이 있습니다. 이 행렬은 6*6 =36개의 메모리 공간을 차지합니다. 매트릭스의 크기가 클수록 공간 낭비가 증가합니다.
테이블 구조를 사용하여 희소 행렬에 대한 정보를 저장할 수 있습니다. 아래와 같이 X라는 테이블을 생성한다고 가정해 보겠습니다. -
여기서 첫 번째 열은 행 번호를 보유하고 두 번째 열은 열 번호를 보유합니다. 세 번째는 M[row, col]에 있는 데이터를 보유하고 있습니다. 이 테이블의 각 행은 세 개의 매개변수가 있으므로 삼중항이라고 합니다. 첫 번째 삼중항은 행렬의 크기 정보를 담고 있습니다. Row =6 및 Column =6은 행렬 M이 6 x 6 행렬임을 나타냅니다. 값 필드는 배열에 있는 0이 아닌 요소의 수를 나타냅니다.
이 테이블도 9 * 3 =36의 공간을 차지하므로 이득은 어디에 있습니까? 행렬 크기가 8*8 =64이지만 8개의 요소만 있는 경우 테이블 X도 36단위의 공간을 차지합니다. 고정된 3개의 열이 있고 행의 수는 0이 아닌 요소의 수에 따라 다릅니다. 따라서 0이 아닌 요소가 T개 있는 경우 공간 복잡성은 O(3*T) =O(T)가 됩니다. 행렬의 경우 O(m x n)입니다.