我在这里读到，对于无向图，空间复杂度是O(V + E)用邻接表表示的，其中V和E分别是顶点和边的数量。
我的分析是，对于完全连接的图，列表的每个条目都将包含|V|-1节点，那么我们总共有|V|顶点，因此，空间复杂性O(|V|*|V-1|)似乎O(|V|^2)是我在这里缺少的东西？
Pet*_*etr 14
您的分析对于完全连接的图形是正确的。但是，请注意，对于完全连接的图，边数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)。