作爲矩陣和效率的鏈接列表

Question

當算法中需要使用大矩陣時，爲了加速複雜性，如果矩陣很稀疏，我們被告知要使用鏈表。這意味着如果數據大部分相同，我們只能保存那些不是那個值的數據。

但是，我們如何識別使用稀疏矩陣不再有用的點？

對於長方形矩陣n我們如何計算可以說矩陣中有太多非零數據要寫入鏈表中的點？

我想我們需要使用對象的內存大小，兩個對象之間的鏈接，然後使用我們的密度因子。但什麼是計算安全地說「此矩陣有x％非零數據，最好使用鏈接列表？

Answer 1

您的問題的答案取決於您優化的內容。空間還是時間？

假設你對空間進行了優化爲了保留長度爲n的方陣的數據，你需要n * n個數字（爲了簡化，假設它是每個值的整數）。你需要有實際的值，矩陣中的值的協調以及指向下一個非零值的指針。爲了簡單起見，我們假設每個字段都是整數大小，所以對於鏈表，你需要4個整數來保存單個值（加上像頭部之類的附加數據）鏈表）。恕我直言，一旦少於矩陣中的值的1/4是非零，使用鏈表比數組數組更好。

顯然，還有其他選項可以保持矩陣值;那麼比例可以不同。

要再次優化時間，它取決於您想要運行哪些操作...