图的邻接表表示的空间复杂性

Question

我在这里读到，对于无向图，当表示为邻接表时，空间复杂度是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)。