生成稀疏矩阵的复杂度

Question

我有一个对称矩阵 S(n*n)，其中大约 70% 的数据为 0。

对称矩阵

我想将对称矩阵转换为具有 t 行的稀疏矩阵。

从原始对称矩阵生成稀疏矩阵的时间复杂度是多少？

是 O(n^2)，因为我必须遍历每一行/列的交叉点并获取不为 0 的元素？

由于我正在处理一个对称矩阵，我可以说我的时间复杂度可以减少到 O((n*(n+1))/2) 因为在对称矩阵中 a[i][j]= a[j] [一世]？在这种情况下，如果我遇到 a[i][j] 为 0，我可以说 a[j][i]=0。这可以将我的循环减少大约一半。

Answer 1

当从对称矩阵的完整表示转换为稀疏表示时，您需要扫描主对角线上及上方（或主对角线上及下方对称）的所有元素。对于 (nxn) 矩阵矩阵，这是需要扫描的 (n^2+n)/2 个条目。因此，您需要执行 O(n^2) 工作来确定需要输入到稀疏矩阵中的内容。

在构建稀疏矩阵时，您需要将原始矩阵中的所有非空条目存储到您的稀疏矩阵中。对于 0 矩阵，这不需要额外的工作，对于完全密集的矩阵，这需要 (n^2+n)/2 次插入操作。

因此，从对称矩阵转换为稀疏表示总是需要 O(n^2) 时间——实际上它需要 Theta(n^2) 时间。