我在这里读到，对于无向图，当表示为邻接列表时，空间复杂度为O(V + E)，其中V和E分别是顶点和边的数量。
我的分析是，对于一个完全连通的图，列表中的每个条目都将包含|V|-1个节点，那么我们总共有|V|个顶点，因此，空间复杂性似乎是O(|V|*|V-1|)，这似乎是O(|V|^2)，我在这里缺少什么？
对于完全连通图，您的分析是正确的。然而，请注意，对于完全连通图，边的数量E本身就是O(V^2)，因此空间复杂度的符号O(V+E)也是正确的。
然而，邻接表的真正优点是，它们可以为那些不是真正密集连接的图节省空间。如果边的数量比V^2小得多，则邻接列表将占用O(V+E)空间，而不占用O(V^2)空间。
请注意，当您讨论O表示法时，通常有三种类型的变量（或者，通常是输入数据）。首先是你所研究的变量依赖性；其次是那些被认为是常数的变量；第三种是"自由"变量，通常假设为最坏情况的值。例如，如果您讨论对一个N整数数组进行排序，通常需要研究排序时间对N的依赖性，因此N是第一种。你通常认为整数的大小是恒定的（也就是说，你假设比较是在O(1)中完成的，等等），你通常认为特定的数组元素是"自由的"，也就是说你研究特定数组元素的最坏组合的运行时。然而，您可能希望从不同的角度研究相同的算法，这将导致复杂性的不同表达。
对于图算法，当然，你可以考虑顶点的数量V是第一类，边的数量是第三类，并研究给定V和最坏情况下边的数量的空间复杂性。那么你确实得到了O(V^2)。但是，将V和E都视为第一种类型的变量通常也是有用的，从而将复杂度表达式视为O(V+E)。
数组的大小为|V|（|V|为节点数）。这些|V|列表中的每一个都具有由deg（V）表示的度数。我们把所有这些加起来，然后应用握手引理。∑deg（v）=2|E|。
因此，您有|V|引用（到|V|列表）加上列表中的节点数，它永远不会超过2|E|。因此，邻接列表的最坏情况空间（存储）复杂度是O（|V|+2|E|）=O（|V|+|E|。
希望这能帮助
根据u r逻辑，总空间=O（v^2-v）由于连接的总数量（E）=v^2-v，空间＝O（E）。甚至我以前也这么想，但是，如果连接的总数（E）远小于顶点的数量（V），比方说在10个人中（V＝10），只有两个相互认识，因此（E=2）那么根据你的逻辑空间=O（E）=O（2）但实际上我们必须分配更大的空间哪个是空格=O（V+E）=O（V+2）=O这就是为什么，space＝O（V+E），如果V>E或E>V