Trong phần này, chúng ta sẽ xem ma trận thưa thớt là gì và cách chúng ta có thể biểu diễn chúng trong bộ nhớ. Vì vậy, ma trận sẽ là ma trận thưa nếu hầu hết các phần tử của nó bằng 0. Một định nghĩa khác là, ma trận có tối đa 1/3 phần tử khác 0 (khoảng 30% của m x n) được gọi là ma trận thưa.
Chúng tôi sử dụng ma trận trong bộ nhớ máy tính để thực hiện một số hoạt động một cách hiệu quả. Nhưng nếu ma trận thưa thớt về bản chất, nó có thể giúp chúng ta thực hiện các phép toán một cách hiệu quả, nhưng nó sẽ chiếm dung lượng lớn hơn trong bộ nhớ. Không gian đó không có mục đích. Vì vậy, chúng tôi sẽ làm theo một số loại cấu trúc khác để lưu trữ ma trận thưa thớt.
Giả sử chúng ta có một ma trận thưa thớt như dưới đây -
Như chúng ta có thể thấy rằng có 8 phần tử khác 0 và 28 giá trị 0. Ma trận này đang chiếm 6 * 6 =36 không gian bộ nhớ. Nếu kích thước của ma trận lớn hơn, sự lãng phí không gian sẽ tăng lên.
Chúng ta có thể lưu trữ thông tin về ma trận thưa thớt bằng cách sử dụng cấu trúc bảng. Giả sử chúng ta sẽ tạo một bảng có tên X như bên dưới -
Ở đây cột đầu tiên giữ số Hàng và cột thứ hai giữ số cột. Cái thứ ba đang giữ dữ liệu hiện tại tại M [row, col]. Mỗi hàng của bảng này được gọi là bộ ba, vì có ba tham số. Bộ ba đầu tiên đang nắm giữ thông tin kích thước của ma trận. Hàng =6 và Cột =6 cho biết ma trận M là ma trận 6 x 6. Trường giá trị biểu thị số phần tử khác 0 có trong mảng.
Bảng này cũng chiếm 9 * 3 =36 lượng không gian, vậy lợi ích ở đâu? Nếu kích thước ma trận là 8 * 8 =64, nhưng chỉ có 8 phần tử hiện diện, thì bảng X cũng sẽ chiếm 36 đơn vị không gian. Chúng ta có thể thấy rằng có 3 cột cố định, số hàng thay đổi theo số phần tử khác không. Vì vậy, nếu có T số phần tử khác không, thì Độ phức của không gian sẽ là O (3 * T) =O (T). Đối với ma trận, nó sẽ là O (m x n).