如何存储稀疏矩阵？

Question

6

我需要在C++中实现两种稀疏矩阵的存储方式：

这里空间复杂度非常重要。有哪些最有效的方法可以实现？

- sayhello

3个回答

2

一种高效的方法是使用哈希映射（对于每一行）的哈希映射（按列索引存储每一行的元素）。然后能够在O(1)时间内访问任何元素。

您可以通过仅迭代非零元素来实现所有数字算法，例如加法和乘法，这将为您提供比矩阵中列数和行数N * M更好的复杂度。

- Ivan Mushketyk

1

由于矩阵是稀疏的，您只需要存储填充的单元格。简单地将坐标与值进行查找即可。理想情况下，您应该使用具有快速查找功能的内容，例如map O(log n)或unordered_map O(1)。

- doron

但是我需要使用链表和数组。 - sayhello

使用链表或数组将为您提供O(n)时间 - 对于小的n值而言，速度较慢但绝对可行。如果您可以对数组进行排序，则可以执行二分查找，其时间复杂度为O(log n)。 - doron

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- pgplus1628 · Accepted Answer

nnz：稀疏矩阵中非零元素的数量
row_size：矩阵的行数
column_size：矩阵的列数
有许多方法可以表示稀疏矩阵，它们的空间复杂度为：

对于空间复杂度：
如果 row_size > column_size，使用 CSC 格式，否则使用 CSR 格式。

对于时间复杂度：
对于 CSR 格式，通过行索引需要 O(1) 的时间，通过二分查找列索引需要 O(log(k)) 的时间，其中 k 是该行非零元素的数量。因此，通过值索引需要 O(log(k)) 的时间。
对于 COO 格式，值可以在 O(1) 的时间内索引。