我读了here对于无向图,当表示为邻接表时,空间复杂度为 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
-notation 时,您通常有三种类型的变量(或者,一般来说,输入数据)。首先是您正在研究的变量依赖性;其次是那些被认为是常数的变量;第三种是“自由”变量,您通常假设它们采用最坏情况 值。例如,如果您谈论对 N
整数数组进行排序,您通常想研究排序时间对 N
的依赖性,因此 N
是第一类。您通常认为整数的大小是恒定的(也就是说,您假设比较是在 O(1)
等中完成的),并且您通常认为特定的数组元素是“自由的” ,也就是说,您研究特定数组元素的最坏可能组合的运行时间。但是,你可能想从不同的角度研究同一个算法,这将导致不同的复杂性表达。
对于图算法,当然可以考虑顶点数V
为第一类,边数为第三类,研究给定的空间复杂度V
和最坏情况下的边数。然后你确实得到了 O(V^2)
。但是,将 V
和 E
都视为第一类型的变量通常也很有用,从而得到复杂度表达式为 O(V+E)
.
关于algorithm - Graph 的 Adjacency List 表示的空间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33499276/