链表作为矩阵和效率
Linked lists as matrix and efficiency
当算法中需要使用大矩阵时，为了加快复杂度，我们被告知在矩阵稀疏时使用 linked 列表。这意味着如果数据大部分相同，我们只能保存不是该值的数据。
但是我们如何确定使用稀疏矩阵不再有用的点？
对于长度为 n 的方阵，我们如何计算可以说矩阵有太多非零数据要写入 [=22] 的点=]编辑列表？
我想我们需要使用一个对象的内存大小，两个对象之间的 link，然后使用我们的密度因子。但是安全地说 "这个矩阵有 x% 非零数据的计算是什么，最好使用 linked 列表 ?
您问题的答案取决于您的优化目标。你优化 space 还是时间？
假设您针对 space 进行了优化。要保留长度为 n 的方阵数据，您需要 n*n 个数字（为简化起见，假设每个值都是一个整数）。在链表的情况下，您需要具有实际值、矩阵中值的坐标以及指向下一个非零值的指针。为简化起见，假设这些字段中的每一个都是整数大小。因此，对于链表，您需要 4 个整数来保留单个值（加上其他数据，如链表的头部）。
恕我直言，一旦矩阵中不到 1/4 的值非零，使用链表比使用数组的数组更优化。
显然，还有其他选项可以保留矩阵值；那么比例可以不同。
要针对时间进行优化，同样，这取决于您要对哪些操作进行 运行...
当算法中需要使用大矩阵时，为了加快复杂度，我们被告知在矩阵稀疏时使用 linked 列表。这意味着如果数据大部分相同，我们只能保存不是该值的数据。
但是我们如何确定使用稀疏矩阵不再有用的点？
对于长度为 n 的方阵，我们如何计算可以说矩阵有太多非零数据要写入 [=22] 的点=]编辑列表？
我想我们需要使用一个对象的内存大小，两个对象之间的 link，然后使用我们的密度因子。但是安全地说 "这个矩阵有 x% 非零数据的计算是什么，最好使用 linked 列表 ?
您问题的答案取决于您的优化目标。你优化 space 还是时间？
假设您针对 space 进行了优化。要保留长度为 n 的方阵数据，您需要 n*n 个数字（为简化起见，假设每个值都是一个整数）。在链表的情况下，您需要具有实际值、矩阵中值的坐标以及指向下一个非零值的指针。为简化起见，假设这些字段中的每一个都是整数大小。因此，对于链表，您需要 4 个整数来保留单个值（加上其他数据，如链表的头部）。
恕我直言，一旦矩阵中不到 1/4 的值非零，使用链表比使用数组的数组更优化。
显然，还有其他选项可以保留矩阵值；那么比例可以不同。
要针对时间进行优化，同样，这取决于您要对哪些操作进行 运行...