algorithm - Graph 的 Adjacency List 表示的空间复杂度

Question

我读了here对于无向图，当表示为邻接表时，空间复杂度为 O(V + E)，其中 V 和 E 是顶点数，边缘分别。

我的分析是，对于一个完全连接的图，列表的每个条目都将包含 |V|-1 个节点，因此我们总共有 |V| 个顶点，空间复杂度似乎是 O(|V|*|V-1|) 这似乎是 O(|V|^2) 我在这里缺少什么？

Answer 1

您对完全连通图的分析是正确的。但是，请注意，对于完全连接的图，边数 E 本身就是 O(V^2)，因此符号 O(V+E) 对于空间复杂度也是正确的。

然而，邻接表的真正优势在于它们可以为并非真正密集连接的图节省空间。如果边数远小于 V^2，则邻接表将采用 O(V+E)，而不是 O(V^2) 空间。

---

请注意，当您谈论 O-notation 时，您通常有三种类型的变量(或者，一般来说，输入数据)。首先是您正在研究的变量依赖性；其次是那些被认为是常数的变量；第三种是“自由”变量，您通常假设它们采用最坏情况 值。例如，如果您谈论对 N 整数数组进行排序，您通常想研究排序时间对 N 的依赖性，因此 N是第一类。您通常认为整数的大小是恒定的(也就是说，您假设比较是在 O(1) 等中完成的)，并且您通常认为特定的数组元素是“自由的” ，也就是说，您研究特定数组元素的最坏可能组合的运行时间。但是，你可能想从不同的角度研究同一个算法，这将导致不同的复杂性表达。

对于图算法，当然可以考虑顶点数V为第一类，边数为第三类，研究给定的空间复杂度V 和最坏情况下的边数。然后你确实得到了 O(V^2)。但是，将 V 和 E 都视为第一类型的变量通常也很有用，从而得到复杂度表达式为 O(V+E).