如何存储稀疏矩阵？

How to store sparse matrix?

我需要在 C++ 中实现 2 种存储稀疏矩阵的类型：

Space 复杂性在这里非常重要。最有效的方法是什么？

由于矩阵是稀疏的，您只需要存储已填充的单元格。只需简单地查找坐标值即可。理想情况下，您应该使用快速查找的东西，例如地图 O(log n) 或 unordered_map O(1).

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

您可以实现所有数值算法，例如仅通过非零元素迭代的加法和乘法，这将使您比 O(N * M) 更复杂，其中 N 和 M 是矩阵中的列数和行数。

nnz : 稀疏矩阵的非零数
row_size : 矩阵行数
column_size : 矩阵列数
方法有很多种，它们的 space 复杂度：

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

对于时间复杂度：
对于CSR格式，Row会被索引O(1)次，Column会被索引O(log(k))次，通过二分查找Column，k是非零的个数该行的元素。因此值将按 O(log(k)) 时间索引。
对于 COO 格式，值将在 O(1) 时间内被索引。