gpt4 book ai didi

c++ - 如何存储稀疏矩阵?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:01:33 24 4
gpt4 key购买 nike

我需要在 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/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com