使用稀疏矩阵检查断点的算法

Question

我想使用稀疏矩阵或矩阵，取决于效率和space节省

我正在尝试找到更有效的方法并在 运行 时间内节省 space

矩阵的大小在变化，但每个值都是字符（可以什么都不是 -‘[=10=]’）

我正在从文件中读取矩阵值的数据...

(每个文件的开头都有矩阵的大小)

提前致谢

Answer 1

您可以将其视为图形表示。 如您所知，如果您使用矩阵，space 复杂度将是 |V|^2（|V| 是节点数）。 此外，如果您使用邻接矩阵（或稀疏矩阵），space 复杂度将为 |V||E|，其中 |E| 是与节点相关的非零字符串的数量。

因此，您可以遍历文件并比较|V|^2和|V||E|，并根据这两个值来决定。