在CRS稀疏矩陣中查找值？

Question

我是使用稀疏矩陣的新手，但現在需要在我的工作中利用一個來節省空間。據我所知，下面的矩陣：

10 0 0 0 -2 0 
3 9 0 0 0 3 
0 7 8 7 0 0 
3 0 8 7 5 0 
0 8 0 9 9 13 
0 4 0 0 2 -1 

可以與這樣的三個矢量來表示：

[10 -2 3 9 3 7 8 7 3 8 7 5 8 9 9 13 3 2 -1] // nonzero_vals 

[1 5 1 2 6 2 3 4 1 3 4 5 2 4 5 6 2 5 6] // col_indices 

[1 3 6 9 13 17 20] // row_ptr (indices of values that start row) 

我的問題是現在確定用於在O（1）時間值查找適當的方程式。例如，如果我想要返回位置（2,2）處存儲的矩陣值，我該如何返回9？另外，如果查找座標未在稀疏矩陣中表示，那麼在O（1）時間內如何返回0？

我很感謝您提供的任何幫助。我確信這方面有很好的方程式，但我無法找到它們。

Answer 1

沒有爲在任意（I，J）獲得的值沒有O（1）過程座標（至少在沒有預處理）。通過對列索引的二分搜索程序，您可以做的最好的平均值爲O（log N）（其中矩陣是MxN）。 ^*

---

_{*好了，說實在的，爲O（log k）的，其中ķ是行非零的個數。但是，如果假定密度與矩陣大小無關（通常是這種情況），那麼O（logN）是有效的。}