数据结构中的稀疏矩阵

在本节中，我们将了解什么是稀疏矩阵以及如何在内存中表示它们。如果矩阵的大部分元素为0，则该矩阵为稀疏矩阵。另一个定义是，非零元素最多为1/3（大约m x n的30%）的矩阵称为稀疏矩阵。

我们在计算机内存中使用矩阵以高效的方式执行某些操作。但是，如果矩阵本质上是稀疏的，它可能有助于我们高效地执行操作，但它会在内存中占用更大的空间。这些空间毫无用处。因此，我们将遵循其他类型的结构来存储稀疏矩阵。

假设我们有一个如下所示的稀疏矩阵：

我们可以看到有8个非零元素和28个零值。此矩阵占用6*6 = 36个内存空间。如果矩阵的大小更大，则空间浪费将会增加。

我们可以使用表结构来存储有关稀疏矩阵的信息。假设我们将创建一个名为X的表，如下所示：

这里，第一列保存行号，第二列保存列号。第三列保存M[row, col]中存在的数据。此表的每一行都称为三元组，因为有三​​个参数。第一个三元组保存矩阵的大小信息。Row = 6和Column = 6表示矩阵M是6 x 6矩阵。value字段表示数组中存在的非零元素的数量。

此表也占用9 * 3 = 36个空间，那么优势在哪里呢？如果矩阵大小为8*8 = 64，但只有8个元素，那么表X也将占用36个单元的空间。我们可以看到有固定的3列，行数随非零元素的数量而变化。因此，如果有T个非零元素，则空间复杂度将为O(3*T) = O(T)。对于矩阵，它将是O(m x n)。

更新于：2020年8月10日

5K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告