压缩稀疏行矩阵与邻接表

Question

3

...与许多其他图形格式（例如adjacency_list）相比，CSR图形具有更少的开销...

与邻接表相比，CSR在开销方面有什么改进？两者都需要O（|V| + |E|）内存来存储图形。我认为边缘存在操作的时间复杂度也是相同的。

这个开销是指什么？

编辑：经过一些思考，我有一种感觉，可能是因为矩阵每行中的每个元素都存储在连续的内存位置中？

- Kumalh

1个回答

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

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

- baol · Answer 1

区别在于常数和局部性。

请记住，O(n) 可能是 n、2*n 或固定的 C，任何 C*n :)

由于存储在内存的连续区域中，在算法执行过程中，数据需要获取的可能性较小。这可以通过另一个常数来提高算法的速度。