我需要在 C++ 中实现两种类型的存储稀疏矩阵:
- 链表
- 数组(有效方式)
空间复杂度在这里非常重要。最有效的方法是什么？
最佳答案
nnz : 稀疏矩阵的非零数
row_size : 矩阵行数
column_size : 矩阵列数
有很多种方式，它们的空间复杂度:
- 压缩稀疏行(CSR):
2*nnz + row_size内存数 - 压缩稀疏列(CSC):
2*nnz + column_size内存数 - 坐标格式(COO):
3*nnz内存数
对于空间复杂度:
如果row_size > column_size，则使用CSC格式，否则，使用CSR格式。
对于时间复杂度:
对于CSR格式，Row会被O(1)时间索引，Column会被O(log(k))时间索引，通过二分查找Column，k是该行非零元素的个数。因此值将按 O(log(k)) 时间索引。
对于 COO 格式，值将在 O(1) 时间内被索引。
格式详情
[1] https://en.wikipedia.org/wiki/Sparse_matrix
[2] https://software.intel.com/en-us/node/471374
关于c++ - 如何存储稀疏矩阵？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30863206/