algorithm - 邻接矩阵和邻接表的时间/空间复杂度

Question

我正在阅读 Eva Tardos 的“算法设计”，在第 3 章中提到邻接矩阵的复杂度为 O(n^2)，而邻接列表的复杂度为 O(m +n) 其中 m 是边的总数，n 是节点的总数。它说在邻接列表的情况下，我们将只需要每个节点大小为 m 的列表。

在邻接列表的情况下，我们是否会得到类似于矩阵的东西，因为我们有列表，它也是一维数组。所以根据我的说法，基本上是 O(m*n)。请指导我。

Answer 1

邻接矩阵为每对节点保留一个值 (1/0)，无论边是否存在，因此它需要 n*n 空间。

邻接列表仅包含现有的边，因此它的长度最多为边数(或者节点数，如果边数少于节点数)。

It says that in-case of adjacency list we will need only lists of size m for each node.

我想你误解了那部分。邻接表不为每个节点保存一个大小为m的列表，因为m是边数总体而言。

在全连接图中，每对节点之间都有一条边，因此邻接表和矩阵都需要 n*n 空间，但对于其他所有情况 - 邻接表将是更小。