memory-management - 邻接表表示所需的内存如何是 O(V+E)？

Question

该声明如何有效？

“对于有向图和无向图，邻接表表示具有理想的特性，即它需要的内存量是 O(V+E)。”

资料来源：算法简介，cormen。

Answer 1

假设您将邻接列表存储在一个数组中，即

edges[v] represents a list of edges outgoing from v

为了测量空间复杂度，首先只需注意V数组中有确切的记录，每个顶点都有一个记录。因此，您正在使用O(V)内存来存储空列表。

接下来，请注意，如果图是有向图，则每条边在这些列表的数组中只出现一次。

如果图是无向图，则每条边在这些列表的数组中恰好出现两次。

在这两种情况下，整个数组中的条目数最多为2 * E = O(E).

放在一起，我们看到内存的总数是有界的O(V + E)，与 相同O(max(V, E))。

当且仅当图是一组不相交的树（称为福雷斯特）时，该术语才V超过。E

Answer 2

我想你可以这样想，如果你有 10 个顶点和 30 条边，那么让 v 和 E 代表你存储每个顶点和边所需的存储空间。

10(V+E)<=(10V+30E)<=30(V+E)

根据上述等式，您可以得出结论，它需要Ѳ(V+E) 空间。